Adventskalender 4. Dezember 2022 - "Collätzchen" - Zahlenspielereien

[TuxPeter]

Hallo allerseits,
Auf die "Collätzchen" kam ich durch den Hinweis eines lieben Freundes, der, im Gegensatz zu mir, richtig was von Mathematik versteht und den solche Sachen wie Zahlentheorie faszinieren.

Mich hingegen hat die simple Möglichkeit, der einfache Algorithmus, gerade diese Reihen zu erzeugen, fasziniert:

Nimm eine beliebige natürliche Zahl (also positiv und ganzzahlig).
Wenn durch 2 teilbar, tue dies,
sonst multipliziere mit 3 und addiere 1.
Weiter so mit der neuen Zahl, bis Du bei 1 ankommst.
(Dann kommt nämlich die Endlosschleife 1-4-2-1 ...)

Sodann habe ich rund um dieses Schema mit Freepascal, mit Geaney als IDE, herumgespielt und die Ergebnisse mittels Gnuplot visualisiert und das Ganze mit dem Simple-Screen-Recorder aufgenommen. Was dabei herauskam, könnt Ihr im Filmchen betrachten. Er hat seine Längen, Sprünge und andere Fehler, aber - Mut zur Lücke - vielleicht ist er trotzdem interessant.

https://jodre.de/collaetzchen/

Dazu gibt es noch ein tar-Archiv mit den Pascal-Programmen. Hierzu folgendes vorweg: Diese Progs wurden als Einmal-, Test- und Spielprogramme geschrieben,
und verzichten weitgehend auf Plaus-Tests und auf eine Konfiguration mittels ext. Parameter.

In der vorliegenden Form schreiben die Programme
in das jeweils aktuelle Arbeitsverzeichnis.

Es ist sehr zu empfehlen, ein Verzeichnis, z.B. "Collatz" VORHER anzulegen
und in allen Programmen die folgende Konstante für die Bildung von Dateinamen
entsprechend anzupassen:

const loadpath = '/home/XX/Collatz/';

- - - an einigen Stellen ist das auch in nachfolgender Konstante enthalten:

const prefix = 'irgendwas';


Eine kleine Warnung bezüglich der Datenmengen: Es ist sehr leicht möglich,
bei entsprechenden Eingaben eine sehr große Anzahl von Dateien mit
entsprechenden Datenmengen zu erzeugen, die den Computer lahmlegen können.
Die kann man dann zwar ebenso leicht wieder löschen, wenn das System noch
reagiert, andernfalls: boote ein Life-System.

Zu den einzelnen Programmen:

collatz_einfachst.pas
// simpler geht's wohl nicht

collatz_einzeln.pas
// Zahl eingeben, Reihe auf dem Bildschirm

collatz_multi_rows.pas
// erzeugt mehrere Collatz-Reihen, generiert das gnuplot-Script und ruft es auch gleich auf. Mit dem Script kann weiter gespielt werden.

collatz_recur_up.pas
// Es wäre doch mal interessant, welche Reihen in einer vorgegebenen Zahl landen bzw. durch sie hindurchgehen auf ihrem Weg hin zur 1. Es muss also "aufwärts" gerechnet werden. Eine typisch recursive Aufgabe, mit einem vorgebenen Wert für die Anzahl der Rechenstufen zwecks Terminierung.
Das Programm läuft schon richtig, bringt die richtigen Werte, der Plot aber nicht.
Weil: Wenn das Prog von seinem rekursiven Ausflug zurück kommt, fehlt ihm der Ausgangspunkt. Diesen Punkt kann Gnuplot somit nicht ausgeben.

