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

Hallo Thomas,
danke für das Rechnen.

Deine Beobachtungen passen in das allgemeine Schema.
Und vielleicht findet sich für 5n+-1 wegen seiner Glattheit
sogar ein Beweis der Konvergenz gegen 1 oder 7.

Zur Erinnerung für alle:
* Beim klassischen 3n+1-Problem gab es schon starke Ausreißer,
wo also die Folge lange umhersauste und zwischendurch auch
sehr grosse Werte annahm.

* Beim 3n+1/5n+1 waren die Ausreißer und grossen Werte
noch extremer.

3n+1 hat nach jedem *3-Schritt im Durchschnitt zwei Halbierungs-
schritte, pro Runde also im Schnitt eine Reduzierung um Faktor 3/4.
3n+1/5n+1 hat in jeder Runde *3*5 und dazu im Durchschnitt
zwei + zwei Halbierungsschritte; pro Runde also im Schnitt eine
Reduzierung um Faktor 15/16. Das ist größer als 3/4, aber noch
kleiner als 1.

5n+-1 hat nach jedem *5-Schritt mindestens zwei Halbierungsschritte,
im Durchschnitt aber 3 Halbierungsschritte, die sich ergeben aus
2 Schritte mit 1/2
3 Schritte mit 1/4
4 Schritte mit 1/8
5 Schritte mit 1/16
Die 3 ergibt sich als als gwichtete Summe aus den Einzelfällen.
5/8 < 3/4 < 15/16 < 1, also sollte 5n+-1 das glatteste
Reduzieren haben.
Andererseits würde der Worst Case: nach jedem *5 nur zwei
Halbierungsschritte ein beliebig grosses Ansteigen erlauben.

**************************************
Für mögliche Beweise scheint mir:
Ein Beweis für 3n+1 würde ziemlich sicher einen Beweis für 5n+-1
nach sich ziehen. Im Gegensatz könnte es einen Beweis für 5n+-1
geben, der nicht "fast-automatisch" einen 3n+1-Beweis nach sch zieht.

Viele Grüße, Ingo.

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

Mir ist jetzt eine allgemeine Vermutung klar geworden.
Betrachtet wird ein System, was auf ungeraden Zahlen
k(1), k(2), ... k(s) basiert. Dabei ist s eine natürliche Zahl
ungleich 0.

Es wird bei einer ungeraden natürlichen Zahl n losgerechnet.
Jede Runde hat s Etappen.
1. Aus n wird k(1)*n +1. Dann wird runterhalbiert.
2. Sei m das Ergebnis der vorherigen Etappe. Bilde k(2)*m +1
und halbiere dann runter.
...
Etappe s: Sei r das Ergebnis der vorherigen Etappe. Bilde
k(s)*r + 1 und halbiere runter.

Das Ergebnis ist der Ausgangswert der nächsten Runde.



Sei B= k(1) * k(2) * ... * k(s).
Der entscheidende Wert ist jetzt C = B / (4^s).

Vermutung:
Ist C < 1, läuft jeder Startwert in einen von endlich vielen Zykeln.
Ist C > 1, läuft fast jeder Startwert (im Sinne von asymptotischer Dichte 1)
nach unendlich.
C=1 kann nicht vorkommen, da B ungerade sein muss.

Begründung: Runterhalbieren besteht im Durchschnitt aus zwei Schritten.
Gleichzeitig wird in einer Etappe mit k(i) multippliziert. Also liefert die
Etappe im Schnitt Faktor k(i) / 4.

Beispiele:
s=1 und k(1)=3 ist der klassische Collatz-Fall.
s=2 und k(1)=3, k(2)=5 steht oben im Thread, von Gilgamesch gerechnet.

Allgemein dürften Instanzen mit kleinem C-Wert schnelles Abstürzen
in die Zykel geben, und C-Werte nahe 1 ganz langsames. Ein vermutetes
Beispiel mit sehr hohen Zwischenwerten
s=3, k= (3,3,7). Dafür ist der C-Wert
3*3*7 / 64 = 63/64.

Viele Grüße, Ingo.

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

Hallo Ingo,

die Vermutung ist wohl genau so richtig.

Ich hatte gewisse Schwierigkeiten bei der Berechnung von (3,3,7) und mußte auf einen unsigned Integer Wert mit 256 Bit wechseln.
Auf jeden Fall scheinen alle Werte in einen Zyklus mit einem kleinem Fixpunkt zu laufen.
Die höchsten Werte können aber gelegentlich sehr groß werden, bei dem Startwert 2799 ist selbst mit 256 Bit Schluss.

Einige Beispiele, Spalten:
- Startwert
- Runden zum Erreichen des Fixpunktes (stimmt nur ungefähr)
- Schritte zum Erreichen des Fixpunktes (stimmt nur ungefähr)
- Fixpunkt (kleinster vorkommen Wert der sich wiederholt)
- Höchster vorkommender Wert

