Zum 3n+1-Problem

By Volker Pittlik Date 2023-06-15 06:57

Hallo Herr Althöfer,

zu dem Problem habe ich schon vor einiger Zeit dieses Video gefunden:

https://youtu.be/094y1Z2wpJg ,welches ich für sehr interessant halte.

Dass Collatz in Peenemünde gearbeitet hatte, wusste ich nicht, auch "Mercedes-Euklid-Rechner" wren mir bisher nicht bekannt.

Freundliche Grüsse

Volker Pittlik

By Ingo Althöfer Date 2023-06-15 09:00

Lieber Herr Pittlik,

danke für den Hinweis auf das Video, was technisch
sehr schön gemacht ist.

Am Anfang steht im Video der Hinweis, junge Mathematiker würden
gewarnt, ihre Zeit damit zu verdaddeln. Die Warnung gibt es oft; aber
unter seriöser Betreuung macht eine Beschäftigung mit dem 3n+1-Problem
durchaus Sinn für Mathestudenten. Ich habe zum Beispiel schon halbe
Vorlesungs-Semester (Titel "Mathematische Spiele und Puzzles") zusammen
mit Studenten an dem Problem gearbeitet. Man lernt viel dabei.

Eines meiner einfach zu formulierenden Ergebnisse ergab sich für eine
stochastische Variante des Problems:
Wenn die aktuelle Zahl n gerade ist, wird sie durch 2 geteilt.
Ist sie aber ungerade, wird entweder 3n-3 oder 3n-1 oder 3n+1 oder 3n+3 gebildet,
und zwar jedes mit Wahrscheinlichkeit 1/4, unabhängig von früheren Zufalls-
entscheidungen. In diesem Modell kann man zur 0 gelangen (3*1-3=0).
Aus der 0 kommt man nicht wieder hinaus.

Theorem (Althöfer 2017): Egal, mit welcher Zahl n(0) begonnen wird, endet
dieser Prozess mit Wahrscheinlichkeit 1 in der 0.

Im Video wird Paul Erdos genannt mit dem Zitat, die Mathematik sei noch
nicht reif für das 3n+1-Problem. Es gibt ein Foto aus dem Jahr 1985, was
Erdos mit dem damaligen mathematischen Wunderkind Terence Tao zeigt.
Tao schaffte im Herbst 2019 einen großen Schritt vorwärts beim 3n+1-Problem:
"Almost all orbits of the Collatz map attain almost bounded values."

Meine persönliche Meinung:
* Ich schätze die Chance, dass die Collatz-Vermutung bis 2037 (100-jähriges
Jubiläum des Problems) bewiesen ist, auf 25 %.
* Ich schätze die Chance, dass die Collatz-Vermutung bis 2050 bewiesen ist,
auf 50 %.
* Ich glaube, dass meine Chance auf einen wesentlichen Beitrag zur Lösung
des 3n+1-Problems bei 5-10 Prozent liegt.

Eine tragische Figur beim 3n+1-Problem war der Collatz-Schüler Prof. Gerhard Opfer
(1935-2020). 2011 (also als älterer Herr) glaubte er, einen Beweis für die Collatz-
Vermutung gefunden zu haben. Er publizierte im Mai 2011 ein Preprint (34 Seiten)
mit Beweis, in dem mehrere Leute (auch ich) eine Lücke fanden. Ich bot ihm
daraufhin eine Wette mit Stichtag 15. Juni 2011 an (mit Quote 1:100):
Ich müsste ihm 10.000 Euro bezahlen, wenn sein Beweis sich als richtig heraus
stellte, und er mir 100 Euro, wenn es eine Lücke gäbe. Er schrieb zurück, er
würde nicht wetten. Ich sollte ihm lieber die Stelle zeigen, wo ich eine Lücke
vermuten würde. Das tat ich nach dem Stichtag meines Wettangebots. Daraufhin
änderte er sein Preprint auf den Seiten 1 und 2 (ganz einfach zu lesen):
https://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf

Im Februar 2020 starb Herr Opfer nicht an Collatz, sondern an Corona.

Volker Pittlik schrieb:

... Dass Collatz in Peenemünde gearbeitet hatte, wusste
ich nicht, auch "Mercedes-Euklid-Rechner" wren mir bisher nicht bekannt.

Collatz hat nicht in Peenemünde, sondern an der TH Darmstadt für das Peenemünde-
Projekt gearbeitet. Die Darmstädter Beteiligten am V2-Projekt lassen sich in
drei Gruppen einteilen:

(i) Die, die irgendwann ganz nach Peenemünde wechselten.
(ii) Die, die immer mal wieder tageweise nach Peenemünde kamen.
(iii) Die, die "immer nur" von Darmstadt aus mitmachten.

