Aggiornamento
Ho sviluppato un algoritmo molto più rapido, basato su questa considerazione:
Se esprimiamo un numero buono nella forma $\displaystyle c^2=a^2 \cdot 10^n + b^2$ dove $a^2$ ha $n$ cifre e $b^2$ ha massimo $n$ cifre
la sua radice $c=\sqrt{a^2 \cdot 10^n + b^2}$ sarà compresa fra $a \sqrt{10^n}$ e $\sqrt{(a^2+1)}\sqrt{10^n}$
Quindi partendo da $a$ non serve verificare tutti i valori possibili di $b$ ma solo in valori interi di $c$ compresi nel range indicato, che sono al massimo 3.
Questo riduce incredibilmente il tempo di elaborazione, consentendo di usare l'impostazione a 1000 cifre di Decimal Basic e di trattare numeri di 28 cifre in tempi ragionevoli.
Ecco le statistitche aggiornate:
Codice: Seleziona tutto
n 2n buoni
1 2 1
2 4 1
3 6 5
4 8 1
5 10 12
6 12 1
7 14 24
8 16 2
9 18 47
10 20 2
11 22 53
12 24 1
13 26 70
14 28 1
15 30 136
16 32 1
Qualche considerazione:
1) Se prendiamo un numero buono di
2n cifre con
n dispari e lo esprimiamo come $c^2=(ka)^2 \cdot 10^n+(kb)^2$ con
k intero positivo e mcd(a,b)=1, diciamo che [a,b] è una coppia generatrice.
Risulta che $(ka)^2 \cdot 10^n+(kb)^2=k^2(a^2 \cdot 10^n+b^2)$ è un quadrato perfetto per ogni
k, ma sono buoni solo quelli che hanno
2n cifre
Esempio: [79,18] è una coppia generatrice per
n=5 e produce i seguenti quadrati:
624100324 ; ( 24982 ) - [79 / 18] non buono (ha 9 cifre)
2496401296 ; ( 49964 ) - [ 158 / 36 ] - buono
5616902916 ; ( 74946 ) - [ 237 / 54 ] - buono
9985605184 ; ( 99928 ) - [ 316 / 72 ] - buono
15602508100 ; ( 124910 ) - [ 395 / 90 ] - non buono (ha 11 cifre)
2) Le coppie generatrici per un dato valore di
n possono produrre numeri buoni per altri valori di
n, moltiplicando il secondo termine per potenze di 10.
Ad esempio se [a,b] è una coppia generatrice per
n=5, [a,10b] è una coppia generatrice per
n=7, infatti $a^2 \cdot 10^{n+2}+(10b)^2=100(a^2 \cdot 10^n+b^2)$
non è detto però che produca numeri buoni.
[79,180] è una coppia generatrice per
n=7 e produce numeri buoni per k da 13 a 17:
10547295475600 ; ( 3247660 ) - [ 1027 / 2340 ]
12232366350400 ; ( 3497480 ) - [ 1106 / 2520 ]
14042257290000 ; ( 3747300 ) - [ 1185 / 2700 ]
15976968294400 ; ( 3997120 ) - [ 1264 / 2880 ]
18036499363600 ; ( 4246940 ) - [ 1343 / 3060 ]
+++++++++++++++++++++++++++++++++++++++++++
Modifica 1:
Come abbiamo visto esiste una formula per generare un numero buono di
2n cifre con
n pari ($c^2=a^2\cdot10^n+b^2)$)
radice della prima parte: $\displaystyle a=\frac{\sqrt{10^n}-2}{2}$
radice della seconda parte: $\displaystyle b=\sqrt{10^n}-1=\frac{10^n}{4}-a^2$
La stessa regola ne genera 2 per
n dspari e maggiore di 1 (testato non dimostrato)
1)
radice della prima parte: $\displaystyle a_1=\left\lfloor\frac{\sqrt{10^n}}{2}\right\rfloor$
radice della seconda parte: $\displaystyle b_1=\frac{10^n}{4}-{a_1}^2$
2)
radice della prima parte: $\displaystyle a_2=a_1+1$
radice della seconda parte: $\displaystyle b_2={a_2}^2-\frac{10^n}{4}$
A titolo d'esempio:
225625 ; ( 475 ) - [ 15 - 25 ]
256036 ; ( 506 ) - [ 16 - 6 ]
2496401296 ; ( 49964 ) - [ 158 - 36 ]
2528178961 ; ( 50281 ) - [ 159 - 281 ]
24995610192721 ; ( 4999561 ) - [ 1581 - 439 ]
25027247420176 ; ( 5002724 ) - [ 1582 - 2724 ]
249987721150773841 ; ( 499987721 ) - [ 15811 - 12279 ]
250019344374190336 ; ( 500019344 ) - [ 15812 - 19344 ]
2499972076977969951361 ; ( 49999720769 ) - [ 158113 - 279231 ]
2500003699601368704016 ; ( 50000036996 ) - [ 158114 - 36996 ]
24999973750446890394001936 ; ( 4999997375044 ) - [ 1581138 - 2624956 ]
25000005373210288713857041 ; ( 5000000537321 ) - [ 1581139 - 537321 ]
249999990486544090505845063936 ; ( 499999990486544 ) - [ 15811388 - 9513456 ]
250000022109321488822075081041 ; ( 500000022109321 ) - [ 15811389 - 22109321 ]
2499999999733768900007087899860721 ; ( 49999999997337689 ) - [ 158113883 - 2662311 ]
2500000031356545698323295196487936 ; ( 50000000313565456 ) - [ 158113884 - 313565456 ]
+++++++++++++++++++++++++++++++++++++++++++
Modifica 2:
Le formule viste sopra si possono generalizzare:
radice della prima parte: $\displaystyle a=\left\lceil{\frac{\sqrt{10^n}}{k}}\right\rceil-j$ con $j=\{0, 1\}$ e $\displaystyle k \in \mathbb{Q} \mid 1\le k< \sqrt{10}$
radice della seconda parte: $\displaystyle b=\left|\frac{10^n}{2k}-\frac{ka^2}{2}\right|$
Al momento non è possibile determinare k, per cui si deve procedere per tentativi. Alcuni valori come 1, 2 e 2,5 producono numeri buoni in quasi ogni ordine di cifre.
Il limite operativo di Decimal Basic ci consente di ricavare un numero buono di 1006 cifre:
Codice: Seleziona tutto
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999947052647186202070832045361844190048442754676687703867682322695235704613473332772572821557450304404977229196293382157078354684390879676450331497114657392613711598538394628506777780702883836955904351725358187413459707480926998959230323331412690143784912470085554249719887183014805274697878072565720883552216263884692442370529881685587511480612448649635479434161634991029549087562256738432399311064765017320476660555459818376474310863574818028190791558583338881363513219237283791767627160114439441934410189838514889184219841035129192364118328433726488496182906730114055094576695353464201507588233447706097612431490043845334502071553702370199991860543600697259040947024455009221703433160625507621844468139487799366056129972303193937907444990511770325846891844;
(9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999735263235931010354160226809220950242213773383438519338411613476178523067366663862864107787251522024886145981466910785391773421954398382251657485573286963068557992691973142533888903514419184779521758626790937067298537404634994796151616657063450718924562)
[316227766016837933199889354443271853371955513932521682685750485279259443863923822134424810837930029518734728415284005514854885603045388001469051959670015390334492165717925994065915015347411333948412408531692957709047157646104436925787906203780860994182] -
[264736764068989645839773190779049757786226616561480661588386523821476932633336137135892212748477975113854018533089214608226578045601617748342514426713036931442007308026857466111096485580815220478241373209062932701462595365005203848383342936549281075438]
+++++++++++++++++++++++++++++++++++++++++++
Modifica 3:
completata la ricerca fino a 32 cifre (che ha richiesto quasi 2 giorni), anche qui 1 solo numero buono
Per tornare al quesito iniziale:
d) No, la probabilità che ci sia più di un numero buono di 100 cifre è piuttosto bassa, quella che ce ne siano 10 è abbastanza remota
e) Sì, esiste un numero buono di 30 cifre (ne esistono 136)
$\displaystyle a=\left\lceil{\frac{\sqrt{10^{15}}}{2}}\right\rceil-1=15811388$
$\displaystyle b=\frac{10^{15}}{4}-a^2=9513456$
$NB=249999990486544090505845063936$
+++++++++++++++++++++++++++++++++++++++++++
Procederò editando questo post in caso di novità
