#21
02.08.2023, 21:13
|
|||||||||||
|
AW: Das 3n+1 / 5n+1 Problem
 Zitat von dreihirn
Aus Interesse frage ich mal: Was liefert das BASIC-Programm denn für Ergebnisse für das 15n+1/n+1 -Problem? Gibt es da auch so abgefahrene kleine Startwerte wie die 95 bei 3n+1/5n+1 ? Neugierige Grüße, Ingo. Mein Post sollte nur helfen, den Code besser zu verstehen, da FreeBasic und Pascal als imperative Sprachen teilweise besser zu verstehen sind, wenn man in der C-Programmierung nicht so drin ist. Geht mir jedenfalls so.
__________________
Mein Profil beim ICCF (International Correspondence Chess Federation) https://www.iccf.com/player?id=89948&tab=3 
|
#22
02.08.2023, 21:32
#23
02.08.2023, 23:26
|
|||||||||||
|
AW: Das 3n+1 / 5n+1 Problem
Hallo Ingo,
diese Folge scheint wesentlich interessanter zu sein als die andere. Es gibt bis jetzt die Fixpunkte: 1, 3, 5, 9, 31, 507 Der erste Overflow erfolgt bei 1799 Anbei wieder Code + Liste. Ein Auszug aus der Liste: 1. Startwert 2. Anzahl Runden bis zum zweiten Erreichen des niedrigsten Wertes 3. Anzahl Veränderungen des Wertes bis zum zweiten Erreichen des niedrigsten Wertes 4. Niedrigster Wert der zweimal erreicht wird (Fixpunkt) 5. Höchster erreichter Wert Code:
1 1 6 1 16 3 2 11 3 46 5 2 11 5 76 7 4 24 3 766 9 2 11 9 136 11 3 18 5 316 13 3 19 3 376 15 5 31 3 856 17 1 10 1 256 19 2 12 9 286 21 2 13 5 316 23 16 95 9 800056 25 2 14 3 376 27 3 20 3 766 29 173 1021 31 643680766 ... 129 6 40 3 1936 131 17 105 3 37726 133 175 1035 31 643680766 135 44 257 507 122625406 ... 1787 266 1578 9 42897306732256 1789 161 956 31 643680766 1791 19 119 9 800056 1793 19 119 9 800056 1795 19 119 9 800056 1797 194 1151 31 643680766 1799 Overflow
|
| Folgende 3 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag: | ||
#24
14.08.2023, 09:05
|
||||||||||||
|
AW: Das 3n+1 / 5n+1 Problem
Liebe Leute,
nach wie vor sitze ich an Varianten des 3n+1-Problems. Gestern abend ist das 5n+-1 Problem dazu gekommen. Es geht los mit einer ungeraden Zahl n. Zu der bildet man 5n-1 und 5n+1. Dies sind beides gerade Zahlen. Eine von ihnen ist durch 4 teilbar, die andere nur durch 2. Man nimmt die Zahl, die durch 4 teilbar ist, und halbiert so lange, bis sich eine ungerade Zahl ergibt. Von der aus startet die nächste Runde. Beispiele: 1 -> (4 , 6) -> 4 -2 -1 Also ist 1 ein Fixpunkt. 7 -> (34 , 36) -> 36 - 18 - 9 9 -> (44 , 46) -> 44 - 22 - 11 11 -> (54 , 56) -> 56 - 28 - 14 - 7 Also ist 7-9-11-7 ein Zyklus. Bis zum Startwert 109 habe ich keine weiteren Zykel gefunden. Vermutung: Jeder Startwert läuft in einen Zyklus. Frage: Sind 1 und 7-9-11 die einzigen Zyklen? Dank im Voraus an alle, die ihre Engine-Bestien auf das Problem loslassen! Herzliche Grüße, Ingo.
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
|
#25
14.08.2023, 13:48
|
|||||||||||
|
AW: Das 3n+1 / 5n+1 Problem
Hallo zusammen,
ich habe es mal schnell durchlaufen lassen (5n-1 und 5n+1), die Änderungen am vorigen Programmcode sind ja überschaubar. Ergebnis: 1. Bis zum Startwert 1.000.000 treten nur die Fixpunkte 1 und 7 auf. 2. Die Folge konvergiert immer sehr schnell, der höchste vorkommende Wert ist nur maximal 10-15 mal größer als der Startwert. 3. Aufgrund von (2.) gibt es auch keine besonderen Ausreißer oder Überraschungen, alles läuft sehr schnell in 1 oder 7 rein. Viele Grüße, Thomas
|
| Folgender Benutzer sagt Danke zu Gilgamesch für den nützlichen Beitrag: | ||
dreihirn (14.08.2023) | ||
#26
14.08.2023, 14:44
|
||||||||||||
|
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.
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
|
#27
18.08.2023, 09:11
|
||||||||||||
|
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.
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
|
#28
18.08.2023, 23:04
|
|||||||||||
|
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 Code:
1 2 10 1 8
3 2 14 1 16
5 2 12 1 16
7 8 62 15 7680
9 4 25 39 624
11 4 28 35 372
13 2 16 1 40
15 7 56 23 7680
17 5 35 39 624
19 4 26 39 624
21 2 14 1 64
23 3 20 35 372
25 3 23 29 232
27 3 23 31 328
29 8 64 15 7680
31 11 91 15 7680
...
199 219 1968 1 30143685317248
201 41 363 15 1257744720
203 6 53 29 1604
205 3 26 29 616
207 43 381 15 1257744720
209 44 390 15 1257744720
211 223 2004 1 30143685317248
...
473 19 168 35 397524
475 6 51 43 5620
477 10 93 1 110132
479 1507 13525 15 5633474152358653058455030362573301198800
481 11 95 15 7680
483 8 68 15 7680
485 8 68 15 7680
...
1649 3 29 29 4948
1651 7 65 29 7432
1653 4 38 29 4960
1655 5688 51062 35 532883555724939922698357411067488379361088412281800423855405840357376
1657 4 38 29 13056
1659 221 1989 1 562413204037782208
1661 276 2477 35 34810817575894536
1663 96 864 29 322328464
...
1961 21 188 35 397524
1963 9 79 15 15464
1965 9 79 15 7680
1967 5159 46312 15 141331469837768875083859002482956122113450198439139246988547504397056
1969 9 79 15 7680
1971 9 79 15 8872
1973 9 79 15 7680
1975 110 987 35 543379976224
1977 1509 13545 15 5633474152358653058455030362573301198800
1979 12 113 1 346240
1981 22 197 35 397524
1983 22 197 35 397524
1985 13 115 15 8800
...
2787 4 33 43 12544
2789 34 311 1 29812096
2791 34 311 1 29812096
2793 34 311 1 29812096
2795 4 33 43 22016
2797 45 404 35 2569008
2799 Overflow
Thomas
|
| Folgende 2 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag: | ||
dreihirn (19.08.2023), Wandersleben (19.08.2023) | ||
#29
19.08.2023, 10:40
|
||||||||||||
|
AW: Das 3n+1 / 5n+1 Problem
Hallo Thomas,
danke für das Rechnen. Zitat von Gilgamesch
...
Die höchsten Werte können aber gelegentlich sehr groß werden, bei dem Startwert 2799 ist selbst mit 256 Bit Schluss. ... 1655 5688 51062 35 53288355572493992269835741106748837936108841228180 0423855405840357376 1657 4 38 29 13056 1659 221 1989 1 ... Und daneben dann so bescheidene Verläufe für 1657 und 1659.. Dank und Gruß, Ingo.
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
|
#30
19.08.2023, 17:58
|
|||||||||||
|
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.
|
| Folgende 2 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag: | ||
dreihirn (20.08.2023), Wandersleben (19.08.2023) | ||
 |
Linear-Darstellung
|
|
Ähnliche Themen
|
||||
| Thema | Erstellt von | Forum | Antworten | Letzter Beitrag |
| Hilfe: Mondial II - Problem | Eckehard Kopp | Technische Fragen und Probleme / Tuning | 5 | 09.05.2016 22:48 |
| Frage: MM I-Problem | Eckehard Kopp | Technische Fragen und Probleme / Tuning | 1 | 26.03.2016 03:09 |
| Frage: Problem mit einem Problem | udo | Teststellungen und Elo Listen / Test positions and Elo lists | 10 | 29.05.2011 01:25 |
| Frage: Fidelity-Problem | Eckehard Kopp | Technische Fragen und Probleme / Tuning | 1 | 29.09.2006 08:36 |
Alle Zeitangaben in WEZ +2. Es ist jetzt 02:47 Uhr.
Powered by vBulletin (Deutsch)
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.