Benutzer:Pacogo7/Notizen zu Collatzfolgen

Dies sind ein paar Notizen zu Collatzfolgen bzw zum Collatz-Problem.

Ich stelle ein System von Vorgängern in Collatzfolgen vor: alle ungeraden Zahlen aus Collatzfolgen, beginnend mit 5 bzw. einer Viererpotenz.

Vorgängersystem

Anders als beim üblichen Vorgehen, dass man bei Zahlen schaut, gibt es eine Collatzfolge für diese Zahl, schauen wir umgedreht, was haben die Zahlen aus der Restklasse 5 mod 8 für Vorgänger. Daraus entstehen systematische Ordnungen.

Das Vorgängersystem führt ein (echtes oder vorgestelltes) Batchprogramm immer weiter durch:

Es arbeitet so, dass es Zeilen schrittweise mit Collatzvorgängern füllt, die links jeweils mit Zahlen der Restklasse 5 mod 8 (A004770) beginnen.

Findet es (rechts) eine durch 3 teilbare Zahl (die ja keinen Vorgänger haben), so endet die Zeile:

5, 3,
13, 17, 11, 7, 9,
21,
29, 19, 25, 33,
37, 49, 65, 43, 57,
45,
53, 35, 23, 15
61, 81
69,
77, 51
85, 113, 75
93,
...

Die Zahlen die sowohl in der Restklasse 5 mod 8 als auch durch 3 teilbar sind, stehen allein in der Zeile. (21 mod 24: 21, 45, 69, 93, 117, ...)

Erzeugendensystem

Aus diesen notierten Zahlen nehmen wir jetzt pro Zeile eine Anzahl von Zahlen heraus, aus denen wir durch Restklassen die anderen Elemente gewinnen.

Wir bilden aus einer Zahl jeweils ihren u-Vorgänger und ihren d-Vorgänger und scheiben sie eine Zeile rechts auf.

Erste linke Zeile: 5 mit Vererbung 5 mod 8.

Jede folgende Zeile weiter nach rechts enthält eine gemerkte Vorgängerzahl die mit verdoppeltem Modulo vererbt und eine mit vervierfachtem mod:

zweite Zeile: 3 mod 16 und 17 mod 32

dritte Zeile: 23 mod 32, 25 mod 64, 11 mod 64 und 65 mod 128

usw.

Dieser Exponent der Modulo-Zweierpotenz ergibt sich genau aus A119476 beginnend mit der zweiten Stelle: Also der zur 5 gehörende Zweierpotenzmodulo ist 2^3 = 8. 3 ist das zweite Folgenglied von A119476.

Vorgehen

Ich bilde zwei Vorgänger zu 5. Dabei gehe ich gemäß Collatzproblem rückwärts vor: 5*2=10 nun ziehe ich 1 ab und teile durch 3. 10-1=9 9/3=3. Der Vorgänger von 5 ist 3. Dies ist eine up-Bildung (Abkürzung u), weil 5 größer ist als 3. Jetzt will ich auch die down-Bildung (Abkürzung d) finden. 5 selber ist schon benutzt. Also addiere ich mit der zugehörigen 2er-Potenz. Sie ist 8. 5+8=13. Ich suche also einen d-Vorgänger zu 13. 13*2=26 26-1 ist 25. 25 ist nicht durch 3 teilbar. Also 13*2*2=52 und 52-1=51 und 51/3 ist 17. 17 ist der d-Vorgänger von 5.

Also hat 5 die beiden Erzeugenden-Vorgänger 3 und 17. Die u-Zahl erhält den verdoppelten mod-Wert, die d-Zahl den vervierfachten: Zweite Zeile: 3 mod 16 und 17 mod 32

Bei durch drei teilbaren Zahlen einer Zeile wird der Vorgänger mit dem nächsten Element der Restklasse gebildet.

