Fibonacci-tall og fraktaler

Leseren har kanskje hørt om Fibonacci-rekken. Det er en spesiell tallrekke som vokser veldig raskt. Regelen er enkel: vi må starte med to tall, 1 og 1. Så får vi neste tall i rekka ved å summere to to forrige. Så vi får 1+1=2. Dermed har vi 1,1,2. Så får vi neste ved å regne ut 1+2=3. Så vi har 1,1,2,3. Og så videre: 1,1,2,3,5,8,13,21,34,55,89,…

Det er lett å skrive et lite Python-skript som regner ut, si, de 200 første Fibonacci-tallene.

fiblist = [1,1]
n = 100
i = 2
while i != n:
 fiblist += [fiblist[i-1]+fiblist[i-2]]
 i += 1

Vi lager altså en liste på to elementer, og så lager vi en while-løkke hvor vi regner ut neste Fibonacci-tall ved hjelp av de to forrige. Resultatet ser omtrent slik ut (skroll til høyre for å se alle):

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738L, 19740274219868223167L, 31940434634990099905L, 51680708854858323072L, 83621143489848422977L, 135301852344706746049L, 218922995834555169026L, 354224848179261915075L, 573147844013817084101L]

Som vi ser, blir tallene fort utrolig store. Det er faktisk en nøyaktig formel for Fibonacci-tallene. La \varphi = \frac{1+\sqrt 5}{2} være “det gylne snitt”. Da viser det seg at det n’te Fibonacci-tallet er gitt ved

F_n = \frac{\varphi^n - (-\varphi)^n}{\sqrt 5}

Formelen ble bevist av de Moivre på 1700-tallet en gang. Vi skal ikke ha bruk for den. Vi skal nemlig snakke om et morsomt resultat av Zeckendorf: det sier at ethvert positivt tall kan skrives som en sum av forskjellige Fibonacci-tall. Dette er unikt om vi krever at vi ikke tillater etterfølgende Fibonacci-tall i summen. Hva betyr dette?

Jo, 1 er et Fibonacci-tall, og det er 2 også, så det er en “liten” sum. Det første ikke-Fibonacci-tallet er 4, som kan skrives 1+3. Neste tall er 5, som er et Fibonacci-tall. Neste igjen er 6, som kan skrives 6=1+5. Og 7=5+2. Og 9=1+8. 10=8+2. 11=8+3.

Så skjer det noe morsomt! Hittil har alle tallene kunne skrives med kun to Fibonacci-tall. Men dette går ikke når vi prøver med 12! Men vi kan skrive 12=8+3+1, som er en sum av 3 Fibonacci-tall. Det neste tallet som vi trenger 3 Fibonacci-tall for å skrive er 18, som kan skrives 18=13+1+5.

Ok, nå har vi lært dette. Så vi har lyst å skrive et program som skriver naturlige tall som summer av Fibonacci-tall. Det er flere måter å gjøre dette på, og min er sikkert ikke den mest effektive – kan du programmere, så kom gjerne med raskere forslag.

Det første jeg gjør, er å lage en liste over de 2000 første Fibonacci-tallene ved måten over. En måte å skrive et tall som en sum av andre Fibonacci-tall er “slags rekursivt”. Du finner det største Fibonacci-tallet som er lavere enn tallet du jobber med. Og så trekker du det fra. Da er oppgaven redusert til å skrive et lavere tall som sum av to Fibonacci-tall. Og slik jobber du deg bakover:

def fibrep(N):
 if N in fiblist:
   return [N]
 else:
   largest = 1
   for n in fiblist:
     if n >  N:
       break
     largest = n
   return fibrep(N-largest) + [largest]

Tester man dette, ser man dette går overraskende raskt (til tross for rekursjonen!). Faktisk vil denne koden også gi en såkalt Zeckendorf-representasjon av tallet N. Dette betyr at svaret vi får er den unike måten å skrive N på som sum av forskjellige, ikke etterfølgende Fibonacci-tall (et kort bevis på hvorfor: anta først at vi får ut en liste med to like Fibonacci-tall (f.eks 10=5+5). Dette kan ikke skje, fordi 5 er et Fibonacci-tall, og da vil koden terminere på den første av dem. Anta så at vi får to etterfølgende Fibonacci-tall: f.eks 21=13+8. Men da er 21 selv Fibonacci-tall, så koden terminerer allerede da)

