PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Collatz Vermutung - Teillösung



Kibo
31.12.2016, 09:23
Hallo,


Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:

Beginne mit irgendeiner natürlichen Zahl n > 0.
Ist n gerade, so nimm als nächstes n/2.
Ist n ungerade, so nimm als nächstes 3n + 1.
Wiederhole die Vorgehensweise mit der erhaltenen Zahl.


Die Vermutung ist, dass alle Zahlen am Ende auf die 1 hinauslaufen.

Komischerweise sehe ich im Wikipediaartikel keinen Hinweis auf eine offensichtliche Teillösung:
Folgende unendliche Reihen bestätigen die Vermutung:
\[ \sum_{x=0}^\infty x \in \N 2^x] laufen alle gegen 1 weil die Zahl aussschließlich aus Zweierfaktoren aufgebaut ist und immer nur /2 gerechnet wird wie 16->8->4->2->1
\[ \sum_{x=0}^\infty x \in \N 3*2^x] bestehen nur aus 2er Faktoren und einem 3er Faktor. 3 und von da ->10->5->16->8->4->2->1
daraus folgt \[ \sum_{x=0}^\infty x \in \N y*2^x] für alle y die die vermutung bestätigen

Rechnet man rückwärts, kann man von allen diesen Reihen sich die raussuchen die durch 3 teilbar sind (unendlich viele) +1 rechnen.

Ich geh mal davon aus, das man das so ähnlich in einschlägiger Literatur finden wird?

mfg

TomS
31.12.2016, 09:56
Du meinst sicher nicht

$$ \sum_{x=0}^\infty x \in \mathbb{N} 2^x $$

$$ \sum_{x=0}^\infty x \in \mathbb{N} 3*2^x $$

Was soll das sein? Wozu die Summe?

Du meinst schlichtweg die Zahlen

$$a_n = 2^n,\;n \in \mathbb{N}$$

$$b_n = 3 \cdot 2^n,\;n \in \mathbb{N}$$

Ja, dafür landest du direkt bei

$$2^n \to 2^{n-1} \to\ldots\to 2 \to 1$$

$$3 \cdot 2^n \to 3 \cdot 2^{n-1} \to\ldots\to 6 \to 3 \to \ldots$$

Die Vemutung besagt jedoch, dass dies für beliebige Zahlen gilt. Dies für spezielle Zahlen zu zeigen hilft also erst mal nicht weiter.

julian apostata
31.12.2016, 11:19
Mit "Geogebra" lässt es sich so einrichten.

n=111 (ihr könnt auch eine andere Zahl wählen). Dann erzeugt ihr eine Schaltfläche. Ich nenne sie "nächste Aktion".

In deren Skriptingteil (bei Mausklick) gebt ihr ein:

Wenn[Mod[n, 2]==0, SetzeWert[n, n/2], SetzeWert[n, 3n+1]]

Wenn ihr jetzt "ewig" auf der Schaltfläche rum klickt, ohne auf die 1 zu kommen, dann habt ihr die Vermutung widerlegt. Da müsst ihr aber aufpassen, dass ihr keine Zweierpotenz erwischt, sonst habt ihr verloren.

Kibo
31.12.2016, 20:32
Hallo Tom, ebenfalls hallo Julian,

du hast Recht, dass ich keine Summe meine.
Ich meine im ersten Absatz die Menge alle Zweipotenzen, wie Julian wohl auch vermutet hat: 2^1, 2^2, 2^3....2^∞ sind alles Zahlen die definitv bei 1 landen.

Alle Produke mit 3 und diesen Zahlen landen ebenfalls bei 1.

Alle Produkte aus einer Zahl die bei 1 landet und einer der eben genannten Zahlen landet ebenfalls bei 1.

Ich bitte die falsche Notation zu Entschuldigen, ich finde leider kaum noch Zeit zum Posten, das geht nur noch "zwischen durch".

mfg

TomS
01.01.2017, 22:06
Ich habe mich mal ein bisschen umgesehen.

Statt der Abbildung