• Beispiel u-Bildung : 3 hat keinen Vorgänger. 19 (=3+16) geht nicht für die u-Bildung, denn 2*19-1=37 ist nicht durch 3 teilbar. Also wird der Vorgänger von 35 (=3+16+16) gebildet. Es ist 23, denn 35*2-1=69 und 69/3=23. Dies ist eine u-Bildung: Der Nachfolger von 23 ist 35. Er ist größer (englisch: up). Zwischen den beiden ungeraden Zahlen ist in der Collatzfolge genau eine gerade Zahl. (Die d-Bildung geht über 19: 19*2*2-1=75. 75/3=25)

• Beispiel d-Bildung : (17 selbst hat den u-Vorgänger 11. Nämlich: (17*2-1)/3 = 11) Also wird 17+32 = 49 genommen. 32 ist ja die mod-Zahl bei 17. 49*2-1=97 ist nicht durch 3 teilbar (und das einfache mal 2 nehmen wäre nicht d-Bildung). Also 49*2*2-1=195. 195/3 = 65. Dies ist eine d-Bildung: Der Nachfolger von 65 ist 17. Er ist kleiner (englisch: down). Zwischen den beiden ungeraden Zahlen sind in der Collatzfolge genau zwei gerade Zahlen.

Allgemeines Phasenprinzip

Die genannten 'Erzeuger' von Restklassen stellen einen Binärbaum dar:

Erste Zeile, Phase 1,

• 5 mod 8

Zweite Zeile,

• 3 mod 16
• 17 mod 32

Dritte Zeile,

• 23 mod 32 (u von 3)
• 25 mod 64 (d von 3)
• 11 mod 64 (u von 17)
• 65 mod 128 (d von 17)

Phase 4, vierte Zeile:

• 15 mod 64
• 73 mod 128
• 59 mod 128
• 33 mod 256
• 7 mod 128
• 185 mod 256
• 43 mod 256
• 257 mod 512

Liste

Die Anweisungen und Bedingungen für diesen Binärbaum sind auf den ersten Blick vielleicht etwas verwirrend. Es ist aber eine fest definierte regelmäßige Abfolge. Zunächst ist es wichtig, dass die erste gefundene Zahl sowohl durch u-Bildung als auch durch d-Bildung entstehen kann. Hinterher wird die Reihenfolge dann so vertauscht, dass die u-gebildete Zahl links steht und die Restklasse mit dem kleineren Modulo bekommt. Die d-Bildung (mit zwei geraden Zahlen) erhält dann die Restklasse mit dem größeren Modulo. Dann geht alles wunderbar auf. Beispiel: 25 ist die erste gebildete Zahl: 3 (mod-Zahl=16) hat keine Vorgänger. Also probiert man den Vorgänger von 19 (=3+16) zu finden. Es ist 25 mit der d-Bildung. Gut. Nun wird die zweite Zahl gesucht. Wir probieren 35 (3+2*16). Der Vorgänger ist 23 mit der u-Bildung. Nun kommt 23 links weil u und 25 rechts weil d hin.

Man kann sie eindeutig in einem Programm umsetzen, was auch geschehen ist.

Die ersten Phasen lauten:

5

3 17

23 25 11 65

15 73 59 33 7 185 43 257

95 105 219 97 39 249 363 385 175 9 123 929 199 57 171 1025

63 297 411 481 487 633 747 129 367 393 507 1697 583 1849 939 513 287 233 347 1377 423 1529 619 3969 815 265 1403 1441 1479 1593 683 4097

383 425 539 1761 615 1913 1003 641 1007 649 1787 2209 1863 2361 1451 5633 927 489 1627 1889 1703 2041 1131 4993 1071 777 3963 2465 1991 6713 5803 6145 191 1065 155 3041 231 3193 2283 7297 1647 1929 1019 4769 3143 825 8107 10753 543 3817 2907 353 935 4601 3691 1921 2351 7433 6523 7585 455 11833 2731 16385

