Hányadik Fibonacci-számig kell elmenni, hogy "00"-tól "99"-ig mindenféle 2-számjegyű végződés szerepeljen?

A 297.-ig, és a 02. Legalábbis ha nem b*tam el ezt a kódot:

int main()

{int A[100], kesze = 100, n = 6, a = 5, b = 8, c, i;

for(i=0;i<100;i++) A[i] = 1;

while(kesze)

{c = (a + b)%1000; a = b; b = c; n++;

if(A[c%100]){kesze--; A[c%100] = 0;}}

printf("n=%d;\na=%d; b=%d.", n, a, b);

return 0;}

Az output:

n=297;

a=597; b=802.

Process returned 0 (0x0) execution time : 0.072 s

A 100-as Pisano periódus 300, abban még szemmel is meg lehet találni, amit keresel. Programmal még biztosabb.

Ez az első 300 Fibonacci szám mod 100:

0,1,1,2,3,5,8,13,21,34,55,89,44,33,77,10,87,97,84,81,65,46,11,57,68,25,93,18,11,29,40,69,9,78,87,65,52,17,69,86,55,41,96,37,33,70,3,73,76,49,25,74,99,73,72,45,17,62,79,41,20,61,81,42,23,65,88,53,41,94,35,29,64,93,57,50,7,57,64,21,85,6,91,97,88,85,73,58,31,89,20,9,29,38,67,5,72,77,49,26,75,1,76,77,53,30,83,13,96,9,5,14,19,33,52,85,37,22,59,81,40,21,61,82,43,25,68,93,61,54,15,69,84,53,37,90,27,17,44,61,5,66,71,37,8,45,53,98,51,49,0,49,49,98,47,45,92,37,29,66,95,61,56,17,73,90,63,53,16,69,85,54,39,93,32,25,57,82,39,21,60,81,41,22,63,85,48,33,81,14,95,9,4,13,17,30,47,77,24,1,25,26,51,77,28,5,33,38,71,9,80,89,69,58,27,85,12,97,9,6,15,21,36,57,93,50,43,93,36,29,65,94,59,53,12,65,77,42,19,61,80,41,21,62,83,45,28,73,1,74,75,49,24,73,97,70,67,37,4,41,45,86,31,17,48,65,13,78,91,69,60,29,89,18,7,25,32,57,89,46,35,81,16,97,13,10,23,33,56,89,45,34,79,13,92,5,97,2,99,1

utána ugyanezek ismétlődnek, hisz ez a teljes periódus.

(Ezzel számoltattam ki:

[link]

Első ránézésre a 12 az utolsó.

...Másodikra mégsem a 12, hanem a 36.

... És az bizonyult a végleges tippnek is.

Azt már nem számolom össze, hogy ez hanyadik :)

jujj, nem hagytam ki az első hét egyjegyű számot...

brrr

Igen, én is éppen azt néztem…

Talán így átláthatóbb lesz:

00; 01; 01; 02; 03; 05; 08; 13; 21; 34; 55; 89; 44; 33; 77;

10; 87; 97; 84; 81; 65; 46; 11; 57; 68; 25; 93; 18; 11; 29;

40; 69; 09; 78; 87; 65; 52; 17; 69; 86; 55; 41; 96; 37; 33;

70; 03; 73; 76; 49; 25; 74; 99; 73; 72; 45; 17; 62; 79; 41;

20; 61; 81; 42; 23; 65; 88; 53; 41; 94; 35; 29; 64; 93; 57;

50; 07; 57; 64; 21; 85; 06; 91; 97; 88; 85; 73; 58; 31; 89;

20; 09; 29; 38; 67; 05; 72; 77; 49; 26; 75; 01; 76; 77; 53;

30; 83; 13; 96; 09; 05; 14; 19; 33; 52; 85; 37; 22; 59; 81;

40; 21; 61; 82; 43; 25; 68; 93; 61; 54; 15; 69; 84; 53; 37;

90; 27; 17; 44; 61; 05; 66; 71; 37; 08; 45; 53; 98; 51; 49;

00; 49; 49; 98; 47; 45; 92; 37; 29; 66; 95; 61; 56; 17; 73;

90; 63; 53; 16; 69; 85; 54; 39; 93; 32; 25; 57; 82; 39; 21;

60; 81; 41; 22; 63; 85; 48; 33; 81; 14; 95; 09; 04; 13; 17;

30; 47; 77; 24; 01; 25; 26; 51; 77; 28; 05; 33; 38; 71; 09;

