Das 3n+1 / 5n+1 Problem
 

Auf das neue 3n+1 / 5n+1 Problem bin ich bei meinen
Bemühungen um das 3n+1-Problem gestossen.
Dies Problem ist eine 2-stufige Variante des bekannten 3n+1 Problems.

Es geht los mit einer ungeraden Zahl n.
Dazu bildet man 3*n+1.
Dann teilt man so oft durch 2, bis wieder eine
ungerade Zahl m entsteht.
Dazu bildet man dann 5*m+1.
Dann teilt man so oft durch 2, bis wieder eine
ungerade Zahl entsteht. Die ist das neu n.
Mit dem geht es wieder von vorne los.

Beispiel:

1 -> 4-2-1 -> 6-3
3 -> 10-5 -> 26-13
13 -> 40-20-10-5 -> 26-13

13 ist also eine Zahl, die auf sich selbst
abgebildet wird.

Auf sich selbst abgebildet werden auch 7 und 9.

7 -> 22-11 -> 56-28-14-7
und
9 -> 28-7 -> 36-18-9

Es kann natürlich auch längere Zyklen geben, wo es erst nach
mehreren Runden zur Ausgangszahl zurück läuft.

Aufgabe: Man finde (mit Computerhilfe) viele
veschiedene Zyklen, möglichst sogar "alle".

***********************************************

Vermutung: Für jede ungerade Startzahl n gibt
es einen Zyklus, in den diese Startzahl läuft.

Das Problem ist wohl härter als das klassische 3n+1-Problem,
weil hier nicht immer mit 3 multipliziert wird,
sondern abwechselnd mit 3 mit 5.

3*5=15 < 16. Weil in jedem Halbierungs-Abschnitt
im Durchschnitt zwei Mal durch 2 geteilt wird,
sollten große Startzahlen auf lange Sicht kleiner
gemacht werden (weil 3/4 * 5/4 < 1).

Ich bin gespannt, wer was mit Computerhilfe oder anders
herausfindet.

Ingo.

AW: Das 3n+1 / 5n+1 Problem
 

Naja... wenn das Problem "härter" ist als das normale 3n+1 Problem (auch als Collatz-Problem bekannt) dann wird das wohl kaum einer lösen können. Selbst das Collatz-Problem selbst hat sich einer endgültigen Lösung bisher entzogen und gilt als eines der ungelösten Probleme der Mathematik.

Meines Wissens gibt es bisher nur eine Teillösung von Terence Tao.

https://arxiv.org/abs/1909.03562

Damit hat er sich dem Ursprungsproblem zwar angenähert, aber auch keine endgültige Lösung geliefert. Insofern dürfte auch die Erweiterung des Problems derzeit eher in die Kategorie "unlösbar" fallen.

AW: Das 3n+1 / 5n+1 Problem
 

Hallo Hartmut,

Es geht mir nur ganz mittelbar um einen formalen Beweis.
Vielmehr spekuliere ich, dass es trotz 15/16 < 1 vielleicht
Startwerte gibt, die ins Unendliche laufen oder zumindest
sehr gross werden.
Das würde dann den bei vielen vorhandenen Glauben erschüttern,
dass alles nur von den Erwartungswerten (also 3/4 < 1 ...) abhängt.

Es gibt etliche andere Teillösungen, unter anderem auch die
folgende von mir, bei der Zufall im Spiel ist:
Zu der aktuellen Zahl n bildet man entweder
3n+1
oder
3n-1
oder 3n+3
oder 3n-3,
und zwar jeden der Werte mit der gleichen
Wahrscheinlichkeit 1/4, unabhängig von früheren Interationen.
Dann halbiert man, bis man wieder ungerade ist.
Das Ganze endet, wenn man bei 0 oder 1 landet.

Ich habe einen Beweis, dass man für jeden ungeraden Startwert
n(0) mit Wahrscheinlichkeit 1 bei 0 oder 1 landet.


*******************************************

Hier ist eine einfachere Variante, ein dreistufiges Prinzip:
Aus n wird
3n+1, dann halbieren
dann wieder 3n+1, wieder halbieren
dann n+1, wieder halbieren
Man beweise, dass damit dadurch von allen Startwerten
aus zu ganz kleinen Werten gelangt.

Das ist plausibel, aber nicht trivial, weil
3*3*1 = 9 > 8 =2*2*2
Im schlimmsten Fall steigt man also mit
ganz vielen 9/8-Schritten nach unendlich auf.

In der Notation aus dem Threadtitel ist das das
3n+1 / 3n+1 / n+1 Problem.

Viele Grüße, ingo.

AW: Das 3n+1 / 5n+1 Problem
 

Hi Ingo