$$ C : n \to C(n) = \left\{ \begin{array}[lcl] nn/2 & : & n = 0 \, \text{mod} \, 2 \\ 3n+1 & : & n = 1 \, \text{mod} \, 2 \end{array} \right. $$

betrachtet man evtl. besser

$$ T : n \to T(n) = \left\{ \begin{array}[lcl] nn/2 & : & n = 0 \, \text{mod} \, 2 \\ (3n+1)/2 & : & n = 1 \, \text{mod} \, 2 \end{array} \right. $$

da hier die sicher mögliche zweite Iteration für die gerade Zahl 3n+1 bereits eingebaut ist.

Es gilt ja: wenn n ungerade, dann wird 3n+1 berechnet; dieses ist jedoch sicher gerade, da für ungerades n=2k+1 gilt und damit 3n+1 = 3(2k+1)+1 = 6k+2 gerade.


Hier eine paar schöne Darstellung des Collatz-Graphen

https://www.jasondavies.com/collatz-graph/
http://swimmingthestyx.com/?p=44 (http://swimmingthestyx.com/?p=447)


Die Vermutung kann wie folgt äquivalent formuliert werden:
1) Für jede positive Zahl n endet die durch C (bzw. T) definierte Folge nach endlich vielen Schritten bei 1
2) Es existiert kein weiterer Loop neben 4,2,1,4,...
3) Der Collatz-Graph ist zusammenhängend
4) Generiert man den zusammenhängenden Teil des Collatz-Graphen ausgehend von 1, so überdeckt dieser die natürlichen Zahlen


Der Collatz-Graph kann mittels der Äquivalenzrelation

$$ a \sim b \, \Leftrightarrow\, \exists z \in \mathbb{Z}: b = 2^z a$$

komprimiert werden. Zwei Zahlen a,b seien äquivalent, d.h. a ~ b, wenn eine ganze Zahl z existiert, so dass die o.g. Gleichung für a,b erfüllt ist.

Da jede beliebige natürliche Zahl n mittels einer ungeraden Zahl p und einem Exponenten k = 0,1,2,... geschrieben werden kann als

$$n = 2^k p, \, p = 1 \, \text{mod} \, 2$$

kann man - ohne Information zu verlieren - einen "reduzierten" Collatz-Graphen konstruieren, indem man im originalen im Graphen alle Zahlen der Äquivalenzklasse [p] zu p

$$[p] = \{p,2p,2^2p,2^3p,\ldots\}$$

durch p ersetzen, d.h. alle geraden Zahlen sowie die trivialen Kanten

$$ 2^kp \to 2^{k-1}p \to\ldots\to 2p \to p$$

eliminiert. Der so reduzierte Graph ist definiert über den Äquivalenzklassen [p], repräsentiert durch die ungeraden Zahlen p.

TomS
04.01.2017, 20:30
Ich habe jetzt mal begonnen, den Collatzgraphen zu generieren.


Zunächst ein Versuch, dies für alle n unterhalb einer gewissen Schranke N durchzuführen, d.h. C(n) zu iterieren. Das Ergebnis sieht sehr ungleichmäßig aus, da der Graph sozusagen Lücken aufweist. Die Elemente werden nämlich nicht alle bis zu einer gewissen Größe Z(N) generiert, sondern es werden i) alle Elemente bis einschließlich N ii) sowie teilweise größere mittels C(n) generiert; oberhalb von N sind also nur einige Elemente vertreten.


Dann ein Versuch, reduzierte Graphen zu erzeugen; dazu definieren ich eine Funktion F(n) wie folgt:

$$ F : n \to F(n) = \left\{ \begin{array}[lcl] x \frac{n}{2^{\nu(n)}} & : & n = 0 \, (\text{mod} \, 2) \\ \frac{(3n+1)}{2^{\nu(3n+1)}} & : & n = 1 \, (\text{mod} \, 2) \end{array} \right. $$

Die Funktion nu zählt dabei wie häufig der Primfaktor 2 in n vorkommt, d.h. liefert für die o.g. Darstellung von mittels k, p genau k zurück:

$$ \nu(2^k\,p) = k$$

$$ n / 2^{\nu(n)} = p$$

Damit erhalte den über die Äquivalenzklassen [p] und repräsentiert durch die ungeraden Zahlen p definierten reduzierten Graphen.


Das C++ Programm ist noch sehr überschaubar; kann ich gerne zur Verfügung stellen. Die Graphik erzeuge ich mittels des Programms yEd; das C++ Programm liefert eine Ausageb im *.tgf Format.


Den gesamten Collatzgraphen erhält man m.E. jedoch besser umgekehrt mittels Rekursion, d.h. anstatt dass man den Nachfolger mittels C(n) o.ä. sucht, konstruiert man rekursiv die jeweils möglichen Vorgänger:

$$ C^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1,2,3,5 \, (\text{mod} \, 6) \\ \{2n, (n-1)/3\} & : & n = 4 \, (\text{mod} \, 6) \end{array} \right. $$

$$ T^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1 \, (\text{mod} \, 3) \\ \{2n, (n-1)/3\} & : & n = 2 \, (\text{mod} \, 3) \end{array} \right. $$

TomS
04.01.2017, 21:03
Ich habe jetzt mal begonnen, den Collatzgraphen zu generieren.


Zunächst ein Versuch, dies für alle n unterhalb einer gewissen Schranke N durchzuführen, d.h. C(n) zu iterieren. Das Ergebnis sieht sehr ungleichmäßig aus, da der Graph sozusagen Lücken aufweist. Die Elemente werden nämlich nicht alle bis zu einer gewissen Größe Z(N) generiert, sondern es werden i) alle Elemente bis einschließlich N ii) sowie teilweise größere mittels C(n) generiert; oberhalb von N sind also nur einige Elemente vertreten.