Viele Grüße,
Thomas

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

Hallo Thomas,
danke für das Rechnen.

Das Zwischen-Maximum für 1655 ist ja echt beeindruckend gross.
Und daneben dann so bescheidene Verläufe für 1657 und 1659..

Dank und Gruß, Ingo.

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

Anbei ein Zip File mit der langen 1655 - (3,3,7) Folge.
Etwas Auffälliges ausser der Länge kann ich nicht erkennen.

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

Hallo Thomas,
danke für die Daten.

Aber das reicht doch schon. Ich habe mal bei Schritgröße 2
drei Screenshots gemacht: vom Anfang der Folge, irgendwo
aus der Mitte, und am Schluss. Natürlich erkennt man da die
Ziffern nicht mehr, aber die Längen der Zahlen.

Man sieht die Ähnlichkeit zu einem Casino mit "positivem
Erwartungswert", wo in jeder Runde log(3) bzw log(7) zu
zahlen ist und dann zufällig ein Gewinn von log(2) oder
2*log(2) oder 3*log(2) oder ... ausgezahlt wird, so ähnlich wie
bei den Gewinnleitern der Gauselmann-Geldautomaten.
(Wobei natürlich die Gauselmann-Automaten aus Sicht der
Spieler einen negativen Erwartungswert haben.)

Die große Länge der Folge zeigt, dass man auch bei gutem
Erwartungswert (hier 63/64 < 1) manchmal lange Durststrecken
überwinden muss, eher man wirklich ins Plus kommt.

Dank und Gruß, Ingo.

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

Jetzt werden die Zahlen wirklich groß.

Ich hatte schon länger nach einer C++ Library gesucht, die beliebig große natürliche Zahlen zulässt und endlich eine nicht zu komplexe Implementierung gefunden.
Damit habe ich die Overflows der 256 Bit Variante (3,3,7) nochmal überprüft.

Ergebnis:


Grüße,
Thomas

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

Hallo Thomas,

abgefahren!
Wenn das der alte Collatz noch erlebt hätte.

Interessant ist der Quotient Schritte / Runden.
Bei 2799 ist er 8,971;
bei 14975 ist er 8,972.

8,97 circa= 9, und das passt gut.
In jeder Runde drei *-Schritte und durchschnittlich
sechs Halbierungen.

Mit Dank und Gruss, Ingo.

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

Vielen dank, Thomas!
Mathematik von ihrer schönsten seite!

Viele grüße
Horst

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

Hallo Horst, hallo Thomas,

die Zahl ist schon monströs gross. Nur bei Primzahlen der
Form 2^m - 1 habe ich bisher größere Zahlen erlebt.


Vielleicht liefert folgende Variante des
Collatz-Problems noch grössere Zahlen für
kleine Startwerte:

n+1 / 3n+1 / 5n+1 / 17n+1
dazwischen jeweils runterhalbieren.
Also hat jede Runde vier Etappen.

Der Clou ist das Produkt 1*3*5*17 = 255.
255 / (4^4) = 255 / 256, also nur ganz knapp unter 1.

Spekulation: Es sollte 3- oder 4-stellige Startwerte
im Dezimalsystem geben, bei denen zwar Konvergenz eintritt,
aber zwischendurch mit 400-stelligen Werten.

Viele Grüße, Ingo.

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

Moin, Ingo

da werden wir Thomas eine eigene windstromtrasse von der Nordsee aus legen lassen müssen, denn nach deinem prinzip kann man die zyklen immer weiter ausbauen.
Es macht aber enorm spaß in den zahlenreihen zu stöbern, zumal ich mit Q-Basic nicht weit gekommen bin. :o

Viele grüße auch an Thomas
sendet Horst

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

Hallo Horst,

Ich habe einen anderen Kumpel in der Szene, wo Raumfahrt-
Trajektorien berechnet werden. Es ist Dr. Dietmar Wolz.

https://althofer.de/space-trajectories.html

Als er vor einigen Jahren mal wirklich sehr arg gerechnet hat,
habe ich Dietmar 707,- Euro Stromgeld überwiesen. Das war ein
Monatsverbraucht von ihm.


Tipp: Mach die Arithmetik wie in der Grundschule,
für jede Ziffer eine Speicherstelle. Damit solltest Du
zumindest 3n+1 5n+1 für 95 hinkriegen.

Der Experte Jürgen Dankert hat es übrigens in seinem
Collatz-Applet genau so gemacht.
https://www.juergendankert.de/spezma.../collatzm.html
Da kann man Zahlen mit beliebig vielen Stellen eingeben.

Viele Grüße, Ingo.

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

Hallo zusammen,