Auf jeden Fall ein interessantes Problem. Ich bin zum ersten Mal in meiner Studienzeit da drauf gestoßen. Das gemeine an der Sache ist, dass es auf den ersten Blick nach einer Aufgabe aussieht, die eigentlich nach einer Lösung mittels vollständiger Induktion schreit... naja... leider nur auf den ersten Blick, aber als Erstsemester hab ich tatsächlich geglaubt, es ginge so oder ähnlich.

Mal sehen. Wenn ich Zeit habe, probiere ich mit dem Rechner mal aus was da so geht...

AW: Das 3n+1 / 5n+1 Problem
 

Hallo Ingo,

Ich fand es ganz interessant, das mal auf die Schnelle zu programmieren.
Die Ergebnisse in der Liste fand ich teilweise etwas unintuitiv, vielleicht kannst du etwas dazu sagen.

- Kein Startwert divergiert (In den ersten Millionen)
- Jeder Startwert endet in einem Zyklus der entweder 5 oder 7 enthält.
- Nur sehr wenige Startwerte werden auf sich selbst abgebildet, aber auch diese Zyklen enthalten immer 5 oder 7.
- Ein wiederholter Startwert bedeutet keinen Zyklus, da für jede Zahl 2 Nachfolge Zahlen möglich sind. (?)
- Ab dem Startwert 22893989 sind auch nach längerer Berechnung keine Neuen mehr erschienen, die auf sich selbst abgebildet werden.

Hier eine Tabelle:

1. Startwert
2. Anzahl Durchgänge bis zur Wiederholung
3. Anzahl Durchgänge bis zum ersten Mal 5 oder 7 erscheint.
4. Die höchste vorkommende Zahl.


Thomas

AW: Das 3n+1 / 5n+1 Problem
 

Hallo Thomas,

danke für Dein Rechnen. Irgendwie scheinen wir verschiedene
Notationen zu haben. Bei mir ist
"*3+1, halbhalb..., *5+1, halbhalb..." eine Runde.

Da gibt es drei kurze Zyklen mit nur einer Runde:

7 -> 22-11 -> 56-7

9 -> 28-7 -> 36-9

13 -> 40-5 -> 26-13

Du scheinst einen weiteren Zyklus gefunden zu haben, der
in Deiner Notation Länge 358 hat. Wie sieht der denn aus?

Und in was läuft die "komische" 95 hinein?

**************************************

Eine Frage: Welche Arithmetik nutzt Du?
Wie gehst Du mit drohenden Overflows um?

Jürgen Dankert hat nicht für ganze Zahlen eine Speicherzelle spendiert,
sondern für jede Dezimalstelle einer Zahl. Addieren und Multiplizieren
tut er wie in Schulklasse 3 und 4.

Viele Grüße, Ingo.

AW: Das 3n+1 / 5n+1 Problem
 

Hallo, Thomas,

das fragezeichen kannst du weglassen, eine wiederholte zahl kann ja einmal bei 3n+1 und dann auch bei 5n+1 auftauchen, die fortsetzung ist also nicht identisch.

Danke für deine schnelle programmierung des problems.
Kannst du eventuell eine datei anbieten, die einige durchgerechnete zahlenreihen wiedergibt?

Viele grüße
Horst

AW: Das 3n+1 / 5n+1 Problem
 

Hallo zusammen,

anbei eine Tabelle mit erweiterter Ausgabe:

1. Startwert
2. Anzahl aller Veränderungen des Wertes bis zur Wiederholung
3. Anzahl aller Veränderungen des Wertes bis zum ersten Mal 5 oder 7 erscheint.
4. Anzahl der Runden: "*3+1, halbhalb..., *5+1, halbhalb..."
5. Die höchste vorkommende Zahl.


Ich nutze Integer Arithmetik, uint64_t entspricht unsigned integer 64 bit.
Overflows checke ich, indem ich überprüfe ob ich in der Nähe des maximalen 64 bit unsigned Integers bin:
18446744073709551615
Zur Zeit ist die Berechnung davon noch weit entfernt.

Die 95 wiederholt sich nach 320 Runden oder 1882 Veränderungen.
Das Ende (1. Counter, 2. Wert) sieht so aus (ab 0):
1881 95
1882 476
1883 238
1884 119
1885 358
1886 179
1887 896
1888 448
1889 224
1890 112
1891 56
1892 28
1893 14
1894 7

Angehängt habe ich die Datei 95.txt

Viele Grüße,
Thomas

AW: Das 3n+1 / 5n+1 Problem
 

:goldcup:

AW: Das 3n+1 / 5n+1 Problem
 

Hallo Thomas,

danke für die erweiterten Daten.

Aber nur in der Mitte einer Iteration (als nächstes
wird *5 +1 genommen).

> ...1893 14
> 1894 7

Es landet also in der "Fixrunde 7".

Viele Grüße, Ingo.