Collatz gehörte zur Gruppe (iii), wie mir im Herbst 2019 der damals
107-jährige (!) Entwickler Wilfried de Beauclair im Gespräch bestätigte.
Collatz habe sich standhaft geweigert, Peenemünde auch nur für einen
Tag zu besuchen. Trotzdem waren seine Beiträge zur V2-Balistik wesentlich.

Freundliche Grüße, Ihr
Ingo Althöfer.

By Frank Brenner Date 2023-06-27 16:00 Upvotes 1

Ingo Althöfer schrieb:

Theorem (Althöfer 2017): Egal, mit welcher Zahl n(0) begonnen wird, endet
dieser Prozess mit Wahrscheinlichkeit 1 in der 0.

Hallo Herr Althöfer,

die stochastische Herangehensweise finde ich sehr spannend.

Die kürzeste Beweisskizze, die mir eingefallen ist, lautet:

Die niedrigsten 3 Bits der Werte { 3n-3, 3n-1,3n+1,3n+3} lauten { 000,010,100,110 }

Von diesen vier Werten wird eine - zufällig und gleichverteilt - ausgewählt.

Dadurch erzielen wir im Durchschnitt eine Reduktion um den Faktor viertewurzel(1/8 * 1/2 * 1/4 * 1/2 } = 0,297...
Diese Zahl nehmen wir mit 3 mal (wegen 3n+x), ergibt: 0,8919
Um also die Zahl n um den Faktor 0,8919... zu verkleinern sind im Durchschnitt 1+ (3+1+2+1)/4 = 2,75 Schritte nötig.

(also 1x malnehmen mit 3 und hinterher im Durchschnitt 1,75 Divisionen durch zwei)

Wenn angenommen werden könnte, daß vor den "000" beliebige Bits stehen, dann kann man also im Durchschnitt eine weitere Division durchführen (1*1/4 + 2*1/8 + 3*1/16 .. = 1 )
Das führt dann im Durchschnitt zu einem Faktor von viertewurzel(1/16*1/2*1/4*1/2) = 1/4, mal 3 für 1+(4+1+2+1)/4 = 3 Schritte, also Faktor 3/4 für 3 Schritte

-3/log(3/4)

Bei der stochastischen Collatzfolge erhalten wir also im Durchschnitt nach ca. 24 Schritten eine Verkleinerung des Folgenelementes um eine Stelle (im Zehnersystem)

Bei der normalen Collatz Folge wird dagegen nicht zufällig ein Wert ausgewählt, sondern die Wahl wird vom aktuellen Wert von n bestimmt.

Tatsächlich gibt es Bitmuster von n die so hartnäckig sind, daß sich mit 3n+1 deutlich häufiger die Werte "010" und "110" für die drei niederwertigsten Bits ergeben.

Beispiel:

Lauter binäre 1en: 2^66438-1 hat 20.000 Stellen

Hier benötigt die 3n+1 Folge nicht 24*20.000 = 480.000 Schritte sondern fast doppelt so viel: 891.093
480.000 Schritte wären es wenn alle vier Fälle (000 010 100 110) gleichhäufig gewählt würden, so wie bei der stochastischen Collatzfolge.

nach 1/8 der Schritte, also nach 11386 Schritten lautet der Zwischenstand:
-------Das Bitmuster '000' trat 0 Mal auf.
-------Das Bitmuster '010' trat 0 Mal auf.
-------Das Bitmuster '100' trat 0 Mal auf.
-------Das Bitmuster '110' trat 55693 Mal auf.

nach 1/2 der Schritte
Länge des Folgendgleids: 18649 Stellen
-------Das Bitmuster '000' trat 26271 Mal auf.
-------Das Bitmuster '010' trat 26001 Mal auf.
-------Das Bitmuster '100' trat 25781 Mal auf.
-------Das Bitmuster '110' trat 92571 Mal auf.
Nach der Hälfte der Schritte ist die Zahl kaum kleiner geworden aber nun ist sie so gut wie "zufällig" und für den Rest benötigt es dann ca. 24* 18649 Schritte

Am Ende nach 891093 Schritten ergibt sich folgende Verteilung

Das Bitmuster '000' trat 26271 + 37.000 Mal auf.
Das Bitmuster '010' trat 26001 + 37.000 Mal auf.
Das Bitmuster '100' trat 25781 + 37.110 Mal auf.
Das Bitmuster '110' trat 92571 + 36.948 Mal auf.

2^n-1 , also binäre 1er Folgen sind bekannte hartnäckige Startwerte, aber bei weitem nicht die schrecklichsten Startwerte.

Im Netz habe ich eine sehr fürchterliche Startzahl gefunden, leider eine sehr kleine und ohne Konstruktionsregel für beliebig große Werte. Sie lautet:
7219136416377236271195