Her er for eksempel Zeckendorf-representasjonen av de 100 første naturlige tallene:

[[1], [2], [3], [1, 3], [5], [1, 5], [2, 5], [8], [1, 8], [2, 8], [3, 8], [1, 3, 8], [13], [1, 13], [2, 13], [3, 13], [1, 3, 13], [5, 13], [1, 5, 13], [2, 5, 13], [21], [1, 21], [2, 21], [3, 21], [1, 3, 21], [5, 21], [1, 5, 21], [2, 5, 21], [8, 21], [1, 8, 21], [2, 8, 21], [3, 8, 21], [1, 3, 8, 21], [34], [1, 34], [2, 34], [3, 34], [1, 3, 34], [5, 34], [1, 5, 34], [2, 5, 34], [8, 34], [1, 8, 34], [2, 8, 34], [3, 8, 34], [1, 3, 8, 34], [13, 34], [1, 13, 34], [2, 13, 34], [3, 13, 34], [1, 3, 13, 34], [5, 13, 34], [1, 5, 13, 34], [2, 5, 13, 34], [55], [1, 55], [2, 55], [3, 55], [1, 3, 55], [5, 55], [1, 5, 55], [2, 5, 55], [8, 55], [1, 8, 55], [2, 8, 55], [3, 8, 55], [1, 3, 8, 55], [13, 55], [1, 13, 55], [2, 13, 55], [3, 13, 55], [1, 3, 13, 55], [5, 13, 55], [1, 5, 13, 55], [2, 5, 13, 55], [21, 55], [1, 21, 55], [2, 21, 55], [3, 21, 55], [1, 3, 21, 55], [5, 21, 55], [1, 5, 21, 55], [2, 5, 21, 55], [8, 21, 55], [1, 8, 21, 55], [2, 8, 21, 55], [3, 8, 21, 55], [1, 3, 8, 21, 55], [89], [1, 89], [2, 89], [3, 89], [1, 3, 89], [5, 89], [1, 5, 89], [2, 5, 89], [8, 89], [1, 8, 89], [2, 8, 89]]

(skroll for å se alle) Vi ser nå at noen tall krever 4 Fibonacci-tall, for eksempel 33=1+3+8+21. Andre krever enda flere. Så vi kan spørre oss, hvis vi plotter naturlige tall mot lengden på en Zeckendorf-representasjon av dem, hvordan vil denne grafen se ut? Vi ser allerede at for de 11 første tallene er den konstant lik 2 (bortsett fra på Fibonacci-tallene hvor den er lik 1).

La oss se hvordan dette ser ut for de 200 første naturlige tallene:

Plot of the 200 first natural numbers versus the length of their Zeckendorf representation.
Plott av de 200 første naturlige tallene mot lengden på deres Zeckendorf-representasjon.

Vi ser et slags mønster, men det er ikke helt klart hva som skjer. La oss plotte de 1000 første også:

De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.
De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.

Hmhm. Mønsteret er ennå litt tydeligere! La oss prøve med de 10.000 første naturlige tallene!

De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.
De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.

Dette er morsomt! Nå ser vi helt tydelig et mønster. Det er til og med noe fraktal-lignenden over det. På den nederste “linjen” ser vi tall som har lengde 1 Zeckendorf-representasjon. Dette er Fibonacci-tallene. På linje 2 er det de som har lengde 2, og så videre. Det vi ser er at disse tynnes ut når vi nærmer oss neste Fibonacci-tall, og sånn er det på hver linje.

Nå kan vi spørre oss hvor raskt denne funksjonen vokser, hvor regulær den er, og så videre! Men det får vente til en anne bloggpost…

Legg igjen en kommentar