0 Daumen
469 Aufrufe

Aufgabe:

Lösung des Collatz Problems


Problem/Ansatz:

Zuerst weiß ich das Viele der besten Mathematiker dieses Problem versucht haben zu lösen und mein Beweis wahrscheinlich nicht korrekt ist, dennoch denke ich das es vielleicht doch ein Beweis ist und würde mich freuen, wenn jemand Mal drüberschauen kann und vielleicht Fehler entdeckt, die ich so nicht sehe. Was vielleicht wichtig ist, ist das ich erst 17 bin also kein Mathematik mit Studienabschluss und dem fehlenden Fachwissen wie man richtig beweist, trotzdem hab ich es Mal versucht.

Den Beweis habe ich über das Newton Verfahren geschafft(also hoffe ich).

Nehmen wir uns die Collatz Folge, nach einer Analyse habe ich festgestellt das man das nächste ungerade Glied der Collatz Folge, wie folgt definieren kann, sofern Cn ungerade ist. Cn+1 = \( \frac{3*Cn+1}{gcd(3*Cn+1,23*C(n)+1)} \). Dabei gibt der gcd die größte 2er Potenz an die in der neuen geraden Collatzzahl enthalten ist. Durch das Teilen durch diesen Faktor erhält man den ungeraden Rest, welcher die neue Collatz Zahl ist. Probe: C₀= 3 -> C₁ = \( \frac{3*3+1}{gcd(3*3+1,23*3+1)} \) = \( \frac{10}{2} \) = 5. Das Newton Verfahren hat die Form xn+1 = xn- \( \frac{f(xn)}{f'(xn)} \) und wenn man x mit C ersetzt erhält man: Cn+1 = Cn- \( \frac{f(Cn)}{f'(Cn)} \) = \( \frac{Cn*f'(Cn)-f(Cn)}{f'(Cn)} \). Jetzt haben wir zwei Gleichungen für Cn+1, die wir gleichsetzen können. Also Cn+1 = \( \frac{3*Cn+1}{gcd(3*Cn+1,23*Cn+1)} \) = \( \frac{Cn*f'(Cn)-f(Cn)}{f'(Cn)} \). Wenn wir die Nenner und Zähler vergleichen erhalten wir: f'(Cn)= gcd(3*Cn+1,23*C(n)+1) und 3*Cn+1 = Cn * f'(Cn) - f(Cn) => f(Cn) = Cn * f'(Cn) - (3*Cn +1) = Cn * gcd(3*Cn+1, 23*C(n)+1) - (3*Cn+1). Nun hat man eine Funktion die von den Collatzzahlen abhängt und wenn man das Newton Verfahren mit einer ungeraden Zahl als Startwert benutzt, ist das nächste x durch das Newton Verfahren, die nächste ungerade Collatzzahl. Wenn man jetzt zeigt das die Funktion nur eine Nullstelle hat, nämlich die 1, dann zeigt das das es nur den Loop 4,2,1 und jede ungerade Collatzzahl mit der man beginnt dank der Eigenschaft des Newton Verfahren, des Annähern an die Nullstelle, auch in den Loop kommt. Also da der gcd eine zweierpotenz ist und wir die Nullstelle suchen der Funktion folgt: f(Cn) = 0 = Cn * 2k -(3*Cn+1) => 2k =\( \frac{3*Cn+1}{Cn} \). Die einzige Collatz Zahl die, diese Gleichung erfüllt ist die 1 und wen man den Grenzwert von C gegen unendlich nimmt kommt 3 raus weshalb, auch nicht die zwei eine Möglichkeit ist als Potenz. Demnach ist die einzige Möglichkeit die 1 und dazu ist diese auch ungerade und erfüllt die Bedingungen. Damit ist gezeigt das alle ungeraden Collatzzahlen nach endlichen Schritten gegen die Nullstelle die 1 konvergiert und somit im Loop ist.

Avatar von
Nehmen wir uns die Collatz Folge

Das ist schon ein durchaus kritischer Satz, denn "die" Collatz-Folge existiert gar nicht. Viel eher existiert für jede natürliche Zahl eine Folge von Iterierten, die eben durch die Collatz-Funktion berechnet werden. Die Vermutung ist: Für jede Startzahl endet die Folge der Iterierten in dem Zyklus (1, 2, 4).

