Mathematiker - So 23.10.16 11:29
Titel: Collatz-Folge

---

Hallo,
ich beschäftige mich gerade wieder einmal mit der berühmten Collatz-Folge.
Das Startglied a(1) ist eine beliebige natürliche Zahl. Die folgenden Glieder der Zahlenfolge werden definiert mit
a(n+1) = a(n) / 2, falls a(n) gerade ist
a(n+1) = 3·a(n) + 1, falls a(n) ungerade ist
Wählt man ein beliebiges Anfangsglied, so endet die Folge stets periodisch auf 4, 2, 1. Gegenbeispiele kennt man nicht, aber auch keinen Beweis.

Bei meinem Problem geht es um das größte in den Berechnungen auftretende Glied. Gefunden habe ich bisher 7125 88512 27944 52160 bei der Startzahl 1410123943.
Zur Berechnung (beginnend bei 1) benötigt mein Programm gute 6 Minuten. Das müsste aber irgendwie schneller werden, sonst wird in vertretbarer Zeit wohl kein neuer "Rekord" gefunden.
Im Moment ist mein Computer nach 20 Minuten Rechnung bei der Startzahl 4,4 Milliarden.

Für das Programm habe ich Gammatesters mp_arith verwendet. Das läuft auch perfekt, aber eben nicht schnell genug.
Der Algorithmus:
Sieht jemand eine elegante Verbesserungsmöglichkeit?

Beste Grüße
Mathematiker

Nachtrag: Das Thema hat sich erledigt und ich bin wieder einmal "deprimiert".
siehe http://www.ericr.nl/wondrous/pathrecs.html

Ralf Jansen - So 23.10.16 14:15

---

Als Nichtmathematiker (ich meine nicht das ich nicht du bin auch wenn es stimmt ;) ) verstehe ich das Problem nicht ganz. Meine triviale, vermutlich auch naive, Lösung wäre die folge 4,2,1 einfach zu verlängern bis man ein sehr großen Startwert hat. Oder gilt das nicht? 2^128 oder 2^256 usw. wären doch wohl gültige Startwerte und sehr groß? Sie würden den ungeraden Fall nie benutzen aber nicht außerhalb der genannten Folgeregel liegen. Oder hast du eine Bedingung verschwiegen?

edit: ok zumindest dein Pseudocode definiert den Startwert als nicht Mitglied der Folge.

Mathematiker - So 23.10.16 14:31

---

Ralf Jansen hat folgendes geschrieben :

Meine triviale, vermutlich auch naive, Lösung wäre die folge 4,2,1 einfach zu verlängern bis man ein sehr großen Startwert hat. Oder gilt das nicht? 2^128 oder 2^256 usw. wären doch wohl gültige Startwerte und sehr groß?

Du hast recht. Allerdings wird nach dem jeweiligen ersten Auftreten eines neuen Maximums gesucht.
Die Folge beginnt mit

Zitat:

a ... neues Maximum 3 ... 16 7 ... 52 15 ... 160 27 ... 9232 255 ... 13120 447 ... 39364 639 ... 41524 703 ... 250504 1819 ... 1276936 4255 ... 6810136 4591 ... 8153620 9663 ... 27114424 20895 ... 50143264 26623 ... 106358020 31911 ... 121012864 60975 ... 593279152 77671 ... 1570824736 113383 ... 2482111348 138367 ... 2798323360 159487 ... 17202377752 270271 ... 24648077896 665215 ... 52483285312 704511 ... 56991483520 1042431 ... 90239155648 1212415 ... 139646736808 1441407 ... 151629574372 1875711 ... 155904349696 1988859 ... 156914378224 2643183 ... 190459818484 2684647 ... 352617812944 3041127 ... 622717901620 3873535 ... 858555169576 4637979 ... 1318802294932 5656191 ... 2412493616608 6416623 ... 4799996945368 6631675 ... 60342610919632 19638399 ... 306296925203752 38595583 ... 474637698851092 80049391 ... 2185143829170100 120080895 ... 3277901576118580 210964383 ... 6404797161121264 319804831 ... 1414236446719942480 1410123943 ... 7125885122794452160

Beste Grüße
Mathematiker

Fiete - So 13.11.16 14:40

---

Moin,
habe hier noch eine Quelle aus Hamburg: http://www.rzbt.haw-hamburg.de/dankert/spezmath/html/collatzproblem.html
Kommt ein bisschen spät, liegt an meinem Gedächtnis.
Das Problem hatte uns Prof. Collatz in einer Vorlesung 1970 kurz vorgestellt.
Gruß Fiete

ssb-blume - Di 29.11.16 16:36

---

hallo Mathematiker,

da kann man nur die Definition von Bertrand Russel angeben:

Die Mathematik kann man als eine Disziplin bezeichnen, in der wir niemals wissen, wovon wird reden, und auch nicht, ob das, was wir sagen, wahr ist.

Hansi

Horst_H - Di 29.11.16 21:19

---

Hallo,

wie konnte ich das übersehen? ;-)
Das dies schon bis mindestens 2^60 getestet ist, ist ja nicht nett oder deprimierend.
Mathematiker nutzt ja leider den einfachsten Ansatz.
Interessant wäre, wie haben "die" das gemacht haben.
So zum Beispiel:
http://www.ericr.nl/wondrous/techpage.html :nut: :nut: :nut:
und endlich mal etwas, wobei Assembler wirlich viel bringt.

Zitat:

Using assembly for the time critical parts rather than plain C accounts for a speed gain of up to 500%.

Gruß Horst