| Autor |
Beitrag |
    
Kay Schönberger (Kay_S)
| | Veröffentlicht am Freitag, den 21. Dezember, 2001 - 20:52: | 
|
Gegeben sei die folgende rekursiv definierte Zahlenfolge F(n):
F1 = 7
und
Fn+1 = ½ * Fn , falls Fn gerade
Fn+1 = ½ * ( 5*Fn + 1 ) , falls Fn ungerade.
Gibt es nun eine Möglichkeit, die Divergenz von F(n) zu zeigen (d. h. wächst F(n) über jede Schranke)?
Ich hab' es mit Restklassen versucht, das Problem ist jedoch, daß in der Folge durchaus eine Periode auftreten kann (so z.B. für F(1) <= 6).
Des weiteren würde mich interessieren, ob man F(n) in Abhängigkeit von n abschätzen kann.
Möglicherweise könnte man daraus eine explizite Bildungsvorschrift für F(n) finden.
Wäre für jeden Ansatz sehr dankbar.
Kay S. |
Rudolf
| | Veröffentlicht am Mittwoch, den 26. Dezember, 2001 - 11:26: |
|
Hi Kay!
Kennst du die Folge:
F1 = a aus N
Fn+1 = Fn/2 falls Fn gerade,
Fn+1 = (3Fn+1)/2 falls Fn ungerade.
Das ist die berühmte Collatz-Folge und es wird vermutet, dass die Folge für jedes beliebige a als Anfangswert in die Schleife 1,2,1,2,...mündet. Bewiesen hat das noch niemand.
Dein Problem scheint ebenfalls allgemein nicht beweisbar zu sein. Willst du es aber nur für den Fall F1 = 7 beweisen, dann hast du doch die Möglichkeit die Folgenglieder einfach mit einen Computerprogramm auszurechnen und das Programm abzubrechen, sobald du in einer Schleife landest.
Sollte das Programm nicht in einer gewissen Zeit abbrechen, dann allerdings müßtest du entweder einen allgemeinen Beweis für die Divergenz der Folge (ohne Schleifenbildung) finden, und das scheint keinesfalls einfach zu sein, oder eben weiter warten, ob die Folge nicht doch in einer Schleife mündet.
Eine Idee:
Die Schleife könnte 1,3,16,8,4,2,1,3,16,...sein.
Versuche vielleicht einmal einen Baum zu entwickeln, indem du die Bildungsvorschrift in umgekehrter Richtung anwendest und sieh nach, ob 7 vorkommt. Bleibt noch die Frage offen, ob das die einzig mögliche Schleife ist?
Gruß, Rudolf |
Kay Schönberger (Kay_S)
| | Veröffentlicht am Samstag, den 29. Dezember, 2001 - 21:52: |
|
Hallo Rudolf!
Das Collatz-Problem war mir natürlich bekannt. Aber das es eventuell unmöglich ist, bei nur einem einzigen Startwert etwas über die Divergenz zu sagen, scheint mir doch merkwürdig zu sein.
Die Hoffnung, der Computer könnte weiterhelfen, hat sich leider getäuscht - keine Spur von einer Periode. Stattdessen wachsen die Folgenglieder munter bis in jede beliebige Höhe (wahrscheinlich exponentiell). Einige Zwischenergebnisse:
F1 = 7
F10 = 229
F100 = 26329873
F1000 = 13714014611597919613981896480457178197406407498
F10000 ~ 8,949·10468
F100000 ~ 2,153·104673
Aber offensichtlich kann man wenigstens etwas über das Wachstum sagen. Scheinbar gilt die Näherung Fn ~ 100,0467·n. Wie man darauf kommen könnte, weiß ich allerdings nicht. Ich denke, je größer die Folgenglieder werden, desto geringer wird die Wahrscheinlichkeit, daß doch noch eine Periode auftritt.
Hat jemand noch eine Idee?
Kay S. |
|
