Collatz Problem ed

Ein mathematisches Problem.... ungelöst?

Meine eigenen Gedanken dazu, damit ich sie mir nicht jedes Mal neu ausdenke

Problem ed

Man fängt mit einer natürlichen Zahl n an und berechnet dann

$  n / 2  $ , falls n gerade

$  3n + 1  $ , falls n ungerade

und das rekursiv.

Die Behauptung ist, dass man über diese Verkettung von jeder natürlichen Zahl aus zur 1 kommt.

Inverses Problem ed

Problem ed

Man kann eine Menge \( M_C \) definieren als diejenigen Zahlen, bei denen der "inverse" Graph von der 1 aus vorbei kommt:

• also zuerst \( 1 \in M_C \)
• für jede Zahl \( n \in M_C \) ist auch \( 2n \in M_C \) (Regel 1)
• ist \( n \equiv 4 \, (\text{mod } 6) \quad (n - 1) / 3 \in M_C \) (Regel 2)

Die Frage ist dann, ob \( M_C = \mathbb{N} \)

Definitionen ed

Ein Ast geht von einer Zahl (dem Keim) aus und folgt dann nur durch Regel (1).

Der Hauptast des Graphs ist der Ast mit der 1 als Keim. Mit den durch ihn erzeugten Keimen sieht er so aus:

$ 
 \begin{array}{llll}
   1 \rightarrow 2 \rightarrow &4 \rightarrow 8 \rightarrow &16 \rightarrow 32 \rightarrow &64 \rightarrow \dots\\
                               &1                           &5                             &21
 \end{array}
$ 

Gedanken ed

Gedanke 0 ed

Ein Keim ist ungerade

Folgt aus der ursprünglichen Problemstellung, dass eine gerade Zahl immer halbiert wird (also kein Keim sein kann).

Gedanke 1 ed

Ein Ast besteht aus dem Keim und allen seinen 2er-Potenzen

Geht direkt aus der Regel (1) hervor.

Somit muss nur gezeigt werden, dass jede ungerade Zahl als Keim auftritt.

Gedanke 2 ed

Ist ein Keim durch 3 teilbar, so erzeugt dessen Ast keine neuen Keime

Ist der Keim durch 3 teilbar, so sind auch alle Elemente n des Astes durch 3 teilbar und damit kann n+1 nicht durch 3 teilbar sein.

Gedanke 3 ed

Erzeugt ein Element eines Astes einen Keim, so erzeugt das übernächste Element einen weiteren Keim

Ein Keim n wird von einem Ast-Element der Form \( 3n + 1 \) erzeugt. Das übernächste Ast-Element ist dann \( 4 (3n + 1) = 12n + 4 = 3 (4n + 1) + 1 \) . Somit ist der neue Keim von der Form \( 4n +1 \) (das Ast-Element dazwischen erzeugt keinen Keim!)

Insbesondere sind die von einem Ast erzeugten Keime dann durch den ersten Keim und dessen durch die Regel \( n \mapsto 4n + 1 \) Kette gegeben.

Gedanke 4 ed

Ein Keim erzeugt nicht selbst einen Keim

Ein Keim n ist ungerade. Dann kann er nicht von der Form \( n = 3m +1 \) mit einer ungeraden Zahl m sein.

Gedanken zu Schleifen ed

Jede Schleife ist durch ein Element eindeutig bestimmt

(aus der Eindeutigkeit des "positiven" Problems)

Damit kann es nur eine Schleife durch die 1 geben: 4,2,1

Somit widerlegt jede andere Schleife die Behauptung.