Dann ein Versuch, reduzierte Graphen zu erzeugen; dazu definieren ich eine Funktion F(n) wie folgt:

$$ F : n \to F(n) = \left\{ \begin{array}[lcl] x \frac{n}{2^{\nu(n)}} & : & n = 0 \, (\text{mod} \, 2) \\ \frac{(3n+1)}{2^{\nu(3n+1)}} & : & n = 1 \, (\text{mod} \, 2) \end{array} \right. $$

Die Funktion nu zählt dabei wie häufig der Primfaktor 2 in n vorkommt, d.h. liefert für die o.g. Darstellung von mittels k, p genau k zurück:

$$ \nu(2^k\,p) = k$$

$$ n / 2^{\nu(n)} = p$$

Damit erhalte den über die Äquivalenzklassen [p] und repräsentiert durch die ungeraden Zahlen p definierten reduzierten Graphen.


Das C++ Programm ist noch sehr überschaubar; kann ich gerne zur Verfügung stellen. Die Graphik erzeuge ich mittels des Programms yEd; das C++ Programm liefert eine Ausageb im *.tgf Format.


Den gesamten Collatzgraphen erhält man m.E. jedoch besser umgekehrt mittels Rekursion, d.h. anstatt dass man den Nachfolger mittels C(n) o.ä. sucht, konstruiert man rekursiv die jeweils möglichen Vorgänger:

$$ C^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1,2,3,5 \, (\text{mod} \, 6) \\ \{2n, (n-1)/3\} & : & n = 4 \, (\text{mod} \, 6) \end{array} \right. $$

$$ T^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1 \, (\text{mod} \, 3) \\ \{2n, (n-1)/3\} & : & n = 2 \, (\text{mod} \, 3) \end{array} \right. $$

TomS
04.01.2017, 21:37
Mit der Relation F* zur rekursiven Generierung des reduzierten Graphen habe ich Probleme. Zunächst mal enthält der reduzierte Graph keine geraden Zahlen, d.h. man kann zwar F(n) für beliebige n definieren, muss diese jedoch im Graphen explizit ausschließen. Die erste Zeile entfällt demnach, es wird nie ein F*(n) = 2n oder 2k n gebildet, bzw. diese müssen übersprungen werden. Die zweite Relation würde ich dann wie folgt formulieren:

$$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \,\wedge\, k = \nu(3n+1)\} $$

Ist das sinnvoll? Kann man das vereinfachen?

TomS
05.01.2017, 00:01
$$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \,\wedge\, k = \nu(3n+1)\} $$

Ist das sinnvoll? Kann man das vereinfachen?
Ich denke, ja:

$$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \} $$

ist ausreichend.

Ich habe jetzt das Programm für die rekursive Erzeugung des Graphen mittels F* fertig. Soweit ich das überprüfen konnte, sieht es vernünftig aus. Der mittels F bzw. F* definierte Graph ist eine "Vergröberung" des mittels C bzw. C* definierten Graphen. Konkret: wenn dieser einen Subgraphen

$$ G_C = \cdots \longrightarrow \! \bigcirc \! \longrightarrow \! \bullet \! \longrightarrow \cdots \longrightarrow \! \bullet \! \longrightarrow \! \bigcirc \! \longrightarrow \cdots $$

enthält, in dem kleine ausgefüllte Punkte für gerade Zahlen und große Kreise für ungerade Zahlen stehen, dann lautet der Subgraph in der Vergröberung

$$ G_F = \cdots \longrightarrow \! \bigcirc \! \longrightarrow \! \bigcirc \! \longrightarrow \cdots $$

Ich kann das (noch) nicht wasserdicht beweisen, aber ich sehe das allen meinen Überlegungen und Ergebnissen des Programmes an. Wenn überhaupt, dann existieren noch kleinere Fehler, aber das Prinzip ist klar.

