Lösung des 3x+1 Problems

[Dirty Oerti]

Tag!

Ich sinniere im Moment mal wieder über eine mögliche Lösung des 3x+1 Problems.
Wer nicht weiß, was gemeint ist: http://de.wikipedia.org/wiki/Collatz-Problem

Kurzes Beispiel:

Startzahl:

15
-ungerade
=> 3 * 15 + 1
46
-gerade
=> 46 / 2
23
-ungerade

(...)

4
-gerade
=> 4/2
2
-gerade
=> 2/2
1
-ungerade
=>3* 1 + 1
4
(und es geht wieder bei 4 an)

Eine schnell getippte Implementierung des Algorithmus in C++ (allerdings mit Berücksichtigung negativer Zahlen):

Code: Alles auswählen

long long collatz_alg( long long start)
{
        cout << start;
        if ( (start == 1) || (start == -1) ) {
                return 1;
        }
        cout << " - ";
        if (start%2) {
                return collatz_alg( 3*start + 1 );
        } else {
                return collatz_alg( start / 2 );
        }
}

Nun möchte, egal wie verrückt das erscheint, versuchen, eine Zahl zu finden, bei der sich (im positiven Bereich) keine Folge von 4 - 2 - 1 am Ende ergibt.

Einfach Zahlen einzusetzen wird wenig bringen, siehe WikipediaArtikel.
Es wurden schon sehr große Zahlen versucht.

Deswegen überlege ich an einem Ansatz, das Problem von hinten heraus zu lösen.

Heißt: Ich versuche einen Endpunkt, bzw eine Folge, die sich wiederholt und nicht 4 - 2 - 1 ist zu finden.

Weil ich das nicht auf dem Papier mache, und weil das hier kein Matheforum sondern ein Programmierforum ist, kann man sich denken, dass ich versuche, das per Computer zu realisieren.

Mal schauen, was dabei herauskommt.

*Nachtrag*
Lösung heißt entweder ein Beispiel, das widerlegt, das jede Ganze, Positive Zahl in der Folge 4 - 2 - 1 endet, oder eine Möglichkeit zu beweisen, das JEDE Zahl in dieser Folge endet.
*/Nachtrag*

[Empire]

Ich hab einen Denk anstoß.
Probier doch mal aus ob es in anderen Zahlen Systemen auch funktioniert
oder ob es dort ähnliche Formeln gibt.

mfg
Empire

*Nachtrag*
Weis nicht wie genau ich meine Gedanke formulieren soll deshalb versuch ich es mit einer Metapher:
Stell dir vor n/2 sei die "Richtung" in die du willst. Aber immer wieder stehen "Hindernisse" (ungerade Zahlen)
im Weg. Mit 3n+1 weichst du ihnen aus.

Hoffe du verstehst was ich meine und es dir weiter hilft.
*/Nachtrag*

[cloidnerux]

Wenn du es wirklich rückwärts betrachten willst, dann stelle dir doch die Frage, wie man sonst zu 1 Kommen könnte.

3n+1 ist immer eine Entfernung von 1, das heißt, egal welche Zahl(außer 0) du betrachtest, du wirst mit 3n+1 nicht näher an 1 heranrücken, auch nicht mit -1.
Das heißt, die einzige Möglichkeit zu 1 zu kommen, ist mit n/2. Das geht aber nur, wenn dieser Wert 2 ist.
Zur 2 kommst du auch nicht mit 3n+1 mit ganzen Zahlen, also geht es hier auch nur wieder mit n/2. Die Bedingung hierfür ist 4, anders geht es nicht. Die 4 kann als n/2 von 8 oder 3n+1 von 1 angesehen werden, was auch die Endlosschleife am ende bedeuten würde.
Das heißt, das ganze wird so lange laufen, bis man zu 4 kommt und dann bricht der Algorithmus ab, anders geht es nicht.
Meine Ausführungen gehen davon aus, das das "Ende" des ganzen die 1 ist.

Und was mir jetzt in den sinn kommt bei dem ganzen, ist es ja doch so, das das ende egt eine bestimmte Zahlenkombination ist, bei der Anfangswert = 3n+1 oder n/2 für n=endwert.
4-2-1 ist so eine Kombination
2 = 4/2
1 = 2/2
4 = 3*1+1

Jetzt müsste man nach weiteren Zahlenpaaren/konstelationen suchen, die genau das erfüllen, wobei die als Endwert nicht 1 haben dürfen, da das wieder zu 4 führen würde. Und wenn man genauer nachdenkt, darf kein Element einer anderen Zahlenkombination vorkommen.

Edit: Hab hier mal bisschen was aufgearbeitet:
http://khsfz.dyndns.info:8000/home/pub/97/

Edit 2:
Nach etwas nachdenken bin ich zu folgenden Schlüssen gekommen:
Sobald die Funktion eine zahl 2^n zurückgibt, wird die Folge in 4-2-1 enden. Da aber eine Zahl 2^n nur durch 3x+1 gebildet werden kann, fallen schon einmal einige zweier Potenzen aus, z.B 32: 32-1=31/3 = 10,3333
Das heißt alle Zahlen für die gilt ((2^n)-1)%3==0 => ((2^n)-1)/3 Sind die schritte, wo die Folge wieder in 4-2-1 enden wird.
Von diesen zahlen gibt es unendlich.
Da diese zahlen selbst ungerade sind, wurden sie durch x/2 gebildet.
Folglich sind alle zahlen (2*((2^n)-1)/3 ein Zeichen dafür, das die Folge in 4-2-1 enden wird.

[cloidnerux]

Auch wenn Dirty Oerty anscheinend nicht mehr so viel Interesse an dem Problem hat, so besteht es bei mir immer noch

In einem Versuch, habe ich einfach mal die Bildungsformel etwas verändert.
Ich hab einfach mal statt 3x+1: x+1, 5*x+1 und 7*x+1 eingesetzt. Alle 3 liefern jeweils eine durch 2 teilbare Zahl und sind deshalb geeignet.
Bei x+1 endete es generell in 2-1, bei 5x+1 Varierte es zwischen verschiedenen Wiederholungen am Ende, je nach Eingabezahl. 7*x+1 gab innerhalb meines Intervalles keine Wiederholung.

Damit komme ich für mich zu dem schluss, das der Algorithmus so lange läuft, bis 3x+1 eine zweierpotenz zurückgibt und damit in die Zweier-Rutsche begibt, die der Algorithmus bis zur 1 hinabläuft.
Damit verändert sich das Problem: Wird für jede Startzahl irgendwann eine Zweierpotenz erreicht?

[Dirty Oerti]

Damit verändert sich das Problem: Wird für jede Startzahl irgendwann eine Zweierpotenz erreicht?

Das ist die ursprüngliche Fragestellung
Finde eine solche Zahl, oder beweise, dass es keine solche gibt.

Und nein, ich habe nicht das Interesse verloren, der ursprüngliche Beitrag ist nur etwas älter (2008 ^^) und daher war ich doch etwas überrascht, dass da noch was kommt

[cloidnerux]

Und nein, ich habe nicht das Interesse verloren, der ursprüngliche Beitrag ist nur etwas älter (2008 ^^) und daher war ich doch etwas überrascht, dass da noch was kommt

Ohh. Hab nicht hingesehen. Dachte egt das das neu wäre^^