Wer hat Zeit - Collatz-Vermutung?

[AccountPasswort]

Eigentlich egal welchen Code man nimmt.

Die Collatz Vermutung ist eines von vielen ungelösten mathematischen Problemen. Gibts seit ca. 80 Jahren.

Wie würde denn der Code aussehen?
Wie kann er optimiert werden, vor allem weil viele Zahlen bei schon bekannten Zahlen einer Rechnung auftauchen (Schleife)?
Wie errechnet man die Rechendauer für ab 15-stelligen Zahlen?

Collatz-Vermutung kennt ja jeder oder?

Jede Zahl n die mit folgender Regel behandelt wird endet immer auf 1. Oder etwas mehr präzise:

Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1, egal, mit welcher natürlichen Zahl man beginnt.

Beeindruckend dabei sind die Anzahl der Schritte von n bis 1. Die sollten ggf. auch gezählt werden. Und welche Zahlen das nicht tun, das wäre der Jackpot. Bisher hat man keine gefunden. "Wir" bzw. Großrechner sind bei Nummer 27 Billion.

nzz.ch - Geschichte:
https://www.nzz.ch/article8BTQT-1.425865

Die Regel lautet:
- ist n gerade (even) teilt man durch 2
- ist n ungerade (odd) gilt 3*n+1

Alle ungeraden werden mit der 2. Regel (3*n+1) gerade, kann man also gleich durch 2 teilen.
Ist nicht schwer aber schaun wir mal oder? Oder nicht?

Bsp:

7 (odd)
3*7+1 = 22 (even)
22/2 = 11 (odd)
3*11+1 = 34 (even)
34/2 = 17 (odd)
3*17 +1 = 52 (even)
52/2 = 26 (even)
26/2 = 13 (odd)
3*13+1 = 40 (even)
40/2 = 20 (even)
20/2 = 10 (even)
10/2 = 5 (odd)
3*5+1 = 16 (even)
16/2 = 8 (even)
8/2 = 4 (even)
4/2 = 2 (even)
2/2 = 1

Tip: Jede Zahl von einem Ergebnis geht den gleichen Weg abwärts zu 1. Wenn man also dort Schleifen reinprogrammiert, dürfte es schneller gehen.

Natürlich ist das nur was für Rechner die mit 15-stelligen Zahlen gut umgehen können. Bis 27 Billiarden hat man bisher keine Folge gefunden die nicht auf 4,2,1 endet.

Viel Spaß.

Code by: https://stackoverflow.com/users/566644/lauritz-v-thaulow

def collatz_sequence(x):
    seq = [x]
    if x < 1:
       return []
    while x > 1:
       if x % 2 == 0:
         x = x / 2
       else:
         x = 3 * x + 1
       seq.append(x)    # Added line
    return seq

~/tmp$ python collatz.py
[6, 3, 10, 5, 16, 8, 4, 2, 1]

 

[Burki73]

Gibt es da nicht ein BOINC Projekt, wo jeder mitmachen also mitrechen kann? Collatz@Home oder so in etwa. Damit möchte ich nur erwähnen, das es schon Versuche gibt, das Problem zu lösen und nicht einer, sondern indem viele dort von Zuhause mit ihrern Rechnern mitrechnen. Ist leider etwas in Vergessenheit geraten, solche Projekte. Aber es gibt Sie und eine Vielzahl anderer, oft von Universitäten oder anderen Einrichtungen durchgeführt.

 

[Axxid]

Es ist ja schon etwas positives, wenn man sich mit solchen Dingen beschaeftigt. Ist ja auch eine schoene Uebung fuer Programmieranfaenger. Aber manchmal frage ich mich warum man dafuer Rechenpower verschwendet. Wobei ich nicht einschaetzen kann, wie lange man fuer 27 Billionen Versuche braucht.
Sollte man eine mathematische Vermutung nicht theoretisch beweisen/wiederlegen?

 

[Raybeez]

Sollte man eine mathematische Vermutung nicht theoretisch beweisen/wiederlegen?

So grundsätzlich nicht, nein. Zum widerlegen einer Behauptung reicht es oft, ein Gegenbeispiel zu finden.


Aber der TE liegt mit seinen 27 Billiarden deutlich daneben. Die bereits überprüften Zahlen liegen viele Größenordnungen dadrüber.

 

[NobodysFool]

Gibt es da nicht ein BOINC Projekt, wo jeder mitmachen also mitrechen kann? ............. Ist leider etwas in Vergessenheit geraten, solche Projekte.

In Vergessenheit geraten ist das sicher nicht, gerade heutzutage mit mehreren Kernen hat man die Rechenpower für sowas. Ich habe früher viele Projekte bei BOINC gerechnet, und war im RAC-Durchschnitt (aufgewendete Rechenzeit) mal sogar unter dem ersten Prozent weltweit. Nur ... gerade wenn man dann mehrere PCs für sowas verwendet bringen einen die Stromkosten mittlerweile um.

 

[SoDaTierchen]

Dein Text ist sehr wirr geschrieben. Mal Theorie, Mal Polemik, und alles Querbeet. Worauf willst du hinaus?

Grundsätzlich keine verkehrte Idee, die Collatz-Vermutung Mal Leuten zu zeigen, die diese vorher noch nicht kannten.

Deine Kernvermutung ist wohl, dass es stimmen muss, weil ja jede Zahl nach der Operation 3n+1 automatisch gerade wird. Das Problem: die dann geteilte Zahl muss nicht wieder gerade sein und ist mit 1,5*n+0,5 größer als die vorherige. Auch wenn das nicht der Fall ist, KÖNNTE es damit eine Folge geben, die einfach immer größer wird, weil sich gerade und ungerade abwechseln.

Das große Problem bei der Beweisführung: für einen Beweis braucht es eine mathematische Regel, die jeder beliebigen Zahl eine terminierende Collatz-Folge bescheinigt. Für den Gegenbeweis reicht ein einziges Gegenbeispiel. Da der Beweis (noch) nicht erbracht werden konnte, suchen sie Leute wie wild ein Gegenbeispiel.

Grundsätzlich ein mathematisch spannendes Thema, aber nochmal meine Frage: worauf willst du hinaus?

 

[Postman]

Wer so etwas um 1 Uhr nachts schreibt braucht dringenst eine große Liebe

 

[Innensechskant]

@Postman hat man doch, wenn man sich um diese Uhrzeit mit dieser Thematik beschäftigt. „Liebe“ muss ja nicht zwingend körperlicher Natur sein? Das nennt man dann Hobby

 

[Aeropony]

Wahrscheinlich sind das hier die Fragen seiner Hausaufgaben:

Wie würde denn der Code aussehen?
Wie kann er optimiert werden, vor allem weil viele Zahlen bei schon bekannten Zahlen einer Rechnung auftauchen (Schleife)?
Wie errechnet man die Rechendauer für ab 15-stelligen Zahlen?