Damit ist es möglich, die Collatz-Vermutung wie folgt äquivalent umzuformulieren:
3') Der auf den ungeraden natürlichen Zahlen vergröberte Collatz-Graph G ist zusammenhängend
4') Generiert man den zusammenhängenden Teil des vergröberten Collatz-Graphen ausgehend von 1, so überdeckt dieser die ungeraden natürlichen Zahlen

Die geraden Zahlen sind zumindest für die Darstellung obsolet (nicht jedoch für die Berechnung, denn sie treten wie in der obigen Formel auch bei der Definition des vergröberten Graphen auf)

Nathan5111
05.01.2017, 01:18
Hallo Tom,

ich habe mich vor einigen Jahren auch mal spielerisch mit Collatz beschäftigt. Meiner Meinung nach müsste ein Beweis wie folgt aussehen:

Bis zu einer Zahl n (gerade) ist die Vermutung experimentell bewiesen.

Gibt es eine Zahl n+1 (ungerade), die in ihrer 'Entwicklung' keine Zahl kleiner als n enthält?

Ich bin 'leider' nur Physiker, nicht Mathematiker, daher würde ich auch sehr gerne auch mal Ralf dazu hören wollen.

TomS
05.01.2017, 02:08
Gibt es eine Zahl n+1 (ungerade), die in ihrer 'Entwicklung' keine Zahl kleiner als n enthält?
D.h.:

Bekannt sei, dass

$$\exists n,k \,:\, T^k(n) = 1$$

Gefragt ist, ob

$$\not\exists k \,:\,T^k(n+1) \le n$$

gilt.

Das ist m.E. nur eine Umformulierung und hilft noch nicht weiter. Wenn letzteres gilt, dann existiert ein n+1, dessen Entwicklung entweder divergiert oder einen weiteren Zyklus generiert.

Frankie
05.01.2017, 12:56
Mich würde ja einmal interessieren, ob es eine näherungsweise Methode gibt, das vorwärts zu generieren... darüber denke ich schon länger nach.

D.h. gegeben sind 1 als Startpunkt und die Startzahl n element N. Lässt sich für jede Verzweigung, die sich rückwärts aus n ... -> 1 ergibt, der wahrscheinliche Weg generieren? Wenn ja, sollte das ein Beweis für Collatz sein.

Sehr interessant jedenfalls, auch für mich als Laien in der Materie.

Grüsse,
Frank

PS: Alles Gute im neuen Jahr an Alle!

TomS
05.01.2017, 13:40
Mich würde ja einmal interessieren, ob es eine näherungsweise Methode gibt, das vorwärts zu generieren... darüber denke ich schon länger nach.D.h. gegeben sind 1 als Startpunkt und die Startzahl n element N. Lässt sich für jede Verzweigung, die sich rückwärts aus n ... -> 1 ergibt, der wahrscheinliche Weg generieren? Wenn ja, sollte das ein Beweis für Collatz sein.Wie ich oben gezeigt habe, kann der Graph nicht nur näherungsweise sondern exakt konstruiert werden, vorwärts und rückwärts. Für einen Startpunkt n ist jedoch keine Abkürzung zur Iteration k bekannt. D.h. man muss für jedes n alle (potentiell unendlich viele) Schritte gemäß Ck(n) oder Tk(n) durchspielen. Auch die rekursive Konstruktion mittels C* oder T* ausgehend von 1 beweist nicht, dass dabei jede natürliche Zahl n auch erreicht wird. Es könnten Zahlen nicht erreicht werden, d.h. der Graph würde in nicht-zusammenhängende (und damit nicht-erreichbare) Sub-Graphen zerfallen, die entweder divergente Teile oder weitere Schleifen enthalten könnten. D.h. obwohl alle Schritte exakt bekannt sind, hilft das beim Beweis nicht.

Dgoe
05.01.2017, 16:24
Hallo Tom,

lässt sich so ein Graph auch irgendwie plotten oder ist eine Visualisierung sinnlos? Vielleicht theoretisch gar eine Animation, wie er sich entwickelt?

Gruß,
Dgoe

zabki
05.01.2017, 18:38
nur so als Einfall:

kann man nicht versuchen, größere Zyklen zu konstruieren oder Bedingungen zu formulieren, die größere Zyklen erfüllen müssen, falls es sie gibt?

Chrischan
05.01.2017, 20:55
Hi Dgoe,

lässt sich so ein Graph auch irgendwie plotten
In Post #5 hat Tom bereits zwei Links genannt:

