Az 73318332000987272. Fibonacci szám tényleg "123456789"-cel kezdődik és végződik?

miért ne lehetne? nem a első 20 számról van szó.

bizonyítsd be hogy miért ne lehetne,addig ne okoskodj.

szerintem esély van rá hogy pont ilyen szám legyen az előző 2szám összege. simán lehet írni egy programot ami egy for ciklussal i=73318332000987272-szor lefut és kiadja neked az eredményt, szeretnéd hogy elkészítsem?

Az a gond, hogy ugyan van formulánk az n. Fibonacci-szám kiszámolására – Binet-formula –, de az jellegében olyan, hogy nem igazán lehet logaritmizálni, így bajos lenne ekkora n-re kiszámolni csak úgy. Gondolom megfelelő szoftverrel azért nem lehetetlen.

Mindenesetre az utolsó számjegyeket gondolom maradéktételekkel meg lehet közelíteni. Pl. 10-es számrendszerben a Fibonacci-számok utolsó számjegyei 60-as periódust mutatnak, ergo a 73318332000987272. szám utolsó számjegye megegyezik a 73318332000987272 (mod 60) = 32. szám utolsó számjegyével. A 32. Fibonacci-szám könnyen meghatározható: 2178309. Ez 9-re végződik, tehát a 73318332000987272. Fibonacci-szám is biztosan 9-re végződik.

100-as maradékra a periódus 300, tehát a 73318332000987272. Fibonacci-szám ugyanarra végződik, mint a 73318332000987272 (mod 300) = 272. Fibonacci-szám, ami meg 312718191492907860985910767785256677811449301165198482789, ami valóban 89-re végződik.

Tehát eddig stimmel. Gondolom ezt tovább lehet számolgatni. Lásd: [link] . Ez alapján meg lehet határozni nagyobb modulo esetén is a periódust. 1000-re – forrás: [link] – a periódus 1500, tehát a 73318332000987272. Fibonacci-szám utolsó számjegye megegyezik a 73318332000987272 (mod 1500) = 272. szám utolsó számjegyével – ami történetesen ugyanaz, mint az előbb –, ami ugyancsak 789-re végződik.

Az első számjegyekre egyelőre nincs sejtésem, hogy hogy lehetne kiszámolni egyszerűen. Elvileg a Binet-formula így hangzik: F_n = [(1+√5)^n - (1-√5)^n] / (2^n*√5)

De hogy ezt nagyon nagy n-re hogy kellene kiszámolni egyszerűbben, azt passzolom. A számlálóban lévő különbség miatt logaritmust nem lehet belőle vonni.

A közelítést egy kicsit veszélyesnek érzem ilyen probléma esetén. Itt van egy esetleg használható állítás:

Egy pozitív x Fibonacci-szám akkor és csak akkor, ha vagy 5x^2+4 vagy 5x^2-4 teljes négyzet.

[link]

Alapötlet: Brute force.

Ha valakinek van egy jó gyors gépe, meg szívesen otthon hagyja néhány hónapra bekapcsolva, akkor például ezt a C programot kell lefuttatni:

int main()

{

long n=73318332000987272, c; /*64 bites rendszer alatt talán ez is mehet az int sorába.*/

int first=0, second=1, xt=1;

for (c=2;c<n+1;c++)

{ xt = (first + second)%1000000000;

first = second%1000000000;

second = xt%1000000000;

}

printf("%d\n",first);

printf("%d\n",second);

return 0;

}

Nekem n = 10^10-re nagyjából 400 másodpercig futott. (Ez azt jelenti, hogy nekem 90 év lenne ezzel az algoritmussal kiszámolni… Mondjuk még biztos lehet finomítani rajta.)