Die Collatz Folge benötigt für diese 22 Stellige Zahl nicht 24*22 (bei zufäligen Startwerten) und auch nicht 44*22 (bei binären 1er Folgen), sondern 134 * 22 Schritte!
Die Anzahl der benötigten Schritte beträgt: 2968
Das Bitmuster '000' trat 181 Mal auf.
Das Bitmuster '010' trat 262 Mal auf.
Das Bitmuster '100' trat 248 Mal auf.
Das Bitmuster '110' trat 429 Mal auf.

Grüße
Frank Brenner

By Ingo Althöfer Date 2023-06-15 18:42

Hallo Herr Pittlik,

jetzt, wo das Zertifikatsproblem des CSS-Forums gelöst scheint,
schreibe ich noch eine zweite kurze Antwort.

Volker Pittlik schrieb:

auch "Mercedes-Euklid-Rechner" wren mir bisher nicht bekannt.

In der Serie gab es seit Mitte der 1930er Jahre auch welche
mit Strombetrieb. Spannend wurde es, als solche Euklid-
Rechner auch dividieren durften. Da war immer die Gefahr
mit dem Teilen durch 0. Es gab eine Extra-Taste zum Auskuppeln,
wenn versehentlich durch 0 dividiert worden war.

Die Rechnerinnen (junge Damen, "Walthers Harem") in Alwin Walthers
Institut für Praktische Mathematik teilten aber absichtlich durch 0,
liefen die Kisten heißlaufen und toasteten darauf ihr Frühstücksbrot.

Dazu hatte ich Ende 2022 mal eine Kurzgeschichte publiziert:
"Die Null und die Unvernunft"
http://schreiblust-verlag.de/mitmach-projekt/schreibaufgabe-dezember-2022/die-null-und-die-unvernunft-eine-wahre-geschichte

Viele Grüße, Ihr
Ingo Althöfer.

Volker Pittlik

By Olaf Jenkner Date 2023-06-15 23:15 Edited 2023-06-15 23:21 Upvotes 1

Wolfram Bernhardt schrieb:

Der gesamte N-Raum erblüht quasi aus 1. Fand ich eine sehr schöne Vorstellung.

Da wären wir wieder beim Schach, wo auch tolle Mattstellungen aus dem Nichts erblühen können:

Wolfgang Dittmann 2003

#1 vor 10
VRZ, Typ Proca
Anticirce, Typ Cheylan

Mattstellung

Hier kann die Lösung nachgespielt werden:
https://pdb.dieschwalbe.de/P1067390
https://pdb.dieschwalbe.de/P1394252
Bei der zweiten Aufgabe stehen am Schluß sogar acht Steine auf dem Brett.

Für Ungeübte ist es am Anfang etwas schwierig, die Lösung zu verstehen.
Verteidigungsrückzüger heißt, daß Weiß Züge zurück nimmt bis er zu einer Stellung kommt,
die die Anschlußforderung erfüllt. Hier wäre das Matt in einem Zug.
Schwarz darf auch beliebig seine Züge zurücknehmen, um das zu verhindern. Weiß spielt
also so rückwärts, daß Schwarz gar nichts anderes übrig bleibt als so zu spielen, wie
Weiß das möchte.
Damit es nicht zu einfach wird, kommt noch eine besondere Schachregel hinzu:
Bei einem Schlagzug bleibt der schlagende Stein nicht stehen, sondern wird auf sein
Ausgangsfeld derselben Farbe (bei Bauern derselben Linie) gesetzt. Ist dieses
Feld besetzt, dann ist der Zug nicht erlaubt. Daher funktioniert auch das seltsame Matt
mit den sich berührenden Königen.
Die Unterschiede zwischen Typ Proca und Hoeg bzw. zwischen Typ Cheylan und Calvet
erkläre ich jetzt nicht.

By Ingo Althöfer Date 2023-06-16 10:19 Upvotes 1

Hallo Wolfram,

Wolfram Bernhardt schrieb:

... Meine Idee war eine generative: Wenn alle Zahlen in N
auf (4,2,) 1 hinauslaufen, müssen sich durch umgekehrte Anwendung der
Regeln aus 1 auch alle Zahlen in N erzeugen lassen. Der gesamte N-Raum
erblüht quasi aus 1. Fand ich eine sehr schöne Vorstellung.

Und wenn man das für ein paar Zahlen zeigen kann, könnte man das vielleicht
induktiv für alle... naja und so weiter... aber auch auf die Idee sind schpn ganz
andere gekommen, da bin ich sicher.

so ist es. Auch das japanische Fernsehteam hatte mir solch ein Aufblüh-Diagramm
hingelegt, und ich sollte etwas dazu sagen

Einen Beweis hat damit bisher niemand gefunden.

Viele Grüße, Ingo.