collatz_recur_up_down.pas
// Hier gehen wir anders vor: Zuerst geht es aufwärts und es wird die eine, problemlose Reihe erzeugt, die aus der wiederholten Verdopplung entsteht. Von dort aus geht es dann wieder abwärts, wobei die "Collatz-Zahlen" (also alle Werte, die aus "n * 3 + 1" entstanden sein können) die Verzweigungspunkte für die Grafik bzw. die Einstiegspunkte für die nächste Rekursion bilden.
Die Daten werden in nur einer Datei abgelegt, die Rekursionen durch Leerzeilen getrennt. Gnuplot macht dann jeweils einen neuen "Ansatz" daraus.

collatz_recur_up_down_und_bunt.pas
// Und nun das Ganze noch bunt und in in 3D. Für jede Rekursion eine neue Datei, aber Gnuplot handelt das ganz prima.

collatz_steps.pas
// Es fiel schon gleich am Anfang auf, dass die Collatz-Reihen recht unterschiedlich in der "Länge" sind. d. h. die Anzahl der Rechenschritte variiert stark, bis die Reihen endlich bei 1 angekommen sind. Und manchmal bilden etliche aufeinanderfolgende Zahlenwerte gleich lange Zahlenreihen, die ich hier mal recht salopp und inkorrekt als "Collatz-Ebenen" bezeichnet habe.

Viel Spaß damit!

Zum Schluss noch dies: Ich habe keine Lust, meinen "Content" den Herren G*le usw. zu schenken und deshalb steht's auf meiner eigenen üppig ausgestatten privaten Web-Seite. Falls etwas nicht funktioniert, werdet Ihr Euch schon melden.

Ich lege auch keinerlei Wert darauf, mit diesen Spielereien WWWeit gesehen werden zu können, aber wenn es im Rahmen dieses Forums interessiert, dann freut mich das richtig. Erwartungsgemäß ist so eine Sache aber in ein bis zwei Monaten komplett durch, dann nehme ich die Seite wieder vom Server runter.

[schorsch_76]

Woher kommt der Name "Collatz"? Haben diese Reihen praktische Anwendungen wie die Taylor Reihen?

[Huo]

Danke für den (für mich jedenfalls) sehr anregenden Beitrag . Auf das faszinierende Collatz-Problem bin ich vor Jahren gestoßen und habe damals als Übung ein paar kleine Python-Programme dazu geschrieben, allerdings keines mit Plot-Ausgabe und insgesamt wohl weniger anspruchsvoll.

Eine Frage, die ich mir gestellt hatte, war die nach besonders "langen" Collatz-Folgen: Für welche Ausgangswerte werden vergleichsweise viele Schritte benötigt, bis die zugehörige Collatzfolge endlich bei der 1 anlangt? Mein entsprechendes Pythonprogramm gibt bis zu einer frei wählbaren oberen Grenze N alle Zahlen n aus, deren Collatzfolge länger ist als die Collatzfolgen aller Vorgänger m < n:

Code: Alles auswählen

$ python collatz_schritte_max.py
Bis zu welcher Zahl soll die Anzahl der Schritte berechnet werden?
1000
Zahl: 1 - Schritte: 1
Zahl: 2 - Schritte: 2
Zahl: 3 - Schritte: 8
Zahl: 6 - Schritte: 9
Zahl: 7 - Schritte: 17
Zahl: 9 - Schritte: 20
Zahl: 18 - Schritte: 21
Zahl: 25 - Schritte: 24
Zahl: 27 - Schritte: 112
Zahl: 54 - Schritte: 113
Zahl: 73 - Schritte: 116
Zahl: 97 - Schritte: 119
Zahl: 129 - Schritte: 122
Zahl: 171 - Schritte: 125
Zahl: 231 - Schritte: 128
Zahl: 313 - Schritte: 131
Zahl: 327 - Schritte: 144
Zahl: 649 - Schritte: 145
Zahl: 703 - Schritte: 171
Zahl: 871 - Schritte: 179

Für alle natürlichen Zahlen bis 1000 besitzt die 871 also die längste Collatzfolge, die sich wie folgt darstellt:

Code: Alles auswählen