80; 89; 69; 58; 27; 85; 12; 97; 09; 06; 15; 21; 36; 57; 93;

50; 43; 93; 36; 29; 65; 94; 59; 53; 12; 65; 77; 42; 19; 61;

80; 41; 21; 62; 83; 45; 28; 73; 01; 74; 75; 49; 24; 73; 97;

70; 67; 37; 04; 41; 45; 86; 31; 17; 48; 65; 13; 78; 91; 69;

60; 29; 89; 18; 07; 25; 32; 57; 89; 46; 35; 81; 16; 97; 13;

10; 23; 33; 56; 89; 45; 34; 79; 13; 92; 05; 97; 02; 99; 01;

Ha a 02-re rákerestek Ctrl+F-fel, akkor látjátok, hogy csak a 3. és a 297. helyen van. Ha pedig a 99-et és a 01-et megnézitek, az előfordul a 7. és a 297. hely között is. (Ugye az utolsó elem a 300. a ciklusban, viszont a kezdő 00 a Fibonacci-sor 0. eleme.)

Ha nem b*tam el ezt a kódot, akkor nem fordul elő az összes 3-jegyű szám maradékként. Ugye két egyforma szomszédos elem után mindig ugyanolyan harmadik jön, ezért a ciklus legfeljebb 1000*1000 hosszú lehet.

int main()

{int A[1000], kesze = 1000, n = 1, a = 0, b = 1, c;

for(c=0;c<1000;c++) A[c] = 1;

while(kesze)

{c = (a + b)%1000; a = b; b = c; n++;

if(A[c%1000]){kesze--; A[c%1000] = 0;}

if(n > 1e7) kesze=0;} //hogy ne legyen vegtelen ciklus

printf("\nn=%d;\na=%d; b=%d.\n", n, a, b);

n = 0;

for(c=0;c<1000;c++)

{if(A[c])

{printf("%3d; ",c); n++;

if(!(n%10))printf("\n");}}

printf("A fenti %d darab maradek nem fordul elo.",n);

return 0;}

Az output:

n=10000001;

a=875; b=501.

4; 6; 12; 14; 20; 22; 28; 30; 36; 38;

44; 46; 52; 54; 60; 62; 68; 70; 76; 78;

84; 86; 92; 94; 100; 102; 108; 110; 116; 118;

124; 126; 132; 134; 140; 142; 148; 150; 156; 158;

164; 166; 172; 174; 180; 182; 188; 190; 196; 198;

204; 206; 212; 214; 220; 222; 228; 230; 236; 238;

244; 246; 252; 254; 260; 262; 268; 270; 276; 278;

284; 286; 292; 294; 300; 302; 308; 310; 316; 318;

324; 326; 332; 334; 340; 342; 348; 350; 356; 358;

364; 366; 372; 374; 380; 382; 388; 390; 396; 398;

404; 406; 412; 414; 420; 422; 428; 430; 436; 438;

444; 446; 452; 454; 460; 462; 468; 470; 476; 478;

484; 486; 492; 494; 500; 502; 508; 510; 516; 518;

524; 526; 532; 534; 540; 542; 548; 550; 556; 558;

564; 566; 572; 574; 580; 582; 588; 590; 596; 598;

604; 606; 612; 614; 620; 622; 628; 630; 636; 638;

644; 646; 652; 654; 660; 662; 668; 670; 676; 678;

684; 686; 692; 694; 700; 702; 708; 710; 716; 718;

724; 726; 732; 734; 740; 742; 748; 750; 756; 758;

764; 766; 772; 774; 780; 782; 788; 790; 796; 798;

804; 806; 812; 814; 820; 822; 828; 830; 836; 838;

844; 846; 852; 854; 860; 862; 868; 870; 876; 878;

884; 886; 892; 894; 900; 902; 908; 910; 916; 918;

924; 926; 932; 934; 940; 942; 948; 950; 956; 958;

964; 966; 972; 974; 980; 982; 988; 990; 996; 998;

A fenti 250 darab maradek nem fordul elo.

Process returned 0 (0x0) execution time : 0.337 s

Ami azt pont azt jelenti, hogy semelyik Fibonacci-szám nem adhat 4 vagy 6 maradékot 8-cal osztva. És ezt belátni is könnyű, csak fel kell írni az első néhány Fibonacci-szám 8-as maradékát (ehhez program sem kell):

1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0; 1, 1, 2, 3,…