Hier eine paar schöne Darstellung des Collatz-Graphen

https://www.jasondavies.com/collatz-graph/
http://swimmingthestyx.com/?p=44 (http://swimmingthestyx.com/?p=447)

Gruß,
Christian

Dgoe
05.01.2017, 21:14
Boah!

Fazinierend. Echt.

Danke Christian.

pane
05.01.2017, 22:09
nun so einfach ist es wohl nicht. Das Problem ist noch immer ungelöst und mithilfe von Computer sind sicherlich schon die ersten zig-Milliarden Zahlen berechnet worden. Nie ist man auf irgendwas anderes gekommen als die 4->2->1 Schleife.

Das es auch anders sein könnte, sieht man, wenn man negative Zahlen nimmt. Wenn man mit einer negativen Zahl startet bleibt man im negativen Bereich. Man kann es sich dann auch leichter machen und alles mit -1 multiplizieren; dann ist man wieder im positiven. Allerdings ändert sich dann die Regel für ungerade Zahlen. Sie lautet dann:
n->3n-1 Nun hat man auf einmal drei verschiedene Zyklen, die immer wieder vor kommen, und zwar: 1->2->1..., 5->14->7->20->10->5... und 17->50->25->74->37->110->55->164->82->41->122->61->182->91->272->136->68->34->17...

Daran sieht man aber auch, dass auch bei großen Zahlen plötzlich andere Zyklen auftauchen können. Wer gerne mit grossen Zahlen rechnet, kann ja mal die normale Collatzfolge mit 27 beginnen. :-)

Mit freundlichen Grüssen
pane

TomS
06.01.2017, 00:38
... lässt sich so ein Graph auch irgendwie plotten oder ist eine Visualisierung sinnlos? Vielleicht theoretisch gar eine Animation, wie er sich entwickelt?

Das von mir verwendete Programm habe ich oben genannt. Es malt (noch) keine so schönen Bilder, aber es ist Freeware, unterstützt ein extrem simples Importformat und war in kürzester Zeit produktiv benutzbar; letzteres war mein Hauptkriterium.

TomS
06.01.2017, 00:45
nun so einfach ist es wohl nicht. Das Problem ist noch immer ungelöst und mithilfe von Computer sind sicherlich schon die ersten zig-Milliarden Zahlen berechnet worden. Nie ist man auf irgendwas anderes gekommen als die 4->2->1 Schleife.
So meinte ich das auch nicht.

Konkret: Gegeben ist eine Abbildung C(n) oder T(n); damit kann das Problem lokal vollständig untersucht werden. Auch mittels der "Inversen" C* bzw. T* kann der Graph lokal vollständog generiert werden; Aber i) immer nur ohne Abkürzung, und ii) immer nur lokal.

i) bedeutet, dass keine effizientere Berechnung für Tk(n) bekannt ist als Tk(n) selbst.

ii) bedeutet, dass der Graph evtl. nicht zusammenhängend ist und dass dann T* nicht den gesamten Graphen generiert. Der Graph könnte prinzipiell in unendlich viele nicht-zusammenhängende Teilgraphen zerfallen, d.h. man müsste die Rekursion evtl. von unendlich vielen Startwerten aus beginnen, die man jedoch nicht kennen kann.

Ich habe übrigens einen Hinweis gefunden, dass eine Verallgemeinerung des Collatz-Problems tatsächlich nicht entscheidbar ist; allerdings ist diese Verallgemeinerung nicht auf das Collatz-Problems selbst anwendbar.


John H. Conway konnte zeigen, dass es eine verallgemeinerte Collatz-Folge gibt, in der n/2 und (3n+1)/2 durch n/k und (3n+1)/k ersetzt wird, die sich auf den Algorithmus einer Turing-Maschine abbilden lässt, was die mathematische Identität der beiden Probleme bedeutet. Nun weiß man, dass die Frage, ob es zu einem Ende des Algorithmus kommt (Halteproblem) nicht generell entscheidbar ist. Es könnte also sein, dass nicht nur die Lösung dieser verallgemeinerten Collatz-Folge unentscheidbar ist, sondern auch die einfachere Collatz-Vermutung. Damit hätte man ein besonders einfaches Beispiel eines unentscheidbaren Problems.

Mehr als diesen Hinweis kenne ich jedoch nicht; weiß jemand mehr?

Kibo
28.03.2017, 19:23
Collatz-Visualisierung (https://www.youtube.com/watch?v=LqKpkdRRLZw)bei Numberphile ganz aktuell

mfg