Das 3n+1 Problem: Ein Nachtrag

Vor etwa einer Woche habe ich das nach wie vor ungelöste Phänomen des Collatz-Problems vorgestellt. Wie so vieles im Leben lässt es mir keine Ruhe. Aus dieser Unruhe heraus habe ich noch ein paar Ergänzungen zu dem Problem, welche hier kurz angezeigt werden sollen.

---

Welch Wunderwelt der Gedankenspiele doch so manches mathematische Rätsel mit sich bringt! Das Collatz-Problem, bzw. das 3n+1 Problem gehört unverkennbar zu meinen aktuellen Lieblingen. Dadurch, dass der Algorithmus mit einem etwas fitten Kopf ohne Probleme durchführbar ist – und andernfalls auch ein enorm simpler Taschenrechner ausreicht – fliegt er mir oft Stundenlang durch den Kopf. Auf langen Bahnfahrten zum Beispiel, oder beim noch längeren auf-den-Zug-warten. Dabei kam mir folgende Idee:

Visualisiere das Problem!

Um nachzuweisen, dass die Collatz-Vermutung richtig ist, also dass bei der Anwendung des Algorithmus zwangsläufig irgendwann ein n=1 entstehen wird, reicht es auch nachzuweisen, dass irgendwann ein n=2^x aus der Reihe hervorgeht, denn für jedes n=2^x gilt logischerweise, dass es durch zwei teilbar ist ergo in x Schritten ein n=1 ergeben wird. Aufgrund dieser Annahme hielt ich es für sinnvoll, einmal die Schritte und Zusammenhänge zu visualisieren – jedoch leider (bislang) ohne Erfolg.

Die oben angeführte Grafik zeigt die ersten 32 natürlichen Zahlen, die für n infrage kommen würden. Zahlen mit gleicher Hintergrundfarbe gehen direkt auseinander hervor und bilden somit eine Gruppe. Ein Farbverlauf markiert den Übergang in eine andere Gruppe. Beispiel: 24-12-6-3-10-5 gehört in eine Gruppe (rosa) 5-16-8-4-2-1 gehört in eine Gruppe (gelb). Das Problem bei dieser Darstellung ist allerdings, dass einem sehr bald die Farben ausgehen. Das Ergebnis: ein nichtssagender Farbhaufen.

Vielleicht ist es sinnvoller, die Farben andersherum zu bestimmen, also von hinten nach vorn. Beispielsweise: 3-6-12-24 oder eben 5-10-20-40. Eine hierzu angelegte Tabelle gibt Aufschluss darüber, welchen Wert eine Zahl als Nächstes annehmen wird. Man liest sie von rechts nach links – findet also für ein n₁ der Farbe F das passende n₂ in einer Zelle der gleichen Farbe F, welche sich weiter links befindet. (Das entsprechende n₀ befindet sich demnach in der Farbe F rechts von n₁)

Sollte sich zu einem n der Farbe F keine identische Farbe weiter rechts zuordnen lassen, findet sich in der Zelle der entsprechende Hinweis zu welcher Zahl man als Nächstes zu springen hat.

Beispiel für n₁=24 (komplett anhand der Grafik nachzuvollziehen)

n	Wert	Farbe
1	24	Dunkelrot
2	12	Dunkelrot
3	6	Dunkelrot
4	3	Dunkelrot
5	10	Hellblau
6	5	Hellblau
7	16	Gelb
8	8	Gelb
9	4	Gelb
10	2	Gelb
11	1	Gelb

Das n₀ zu 24 lässt sich entsprechend ermitteln, indem man rechts in der Tabelle eine dunkelrote Zelle ausfindig macht, in unserem Fall ist dieses n₀ entsprechend 48

Es gibt allerdings auch besondere n, die mehr als einen Ursprung haben. Nämlich jedes n für welches gilt: n-1 ist restlos durch 3 teilbar. Ein Beispiel dafür wäre die 16, welche sowohl den Ursprung n₀=32 als auch den Ursprung n₀=5 haben kann.

Vielleicht werden diese besonderen Zahlen bei einer späteren Betrachtung noch einmal einen Sinn erhalten – ich bin mir unsicher, ob an diesen Zahlen bereits geforscht wurde. Falls einer der wenigen Leser sich mit der Materie auskennt, soll er sich wie immer auf gewohnten Wege an mich wenden.. Oder über die Kommentarfunktion.

Programmiere den Algorithmus

Es ist fast schon bedenklich, dass ich in meinem letzten Beitrag den fabelhaft einfachen Algorithmus vorgestellt habe, ihn aber zu diesem Zeitpunkt noch nicht in Programmcode ausgedrückt habe. Wie man von vorherigen Beiträgen wissen kann, bin ich für Projekte dieser Art gern bereit, einmal in die Python Trickkiste zu greifen, so auch hier.

list=[]
 def collatz(x):
     f=0
     while x != 1:
         f=f+1
         if x % 2 > 0:
              x =((3 * x) + 1)
              list.append(x)
         else:
             x = (x / 2)
             list.append(x)
     print ("Der Vorgang hat "+str(f)+" Durchgänge benötigt.")
     return list    
 calc=collatz(31)
 highx=1
 for x in calc:
     if(x>highx):highx=x
     print(x)
 print("das größte n ist "+str(highx))

Auf die Idee, den Code zu schreiben bin ich übrigens gekommen, als ich noch händisch – erst im Kopf später mit Taschenrechner – versucht habe, den Algorithmus auf 31 anzuwenden. Sagenhafte 40 Schritte habe ich Schritt für Schritt erledigt, bis ich zur Automatisierung übergegangen bin. Eine richtige Entscheidung – denn aus der 31 ergeben sich satte 106 Schritte bis zur 1: Das größte n hierbei ist 9232.

Die Faszination bleibt

Ich bin nach wie vor fest davon überzeugt, dieses Rätsel niemals lösen zu können. Aber durchaus gewillt, meine Gedanken dazu hier liegenzulassen. Ich kann nur betonen, dass das herumspielen mit solchen Zahlen eine wahre Freude bereiten kann – und hoffe diese Freude hiermit etwas verbreiten zu können.