Mathematik: Collatz-Folge

[Mike]

Hi,
nur mal aus Neugier und aktuellem Anlass, denn ich weiss es gibt hier viele Mathebegeisterte.

Ich bin ein Laie auf dem Gebiet, auch wenn es mich oft fasziniert. Nun mal zu dieser Collatz-Folge; Da denkt sich dieser Lothar Collatz ein Zahlenrätsel aus und die Elite versucht dieses zu enträtseln. Was mich dabi wundert ist nur, was soll das? Gerade Zahlen halbieren, falls ungerade x3+1.

Warum macht er bei ungeraden nicht einfach +1 um wieder die Geraden-Regel anzuwenden? Oder warum nicht Ungerade mal 7(oder sonstwas passendes)+1? Was soll also an diesem mal 3 so besonders sein?

Also aus Laiensicht ist das Interesse für mich an so einem simplen Zahlenspiel nicht verständlich.

Mike

[herrmann]

Was genau den Mathematiker Collatz bewog, seine in der Wirkung ziemlich chaotische Bildungsregel aufzustellen, ist mir nicht bekannt. Aber seit Gödel nachgewiesen hat, dass es in jeder formal durchgebildeten mathematischen Theorie Aussagen gibt, deren Richtigkeit oder Falschheit sich innerhalb dieser Theorie nicht entscheiden lässt, suchen Mathematiker nach Beispielen für dieses Phänomen.

Bisher war neben der Goldbach-Vermutung auch die Collatz-Vermutung ein ganz hoffnungsvoller Kandidat für diese Rolle. Die dauernden Versuche, sie zu beweisen oder zu wiederlegen, dienen dem Zweck, nachzuweisen, dass die Collatz-Vermutung sehr wohl entscheidbar ist. (Ihre Nicht-Entscheidbarkeit nachzuweisen, gibt es bislang eh' keinen versprechenden Weg.)

Außerdem gilt hier vielleicht auch die Antwort, die ein Bergsteiger auf die Frage gab, warum er er denn unbedingt diesen speziellen Berg bezwingen müsse: "Weil er da ist."

H.

[Der Martin]

Hallo,

Außerdem gilt hier vielleicht auch die Antwort, die ein Bergsteiger auf die Frage gab, warum er er denn unbedingt diesen speziellen Berg bezwingen müsse: "Weil er da ist."

eine Einstellung, die ich noch nie nachempfinden konnte. Normalerweise möchte ich ein bestimmtes Ziel erreichen, und nehme die Hindernisse auf dem Weg dorthin (miss)billigend in Kauf, versuche aber, sie mit geringstmöglichem Aufwand zu überwinden - oder ganz zu umgehen.
Oder ich stelle für mich fest, dass der Aufwand nicht in einem angemessenen Verhältnis zum vorgesehenen Ziel steht, und lass es dann bleiben.

Eine Herausforderung nur um ihrer selbst willen? Ohne mich ...

Ciao,
 Martin

[Gunnar Bittersmann]

@@Mike:

nuqneH

Warum macht er bei ungeraden nicht einfach +1 um wieder die Geraden-Regel anzuwenden?

Kann man machen:

[latex]a_n = \begin{cases}a_{n-1}/2,  & \text{wenn }a_{n-1}\text{ gerade,}\a_{n-1}+1, & \text{wenn }a_{n-1}\text{ ungerade.}\end{cases}[/latex]

Allerdings ist der Beweis, dass man nach endlich vielen Schritten immer 1 rauskommt, dann aber recht einfach. Mit vollständiger Induktion:

Induktionsanfang: Der Algorithmus kommt für die Startwerte a₀ = 1 und a₀ = 2, a₁ = 2/2 = 1 bei 1 an.

Induktionsschritt: Unter der Annahme, dass der Algorithmus für alle Startwerte a₀ < 2k - 1 bei 1 ankommt, ist zu zeigen, dass er das auch für a₀ = 2k - 1 und a₀ = 2k tut. (k ∈ ℕ, k ≥ 2)

Beweis für a₀ = 2k: a₁ = 2k/2 = k. Da k < 2k - 1, kommt der Algorithmus laut Induktionsvoraussetzung bei 1 an.

Beweis für a₀ = 2k - 1: a₁ = a₀ + 1 = 2k. Dass der Algorithmus dann bei 1 ankommt, wurde eben gezeigt.

Qapla'

[Jens Holzkämper]

Tach,

Warum macht er bei ungeraden nicht einfach +1 um wieder die Geraden-Regel anzuwenden?

diese Folge würde immer gegen 1 konvergieren und wäre somit kein spannendes Problem.

Oder warum nicht Ungerade mal 7(oder sonstwas passendes)+1?

Ich vermute mal, die Folge ist ihm irgendwo über den Weg gelaufen und er fand den im Prinzip nicht vorhersehbaren Verlauf spannend, man würde ja erstmal erwarten, dass verschiedene Schleifen möglich sind.

Dein Beispiel mit 7x+1 führt schon mit kleinen Ausgangswerten schnell zu Zahlen, die man nicht mehr so eben im Kopf berechnen möchte:
10,5,36,18,9,64,32,16,8,4,2,1 sieht ja erstmal gut aus, aber
3,22,11,78,39,274,137,960,480,240,120,60,30,15,106,53,372,186,93,652,326,163,1142,571,3998,1999,13994,6997,48980,24490,12245,85716,42858,21429,150004,75002,37501,262508,131254,65627,459390,229695,1607866,803933,5627532,2813766,1406883,9848182,4924091,34468638,17234319,120640234,60320117,422240820,211120410,105560205,738921436,369460718,184730359,1293112514,646556257,230926504,115463252,57731626,28865813,202060692,101030346,50515173,353606212,176803106,88401553,618810872,309405436,154702718,77351359,541459514,270729757,1895108300,947554150,473777075, (hier Abbruch wegen int-Überlauf)
oder 7,50,25,176,88,44,22 (ab hier siehe oben)

Was soll also an diesem mal 3 so besonders sein?

Andere Multiplikatoren erzeugen halt einfach weniger spannende Ergebnisse, die 3 erzeugt soweit ersichtlich weder Schleifen noch explosives Wachstum

Also aus Laiensicht ist das Interesse für mich an so einem simplen Zahlenspiel nicht verständlich.

Nicht? Mit sowas kann man sich z.B. wunderbar im Unterricht/Vorträgen/Sitzungen…, die Zeit vertreiben, wenn es mal wieder langweilig ist. Und die Mathematik, die dann hinter der Lösung eines dermaßen trivial erscheinenden Problems steckt, ist immer wieder spannend kompliziert.

mfg
Woodfighter

[Gunnar Bittersmann]

@@Jens Holzkämper:

nuqneH

(hier Abbruch wegen int-Überlauf)

Überlauf? 32-Bit-System oder hast du dich da verrechnet?

Allerdings bricht der Algorithmus auch nach einer Million Durchläufe noch nicht ab.

Qapla'

[Jens Holzkämper]

Tach,

(hier Abbruch wegen int-Überlauf)

Überlauf? 32-Bit-System oder hast du dich da verrechnet?

64 Bit System, aber im Gegensatz zu anderen Sprachen kann man sich darauf verlassen, dass die Datentypen egal wo sie laufen, den selben Wertebereich haben: ein Java int hat immer 32 Bit. Da es mich wundern würde, wenn die Folge insgesamt wieder fallen würde, habe ich dann nicht auf einen beliebig groß werdenden Datentyp umgestellt.

mfg
Woodfighter