die (1,3,5,17) Sequenz verhält sich wirklich ungewöhnlich.
Über weite Strecken (z.B. 4000 Werte) geht die Sequenz recht schnell zu einem (niedrigen) Fixpunkt bzw. einer Wiederholung über, ohne dabei extrem hohe Wert zu erreichen.
Ab und zu "explodiert" die Sequenz aber regelrecht und erreicht extrem hohe Schrittzahlen und Werte.

Das Verhalten könnte vielleicht auch mit der sogenannten "Glide" Funktion bzw. mit den "Modular restrictions" zu tun haben.
Für viele Startwerte fällt eine Sequenz (egal welche, d.h. auch die normale Collatz Sequenz) in wenigen Schritten unter den Startwert.
z.B. für (Startwert mod 256) fallen viele Restklassen (immer) fast sofort unter den Startwert und sind deswegen nicht interessant.


Viele Grüße, Thomas

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

Hallo Thomas,

Hammer! Einfach nur Hammer!

Aus Neugier frage ich mal: wieviel Rechenzeit
auf welcher Hardware hast Du für das 1-3-5-17-
Problem investiert?

Restlos begeistert, Ingo.

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

Hallo Ingo,

so groß war der reine Rechenaufwand gar nicht mal, die Library scheint recht gut optimiert zu sein.
Ein Durchlauf einer solchen langen Sequenz hat etwas über 8 Minuten auf einem CPU Core gedauert.

Ich habe einen Haswell Core i7-4790K @ 4.00 GHz benutzt.
8 Minuten / 2.000.000 Steps => 960.000 Takzyklen / Schritt
Da die Zahlen mühelos in den first Level Cache der CPU (32 KB) passen, kommt man mit 960.000 Takzyklen pro Schritt offenbar hin.

Insgesamt habe ich dann ca. 12 Durchläufe gebraucht bis alles gepasst hat, also 96 Minuten Rechenzeit auf einem Core.
Da würde auf den schnelleren Rechnern und mit Multi Tasking noch mehr gehen.
Das Anpassen des Sourcecodes und Kontrollieren der Ausgabe ist da aufwendiger, geht aber alles noch in vertretbarer Zeit.


Viele Grüße, Thomas

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

Hallo,

an dem 3n+1 Problem sitze ich ja seit 2011
immer wieder mal. Jetzt habe ich mich dazu
durchgerungen, ein paar Preise für theoretische
Beweise auszusetzen:

https://www.althofer.de/collatz-prizes.html

Die sind natürlich nicht nur für Leute aus diesem
Forum gedacht, aber eben auch.

Laufzeit der Preise bis Ende 2037.

Frohes Probieren,

Ingo.

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

Hallo,

gerade habe ich im Internet gefunden, dass es ein jabanisches KI-
Startub-Unternehmen gibt, was im Juli 2021 einen 120-Millionen-
Yen-Breis für die Lösung des klassischen Collatz-Broblems bis
Juli 2031 ausgesetzt hat. Die 120 Mio Yen entsbrechen etwa
800.000 US-Dollar, wogegen mein 1.000-Euro Breis bis
Ende 2037 natürlich Beanuts ist.

Hier die Webseiten des Breises und der Firma:
https://mathprize.net/posts/collatz-conjecture/
https://bakuage.com/en/
https://bakuage.com/en/about/index.html

Als Kabital der Firma sind 3 Mio Yen angegeben, also circa
nur 20.000 US-Dollar. Ich kenne mich mit den jabanischen
Marktregularien nicht aus, aber wenn es eine GmbH mit nur
circa 20.000 US-Dollar Einlage wäre, dann sollte sich ein
Löser des Broblems nicht zu viel Hoffnungen machen, dadurch
knabber Dollar-Millionär zu werden.

Viele Grüße, Ingo.

Zum Vergleich die Regeln meines bescheidenen Breises:
https://www.althofer.de/collatz-prizes.html

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

Hallo,

Ende November 2023 war die Tagung "Advances in Computer Games 2023",
bei der ich Ergebnisse von Michael Hartisch, Thomas Zipproth und mir
vorstellen durfte.

Die Tagung war onlline. Jetzt hängen alle Vorträge und Diskussionsteile
bei Youtube online, unter
https://www.youtube.com/playlist?lis...hOINjLHeuf9q7-

Die Präsentation zum 3n+-1-Spiel und zum 3n+1 / 5n+1 Problem
findet sich in den ersten 22 Minuten des Videos von Tag 3:
https://www.youtube.com/watch?v=-BWh...uf9q7-&index=9

Chairman der Sitzung war Bruno Bouzy, was die Gelegenheit gibt, direkt
nebeneinander französisches und westfälisches Englisch zu hören.
Keine Angst: Brunos und mein Englisch ist einfach, und der Grossteil
des Textes findet sich auch auf den gezeigten Folien.

Viele Grüsse, Ingo.