Autor Beitrag
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2608
Erhaltene Danke: 1386

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 23.10.16 11:29 
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 user profile iconGammatesters mp_arith verwendet. Das läuft auch perfekt, aber eben nicht schnell genug.
Der Algorithmus:
ausblenden Quelltext
1:
2:
3:
4:
Wiederhole
   Test auf gerade, dann halbieren
   andernfalls 3*a+1 mit Kontrolle auf neues Maximum und danach halbieren
Abbruch, wenn Zwischenwert < Startzahl
Sieht jemand eine elegante Verbesserungsmöglichkeit?

Beste Grüße
Mathematiker

Nachtrag: Das Thema hat sich erledigt und ich bin wieder einmal "deprimiert".
siehe www.ericr.nl/wondrous/pathrecs.html
Einloggen, um Attachments anzusehen!
_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4421
Erhaltene Danke: 902


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2608
Erhaltene Danke: 1386

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 23.10.16 14:31 
user profile iconRalf Jansen hat folgendes geschrieben Zum zitierten Posting springen:
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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 519
Erhaltene Danke: 212

W7
Delphi 6 pro
BeitragVerfasst: So 13.11.16 14:40 
Moin,
habe hier noch eine Quelle aus Hamburg: www.rzbt.haw-hamburg.../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

_________________
Fietes Gesetz: use your brain (THINK)

Für diesen Beitrag haben gedankt: Mathematiker
ssb-blume
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 362
Erhaltene Danke: 6

XP, W7, W8
Deutschland
BeitragVerfasst: 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

_________________
Brain: an apparatus with which we think we think.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1640
Erhaltene Danke: 234

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.
user profile iconMathematiker nutzt ja leider den einfachsten Ansatz.
Interessant wäre, wie haben "die" das gemacht haben.
So zum Beispiel:
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