(weitere Zahlen in der Versionsgeschichte 26.6.2020)

Innere Folgen in A363686

Die folgenden Hinweise sind nur zur Illustration der Liste von A363686. Die folgenden Zahlenfolgen sind Stränge der Liste:

Column 1 gives A283507 starting from its third term.

Die jeweils ersten Zahlen je Phase 5, 3, 23, 15, 95, 63..., die Restklassen mit dem kleinsten Modulo erzeugen, folgen A283507. A283507 ist eine Folge mit einem ganz anderen Hintergrund. Ein Zellautomat. Wir brauchen hier nur einen Teil davon: (Es ist die Dezimalschreibweise von binären Zahlen, bei denen die erste Ziffer zwischen I und O alterniert, die zweite Ziffer immer O ist und dann nur noch Is folgen, jedes Mal ein I mehr: 23= IOIII, 15=OOIIII, 95=IOIIIII usw.) Man beachte, dass die jeweils zweite Zahl deswegen so groß ist, weil eine durch 3 teilbare Zahl vorher kam.

darauf anschließend

Die direkt darauf anschießenden Zahlen: 17, 25, 73, 105, 297, 425, 1193, 1705, 4777, 6825, ... sind die ungeraden Zahlen des Hwang-Deutsch merging algorithm A260795 (sie folgen d, du, duu, duuu, duuuu, usw.)

vorletzte Zeile

Die vorletzten Zahlen pro Phase: 3, 11, 43, 171, 683, 2731, 10923, ... sind u, ud, udd, uddd, udddd, usw. siehe A007583 = a(n) = (2^(2*n + 1) + 1)/3.

Right border gives A052539 starting from its second term.

Die Zahlen der Form 4^n + 1 (5, 17, 65, 257, 1025, 4097, 16385, 65537...) A052539, die letzten Zahlen je Phase, bilden dabei jeweils die Restklassen mit dem größten Modulo.

Note canonical

Inzwischen ist die obige Liste bei oeis angelegt und wird editiert. A363686. Dort habe ich notiert: Note: There is a canonical u-predecessor and a d-predecessor for every odd number already determined.

Es geht darum zu beweisen, dass die Folge immer (mit weniger als zwei mod-Additionen) entsprechende Vorgänger liefert.

Beweisskizze

Suche ich für eine ungerade Zahl m > 1 einen ungeraden Collatzvorgänger, so gibt es nur drei Fälle:

1. m ist durch 3 teilbar
2. m hat einen u-Vorgänger also: (m*2-1) ist durch 3 teilbar
3. m hat einen d-Vorgänger also: (m*4-1) ist durch 3 teilbar