Nehmen wir uns die Collatz Folge, nach einer Analyse habe ich festgestellt das man das nächste ungerade Glied der Collatz Folge, wie folgt definieren kann, sofern Cn ungerade ist. $$ C_{n+1} =  \frac{3\cdot C_n+1}{\gcd(3\cdot C_n+1,2^{3\cdot C_n+1})} $$ Dabei gibt der gcd die größte 2er Potenz an die in der neuen geraden Collatzzahl enthalten ist.

Das Problem kann durchaus angepasst werden, indem man die Iterationsvorschrift kann dahingehend modifiziert.

Das Newton Verfahren hat die Form \( x_{n+1} = x_n- \frac{f(x_n)}{f'(x_n)} \) und wenn man x mit C ersetzt erhält man: \( C_{n+1} = C_n- \frac{f(C_n)}{f'(C_n)} = \frac{C_n\cdot f'(C_n)-f(C_n)}{f'(C_n)} \).

Das Newton-Verfahren ist eine Iterationsvorschrift, die zu einer gegebenen Funktion und einem gegebenen Startwert Eine Iterationsfolge über

$$ x_{n+1} := x_n- \frac{f(x_n)}{f'(x_n)} $$

berechnet. Insofern muss man das \( f \) spezifizieren und kann dann da auch nicht einfach beliebige Folgen einsetzen und erwarten, dass immer noch Gleichheit gilt.

Dein Ziel könnte es sein eine Funktion \( f \) zu bestimmen, für die mit \( C_1 =m \in \mathbb N \) die Gleichheit

$$ C_{n+1} = C_n + \frac{f(C_n)}{f'(C_n)} \quad \forall n\in\mathbb N$$

gilt. Dazu kann man

$$  \frac{3\cdot C_n+1}{\gcd(3*C_n+1,2^{3\cdot C_n+1})} = C_{n+1} \stackrel{!}{=} \frac{C_n*f'(C_n)-f(C_n)}{f'(C_n)} $$

betrachten und schauen, ob man daraus eine Funktionsvorschrift gewinnen kann. Wichtig ist, dass die zweite Gleichheit (mit ! gekennzeichnet) nur für bestimmte Funkionen \( f \) gilt und man ein solches \( f \) erst noch bestimmen muss. Die Existenz einer solchen Funktion und ob sie in irgendeiner Form elementar ist, sei mal dahingestellt.

Wenn wir die Nenner und Zähler vergleichen erhalten


Dieser Schritt ist nicht gerechtfertig, denn:

1. Da wir f nicht kennen, können wir nicht sagen, dass der Nenner und Zähler des zweiten Bruchs ganzzahlig sind.
2. Wenn wir dies als Zusatzannahme voraussetzen, können wir den Schluss aber immer noch nicht durchführen, da der Bruch auf der linken Seite nie vollständig gekürzt ist. Über den Bruch auf der rechten Seite haben wir überhaupt keine Aussage.

Bsp.: Aus der Gleichheit 3/5 = 9/15 folgt nicht 3=9 und 5=15.

Also ist dieser Ansatz aller Voraussicht nach nicht zielführend.

Stattdessen brachtest du also direkt den Ansatz über ein Gleichungssystem:

\( f'(C_n)= \gcd(3\cdot C_n+1,2^{3\cdot C_n+1}) \)
\( 3\cdot C_n+1 = C_n \cdot f'(C_n) - f(C_n)\)

\( \implies f(C_n) = C_n \cdot f'(C_n) - (3\cdot C_n +1) \)
\( \implies f(C_n) = C_n \cdot \gcd(3\cdot C_n+1, 2^{(3\cdot C_n+1)}) - (3\cdot C_n+1)  \)

Also ist der Ansatz schlussendlich \( f \) passend an diskreten Stellen zu definieren, ohne eine geschlossene Form anzugeben.

Nun hat man eine Funktion die von den Collatzzahlen abhängt und wenn man das Newton Verfahren mit einer ungeraden Zahl als Startwert benutzt, ist das nächste x durch das Newton Verfahren, die nächste ungerade Collatzzahl. Wenn man jetzt zeigt das die Funktion nur eine Nullstelle hat, nämlich die 1,

Ich denke aus den gegebenen Daten über \( f \) lässt sich diese Frage nicht beantworten.

Also da der gcd eine zweierpotenz ist und wir die Nullstelle suchen der Funktion folgt: f(Cn) = 0 = Cn * 2k -(3*Cn+1) => 2k =\( \frac{3*Cn+1}{Cn} \). Die einzige Collatz Zahl die, diese Gleichung erfüllt ist die 1

Warum?

Die einzige Collatz Zahl die, diese Gleichung erfüllt ist die 1 und wen man den Grenzwert von C gegen unendlich nimmt kommt 3 raus weshalb, auch nicht die zwei eine Möglichkeit ist als Potenz


Du kannst C nicht gegen unendlich laufen lassen, n vielleicht. Aber der Grenzwert wird nur existieren, wenn man weiß, dass \( C_n \) konvergiert oder bestimmt divergiert. Ersteres ist äquivalent zur Collatz-Vermutung und kann daher nicht angenommen werden.

Danke für die Antwort und ja ich weiß vieles ist nicht richtig formuliert. Die Idee hinter dem verwenden des Newtonverfahren war das finden einer Funktion die eben die Eigenschaft hat, wenn man das Verfahren anwendet die nächste ungerade Collatz Zahl der Folge zu finden. Und diese findet man in dem man die Vorschrift der nächsten ungeraden Collatzzahl mit der des Newtonverfahren gleichsetzt. Dies geht den man sucht ja die Funktion die dies zulässt also kann man doch nach dieser umstellen und die beiden Nenner gleichsetzen. Zu der Frage wieso der gcd einer zweierpotenz ist hätte ich vermutlich näher eingehen können aber da dieser den größten gemeinsamen Faktor angibt und es sich bei der einen Zahl nur um eine Zweierpotenz handelt, kann der größte gemeinsam Faktor nur eine zweierpotenz sein. Da wir den Grad aber nicht kennen ist das Ergebnis also 2k. Und so kommt man eben durch gleichsetzen der Funktion mit 0, auf den Ausdruck der angibt welches Cn eine Nullstelle zur Funktion ist. Dieses Cn muss eine Zweierpotenz sein, welches nur Cn =1 erfüllt. Das mit dem Grenzwert war tatsächlich auch unsauber ausgedrückt. Was ich damit zeigen wollte ist das die 1 tatsächlich die einzige Collatzzahl ist, die eine Nullstelle der Funktion ist, denn egal wie groß das Cn ist, der Term kann nie kleiner als 3 sein und somit gibt es keine andere Collatzzahl, die eine Nullstelle der Funktion ist, schließlich muss diese dann einer Zweierpotenz ergeben die kleiner als 4 ist. Ich hoffe nun das der Ansatz etwas besser verstanden ist und ja die Funktion ist tatsächlich nur für die natürlichen Zahlen definiert und die Werte auf den ganzen Zahlen, denn die Funktion kann sowohl positiv als auch negativ sein.

2 Antworten

0 Daumen

Kann dir bei deiner Frage inhaltlich leider nicht weiterhelfen, dennoch ein kleiner Hinweis: LaTeX-Formeln müssen hier mit $$ an Formelanfang und ende markiert werden, um sie korrekt darzustellen.

Avatar von

Achso okay danke:) war das erste Mal das ich was gepostet habe

\(\)----\(\)

0 Daumen

Deine Formeln sind leider schwer oder gar nicht lesbar. Deshalb habe ich mir deinen 'Beweis' nicht ausführlich ansehen können. Ich selbst (ebenso, wie mein ehemaliger Mathelehrer) habe mich viele Jahre mit diesem Problem beschäftigt. Ich glaube eine Beweisidee entdeckt zu haben:

Wenn man jeder Startzahl die Anzahl der Elemente der Collatz-Folge mit dieser Startzahl zuordnet und diese Wertepaare als Polarkoordinaten auffasst, erhält man als Graph eine Spirale von 'Fußabdrücken', welche eine Gesetzmäßigkeit erkennen lässt. Einen vollständigen Beweis konnte ich daraus nicht entwickeln. Dein Ansatz über das Newton-Verfahren wird so nicht gelingen.

Alle ungelösten Probleme der Mathematik wurden von sehr vielen Mathematikern und mathematischen Laien zu lösen versucht. Die Tatsache, dass das Collatz-Problem noch keiner gelöst hat, macht mich sowohl gegenüber meinem eigenen als auch gegenüber deinem Ansatz sehr skeptisch.

Avatar von 123 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community