{"id":4586,"date":"2015-01-20T01:23:53","date_gmt":"2015-01-19T23:23:53","guid":{"rendered":"http:\/\/www.soeren-in-norwegen.net\/blog\/?p=4586"},"modified":"2014-10-03T13:37:22","modified_gmt":"2014-10-03T11:37:22","slug":"die-fibonaccifolge","status":"publish","type":"post","link":"http:\/\/www.soeren-in-norwegen.net\/blog\/2015\/01\/die-fibonaccifolge\/","title":{"rendered":"Die Fibonaccifolge – Nerd-Sniping"},"content":{"rendered":"

Parmanand Singh schreibt in der Historia Mathematica<\/a>, Volume 12, Issue 3, August 1985, Seiten 229\u2013244 in seinem Artikel „The so-called fibonacci numbers in ancient and medieval India<\/a>“ (Volltext scheint fuer die Allgemeinheit verfuegbar zu sein), dass bereits Virahanka<\/a>, Gopala und auch Hemachandra<\/a> vor Leonardo da Pisa<\/a> diese mathematische Folge von Zahlen und deren Bildungsgesetz angaben. Wohl auch in Europa<\/a> war die Folge in der Antike bereits Nikomachos von Gerasa<\/a> bekannt. Aber wie so oft, fallen Ruhm und Ehre wem anders zu, weil irgendwann mal irgendwer zu faul war ordentliche Literaturrecherche zu machen und hinterher will es wieder keiner gewesen sein und keiner gibt den Fehler zu und deswegen wird es bis heute nicht ordentlich gemacht. Aber letztlich ist’s ja doch auch nicht so richtig relevant, was fuer einen Namen das Kind traegt \u2026 wohohoho \u2026 DAS ist natuerlich eine ganz andere Diskussion im Zusammenhang mit wirklichen Kindern; aber darum soll es hier nicht gehen. Deswegen halte ich mich an diesen nach dem „filius Bonacii“ (Sohn des Bonacii) gegebenen Namen.<\/p>\n

Die\u00a0Fibonaccifolge ist eine so sch\u00f8n einfache Folge. Das naechste Element bildet sich aus der Summe der ersten beiden Elemente. Aus 1 und 1 mach 2. Aus 1 und 2 mach 3. Aus 2 und 3 mach 5. Aus 3 und 5 mach 8 usw. ad infinitum. Hier sind mal die ersten Glieder:<\/p>\n

1, 1, 2, 3, 5, 8, 13, 21, 33, 54, 87, 141, 228, 369, 597, 966, 1563 \u2026 \u2026 \u2026<\/p>\n

Diese Reihe waechst also relativ rasant.<\/p>\n

Die Zahlen alle hintereinandergeschrieben ergeben eine neue Zahl. Im obigen Beispiel waere das 11235813213354871412283695979661563. Bis zum 17. Element „bildet“ die Fibonaccifolge eine 35-stellige Zahl.<\/p>\n

Alles klar, alles einfach. Ich erzaehle das, um das anstehende Problem besser zu verdeutlichen.<\/p>\n

In kurz (und mathematisch nicht ganz sauber formuliert) beschaeftigte mich seit Jahren der Gedanke, ob alle Zahlen gleich haeufig in der Fibonaccifolge vorkommen.
\nOder anders: wie oft kommt mein Geburtsdatum in der Fibonaccifolge bis zur 100-millionsten Stelle vor und kommt jede andere achtstellige Zahl genauso haeufig vor.<\/p>\n

AHAHAHA! In der zweiten Formulierung steckt schon etwas korrektere Mathematik – die Haeufigkeit einer Zahl.
\nNatuerlich kommen nicht alle Zahlen gleich oft vor bis zu einer gegebenen Stelle der Folge.
\nZur Veranschaulichung denken wir uns 4-stellige Zahlen; bspw. die 1234 oder die 9999. Dann kann es natuerlich schon sein, dass die 1234 bis zu einer bestimmten Laenge der Folge exakt genau so oft drin ist, wie die 9999, oder die 8765. Aber von allen 4-stelligen Zahlen wird sicherlich die eine oder andere \u00f8fter oder weniger oft bis zu dieser Stelle der Folge drin sein.
\n„Genauso haeufig“ wuerde also auf die Frage hinaus laufen, ob das Vorkommen aller Zahlen bis zu einer gegebenen Laenge der Fibonaccifolge normalverteilt<\/a> ist.<\/p>\n

Und hier k\u00f8nnte ein richtiger Mathematiker mich verbessern. Zum Ersten gibt es es einen ganzen Haufen von Wahrscheinlichkeitsverteilungen<\/a>. Ich habe nicht die leiseste Ahnung, ob die Normalverteilung die Richtige ist (sein k\u00f8nnte). Bei der Wahl der Verteilung folgte ich dem Indifferenzprinzip<\/a> (und dem Einfachheits- bzw. Faulheitsprinzip: keine Ahnung haben = nimm das was du kennst).
\nZum Zweiten ist die Normalverteilung eine stetige Wahrscheinlichkeitsverteilung. Bei dem Problem handelt es sich aber um ein „diskretes Problem“. Ich sollte das also dahingehend umformulieren, ob sich das Vorkommen aller Zahlen einer Normalverteilung angleicht. Ich habe aber wiederum keinen blassen Schimmer inwiefern das gerechtfertigt ist (sein k\u00f8nnte).
\nDas erinnert mich etwas daran, dass ich erstmal zeigen sollte, dass es eine L\u00f8sung gibt bevor ich mich an das Berechnen dieser L\u00f8sung mache.<\/p>\n

Wieauchimmer, mich duenkt, dass dieses Problem mit dem Problem verwandt ist, ob eine Zahl normal<\/a> ist. Auch bei dieser Behauptung bleibe ich mir (und euch, meinen lieben Leserinnen und Lesern) den Beweis der Richtigkeit derselben schuldig.<\/p>\n

Im uebrigen ist das bei Pi (und anderen irrationalen Zahlen) eine offene Frage<\/a>. Bis zur 100-millionsten Stelle scheint es aber wohl ganz gut zu passen<\/a>.<\/p>\n

Das Problem laeszt sich also auf zwei einfache Probleme herunterbrechen:
\n1.: addiere zwei Zahlen nach einem bestimmten Schema und haenge die Summe an die Kette ran; brich ab, wenn die Kette eine bestimmte Laenge hat;
\n2.: zaehle wie oft gewisse Zahlen vorkommen.<\/p>\n

„Einfach“ in so fern, dass man sich das leicht vorstellen kann. Am Beispiel oben sieht man ja aber, wie rasant die einzelnen Elemente wachsen. Zur Addition wuerde ich also einen Computer empfehlen. Und eine Zahl mit 100 Millionen stellen zu untersuchen ist auch recht langwierig. Da der Computer ohnehin schon zur Hand ist, sollte der gleich auch zur Analyse benutzt werden. Schlieszlich handelt es sich um ein Zahlenverarbeitungsproblem. Dafuer wurden die Dinger schlieszlich erfunden.<\/p>\n

Eigentlich greife ich mit all diesen Ausfuehrungen schon viel zu weit vor. Ich war ja dabei, dass mir das Problem seit Jahren im Kopf rumspukte. Ich hatte aber nie die Musze, mich da mal naeher mit zu beschaeftigen. Wusste ich doch, dass ich dafuer zumindest rudimentaere Programmierkenntnisse haben muss.<\/p>\n

Dann aber geschah es, dass ich vor einiger Zeit bei einem Quiz dabei war. Ich will jetzt nicht sagen, dass ich „mitgeschleppt“ wurde. Ich bin da aus eigener Initiative mitgegangen. Aber mein Wissen zu norwegischen Gerichten, Werbespruechen oder anderen bei solchen Quiz‘ gefragten Sachen halten sich doch sehr in Grenzen.<\/p>\n

Ich hatte aber einen Stift in der Hand und eine Serviette vor mir liegen. Zunaechst malte ich nur die ueblichen Krusedull<\/a> (ein Wort, welches ich sehr sehr toll finde). Etwas im Geiste finge ich dann an, die ersten Elemente der Folge aufzuschreiben. Dann begann ich noch mehr Elemente\u00a0ordentlich auszurechnen. Ich schrieb die Folge bis zu einer gewissen Laenge auf (mich duenkt bis zur 39. Stelle oder so) und zaehlte, wie oft die Zahlen 0 bis 9 darin vorkamen. Dannn zeichnete ich ein Histogramm<\/a>.
\nUnd dann geschah das, was i.A. als Nerd-Sniping<\/a> bekannt ist. Ich fing an mir mit meinen (mittlerweile vorhandenen) rudimentaeren (wirklich nicht mehr!) Programmierkenntnissen Gedanken ueber eine Automatisierung des Ganzen zu machen. Nebenbei lief das Quiz natuerlich weiter und ich warf auch ab und zu mal ein Kommentar ein.<\/p>\n

Hier ist die Arbeit des beschriebenen Abends zu sehen:<\/p>\n

\"Fibonacci_Start\"<\/a><\/p>\n

Damit l\u00f8se ich natuerlich nicht das eigentliche mathematische Problem dahinter. Aber ich sage mal so. Wenn ich sehe, dass sich die Haeufigkeiten fuer bspw. alle vierstelligen Zahlen bis sagen wir zur 100-millionsten Stelle der Fibonaccifolge einer Normalverteilung genuegend angleichen, dann sehe ich das Problem fuer meine Beduerfnisse als gel\u00f8st an.<\/p>\n

Eine technische Sache noch an dieser Stelle. Bisher schrieb ich bspw. „4-stellige Zahlen“. Natuerlich sind damit 4-stellige Zeichenketten gemeint.
\n4-stellige Zahlen beginnen bei der 1000 und enden mit der 9999.
\nBei der „0007“ hingegen handelt es sich um eine 4-stellige Zeichenkette, auch wenn die Zahl selber einstellig – die Sieben eben – ist.
\nWenn man sich auf die Ziffern 0 bis 9 als Zeichen beschraenkt beginnen 4-stellige Zeichenketten bei der „0000“ und enden bei der „9999“. Man hat also insgesamt 10.000 verschiedene 4-stellige Zeichenketten.
\nIch entdeckte dieses Problem erst als ich schon „mittendrin“ war. Sicherlich auch dadurch bedingt, weil ich die ganze Zeit ja irgendwie mit Zahlen\u00a0 arbeite. Da musste ich durch „Fehler in den Resultaten“ erstmal auf den Unterschied zwischen Zahl und Zeichenkette gestoszen werden.<\/p>\n

Aber genug fuer heute.
\nDie naechsten Beitraege werden sich zunaechst dem „technischen Hintergrund“ widmen, bevor ich mich an die Dartellung der spannenden (und sch\u00f8nen) Ergebnisse mache.<\/p>\n","protected":false},"excerpt":{"rendered":"

Parmanand Singh schreibt in der Historia Mathematica, Volume 12, Issue 3, August 1985, Seiten 229\u2013244 in seinem Artikel „The so-called fibonacci numbers in ancient and medieval India“ (Volltext scheint fuer die Allgemeinheit verfuegbar zu sein), dass bereits Virahanka, Gopala und auch Hemachandra vor Leonardo da Pisa diese mathematische Folge von Zahlen und deren Bildungsgesetz angaben. […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/4586"}],"collection":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/comments?post=4586"}],"version-history":[{"count":3,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/4586\/revisions"}],"predecessor-version":[{"id":4588,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/posts\/4586\/revisions\/4588"}],"wp:attachment":[{"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/media?parent=4586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/categories?post=4586"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.soeren-in-norwegen.net\/blog\/wp-json\/wp\/v2\/tags?post=4586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}