Die Addition (m' = m + 2^n) von m mit einer Zweierpotenz erzwingt, dass diese Fälle wechseln müssen. Dies ergibt sich aus der modularen Arithmetik.

Conjecture

Conjecture: With the associated residue classes, this sequence forms a complete decomposition of the odd integers. In other words: If we form the complete residue classes to each number from this sequence, then all odd numbers > 1 occur once.

Remark

Remark: Even if it can be shown that every odd integer can be transformed by a Collatz sequence into a number equivalent to 5 mod 8, this does not mean that the sequence already ends immediately in the 4-2-1 cycle. For example, T(4, 2) = 73 is transformed into 125, but then jumps up again to T(14, k) = 47.

Vollständige Abdeckung

Schreiben wir die Liste, also den Binärbaum von A363686, komplett mit allen Restklassen zum jeweiligen Modulus hin, so sind alle Zahlen (nach unten) jeweils Anfänge von Collatzfolgen bis zur 5 mod 8-Ebene.

Außerdem haben alle nicht durch 3 teilbaren Zahlen (nach oben) einen Vorläufer im Binärbaum selbst.

Beispiel mit dem in die linke Spalte geschriebenen Ausschnitt der Folge 9, 7, 11, 17, 5:

• 9 521 1033 1545 2057 2569 3081 3593 4105 ... Phase 5, 9 hat Modulo 512
• 7 135 263 391 519 647 775 903 1031 ... Phase 4, 7 hat Modulo 128
• 11 75 139 203 267 331 395 459 523 587 ... Phase 3, 11 hat Modulo 64
• 17 49 81 113 145 177 209 241 273 ... Phase 2, 17 hat Modulo 32
• 5 13 21 29 37 45 53 61 69 ... Phase 1, 5 hat Modulo 8

521 (rechts neben der 9) der fünften Phase hat als Nachfolger 391 (rechts neben der 263) der vierten Phase und 587 (ganz rechts dritte Zeile) der dritten Phase.

Nachfolger 5 mod 8

Ich füge hier nun wieder eine ältere Bemerkung ein, die eine Art Systematik jenseits der Grenze ausmacht.

Nachfolger der 5 mod 8-Zahlen

Die Nachfolger der 5 mod 8-Zahlen enden gemäß A075677 (Folge von T. D. Noe).

Schreibt man in die erste Spalte einer Tabelle die Restklasse 5 mod 8 hinein und in die zweite Spalte die Zahlen von A075677, so bildet die zweite Spalte die ungeraden Collatznachfolger der ersten:

5 1
13 5
21 1
29 11
37 7
45 17
53 5
61 23
69 13
77 29
85 1
93 35
usw.

Diese ungeraden Nachfolger lauten: 1, 5, 1, 11, 7, 17, ... gerade indizierten Zahlen: 5, 11, 17, 23, entwickeln sich gemäß A016969: a(n) = 6*n + 5. Die ungerade indizierten Zahlen gemäß A067745.

Die Folge (A075677) ist in sich verschlungen, nimmt man ab dem dritten Folgenglied (Index in der Klammer: a(3)=1) immer jedes vierte (a(7)=5, a(11)=1 usw.) , so ergeben sich die Folgenglieder der Folge selbst.

Vorgänger in A075677

Die 5 mod 8 Vorgänger der Zahlen in A075677 lassen sich jeweils mit verschiedenen Anfängen durch a(n) = 4*a(n-1) + 1 erzeugen, wobei das erste Folgenglied beim ersten Vorkommen der Zahl aus A075677 jeweils ausnahmsweise noch kein 5 mod 8 Vorgänger ist.

Beispiel: Der direkte Vorgänger von 11 ist 7. Der erste 5 mod 8 Vorgänger von 11 ist 29. Die 5 mod 8 Vorgänger von 11 sind gemäß A072261: 7, 29, 117, 469, 1877, 7509, 30037, 120149, ... Die Anfangszahl a(1) ist hier 7.

In der linken Spalte sind die Zahlen von A075677. Es ergeben sich die Anfangszahlen für die 5 mod 8 Vorgänger in der rechten Spalte als die ungeraden Zahlen in Zweierschritten (A005408):

1 1 (Vorgänger von 1: A002450: a(n) = 4*a(n-1) + 1, a(1) = 1)
5 3 (Vorgänger von 5: A072197: a(n) = 4*a(n-1) + 1, a(1) = 3)
1 5 (Vorgänger von 1: A002450: a(n) = 4*a(n-1) + 1, a(1) = 5)
11 7 (Vorgänger von 11: A072261: a(n) = 4*a(n-1) + 1, a(1) = 7)
7 9 (Vorgänger von 7: A206374: a(n) = 4*a(n-1) + 1, a(1) = 9)
17 11 (Vorgänger von 17: A072262: a(n) = 4*a(n-1) + 1, a(1) = 11)
5 13 (A072197, a(1) = 13)
23 15 (A072201)
13 17 (A330246)
usw.

Gegenüberstellung

Es gibt eine interessante Folge von Wolfdieter Lang, oeis:A347840, die die Vorgänger von A075677 auflistet.

Schreibt man die 5 mod 8 Restklasse in die Mitte, so ergibt sich folgende Vorgänger/Nachfolger-Tabelle

Vorgänger/Nachfolger-Tabelle

A075677 / 5 mod 8 / A347840 / unger.
1	5	1	1
5	13	3	3
1	21	1	5
11	29	7	7
7	37	9	9
17	45	11	11
5	53	3	13
23	61	15	15
13	69	17	17
29	77	19	19
1	85	1	21
35	93	23	23
19	101	25	25
41	109	27	27
11	117	7	29
47	125	31	31
25	133	33	33
53	141	35	35
7	149	9	37
59	157	39	39
31	165	41	41
...	...	...	...

Die 3. Spalte ist der Listenvorgänger der 1. Spalte, die 2. Spalte ergibt den 5 mod 8-Vorgänger der 1. Spalte.

Argumentation für einen Beweis der Collatzvermutung

Die Argumentation für einen Beweis der Collatzvermutung ist hier: Benutzer:Pacogo7/Überlegungen_zur_Collatzvermutung ausgelagert.

Basierte Stufen von Ebenen 5 (mod 8)

Ebenen

Es sollen nun Ebenen oder Stufen gebildet werden, um den Abstand der Zahlen == 5 (mod 8) von den basierenden Nachfolgern
zu kennzeichen:

• Ebene 0: direkte Vorgänger zu 1: 5, 21, 85, 341, 1365 ... (vgl. auch A002450, A238192)

• Ebene 1: direkte Vorgänger zu Ebene 0:
  • 13, 53, 213, 853, 3413, 13653, 54613, 218453, ... (Vorg. 5: A072197)
  • 453, 1813, 7253, 7281, 29013, 29125, 116053, ... (Vorg. 85: A342816)
  • 909, 3637, 14549, ... (Vorgänger 341)
  • ...

• Ebene 2: direkte Vorgänger zu Ebene 1

• ...

Zu beweisen wäre hier, dass dies eine vollständige Abdeckung der Zahlen == 5(mod 8) darstellt.

Mit anderen Worten: Zu beweisen wäre, dass jeder Zeile in der obigen Gegenüberstellung eine dieser Ebenen
zuzuordnen ist.

A252829

Der quadratisch offene Table A252829 von R. H. Hardin ist eine Hilfe für die genannte Ebenenbildung. Die Hauptdiagonale "\" ist die oben genannte Ebene 0, also A002450. Neue Spalten und Zeilen entstehen durch Addition mit Viererpotenzen (A000302):
Also ist zB T(3,4) = 37, weil 21 + 4² = 37.

Eine Paralleldiagonale T(1,3), T(2,4), T(3,6) ... besteht aus der ersten Zeile von Ebene 1: (3,) 13, 53, 213. (Vorgänger von 5: A072197)

Die Folge A067745 (auch A176672) kann als Anfangselement für die Diagonalen genommen werden, fungiert (ohne die erste nummerierende Zeile) also jeweils als Collatz-Generalnachfolger für die ganze Diagonale.

Also wir fügen A067745 als erste Zeile in A252829 hinzu:

7, 5, 13, 1, 19, 11, 25, 7, 31, 17, 37, 5, 43, 23, 49, 13, 55, 29, 61,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
2, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, ...
3, 9, 21, 37, 53, 69, 85, 101, 117, 133, 149, 165, 181, 197, 213

Die neunte Diagonale (hier jetzt: 31, [10], 41, 165, 661) liefert beispielsweise die Collatz-Vorgänger von 31.

Spielbrett

Man kann die (um A067745) erweiterte Tafel A252829 wie ein Spielbrett nutzen. Erlaubte Sprünge sind solche, die zu Tabellenzellen führen, die direkte Collatzvorgänger der Startzelle sind. Bei jeder Ebene werden die Sprungregeln erweitert.