$ python collatz.py
Geben Sie bitte eine natürliche Zahl ein:
871
871 2614 1307 3922 1961 5884 2942 1471 4414 2207 6622 3311 9934 4967 14902 7451 22354 11177 33532 16766 8383 25150 12575 37726 18863 56590 28295 84886 42443 127330 63665 190996 95498 47749 143248 71624 35812 17906 8953 26860 13430 6715 20146 10073 30220 15110 7555 22666 11333 34000 17000 8500 4250 2125 6376 3188 1594 797 2392 1196 598 299 898 449 1348 674 337 1012 506 253 760 380 190 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 1

Übrigens: Auch für Mathe-Nerds gibt es alle Jahre wieder einen sehr schönen Adventskalender (der keine Kenntnisse jenseits der Schulmathematik voraussetzt, aber die Bereitschaft zum Kopfzerbrechen):
https://www.mathekalender.de/wp/de/home-page-deutsch/

[kalle123]

Die beiden YT videos kannte ich schon dazu

https://www.youtube.com/watch?v=094y1Z2wpJg

https://www.youtube.com/watch?v=LqKpkdRRLZw

Aber toll, dass du deinen Ansatz hier vorstellst

Gruß KH

[TuxPeter]

Vielen Dank für Eure Beiträge!

Die jeweils "längsten" Collatz-Folgen in einem Zahlenbereich zu suchen, fand ich auch sehr interessant - ich habe sie lediglich aus der graph. Darstellungen herausgefizzelt.
Was mich immer noch umtreibt, ist, ein mal ein Programm zu schreiben, welches die von mir so benannten "Collatzs-Ebenen" sucht. Falsche Bezeichnung, aber für mich anschaulich, aus den Grafiken heraus. Eigentlich keine Ebenen, sondern nur Geraden, von einer größere Anzahl gleich langer Collatzreihen aus direkt aufeinanderfolgenden Zahlen gebildet. Das eine Progr. (Collatz-Steps) zeigt diese ja als Graph, und aus dem Gezackele in der unteren, schwarzen Linie geht die jeweilige Anzahl von gleichlangen Reihen hervor.
Man könnte die Aufgabenstellung auch erweitern und nach beliebigen Mustern suchen, z.B. linear ansteigende oder abfallende Längen usw. Es gäbe da schon noch etwas zum Basteln ...

[uname]

Danke für deinen schönen Beitrag. Vor Jahrzehnten habe ich auch einige mathematische Probleme mit Software gelöst. Hierzu gehörte z. B. die Annährung von Pi. Hierfür habe ich in meinen Berechnungen einen Viertel Einheitskreis genommen und die äußere bzw. innere Fläche in Form von Hunderttausenden oder waren es Millionen Einzelstreifen berechnet.

Heute interessiert mich die Mathematik immer noch. Aber ich konsumiere sie eigentlich nur noch passiv. So schaue ich gerne Videos von Numberphile, die auch Videos zu Collaz gemacht haben.

Sehr schön finde ich auch die Videos von mathspacewien, wo vor allen auf historische Formeln eingegangen wird.

[Meillo]

Interessant faende ich die Frage, an welchen Zahlen man nie vorbei kommt. Bleiben immer welche offen oder werden beim Berechnen der Reihen bis zur Ausgangszahl 1000 beispielsweise alle Zahlen bis 500 mal besucht (die Startzahlen ausgeschlossen, natuerlich)?

Mag dafuer mal jemand eine Auswertung machen oder Erkenntnisse beschreiben?

[TuxPeter]

Es gibt ja in den Gnuplots immer geheimnisvolle Lücken, aber diese sind in höheren Wertebereichen angesiedelt.
Da aber die Schiene, auf denen die Reihen nach unten sausen, die Halbierung ist, müssen bei den Reihen von 2 bis n alle Zahlen von 1 bis n/2 von mindestens einer Reihen "durchquert" werden.