Schachcomputer.info Community

Zurück   Schachcomputer.info Community > Computerschach / Computer Chess: > Schach und künstliche Intelligenz, Knobeleien, Denkspiele / Chess and artificial intelligence
Seite neu laden Mathe: Das 3n+1 / 5n+1 Problem


Antwort
Seite 1 von 2 1 2
 
Themen-Optionen Ansicht

  #1  
Alt 02.08.2023, 23:26
Gilgamesch Gilgamesch ist offline
Super System III
  
Registriert seit: 01.08.2023
Ort: Mindelheim
Land:
Beiträge: 14
Abgegebene Danke: 11
Erhielt 21 Danke für 10 Beiträge
Aktivitäten Langlebigkeit
0/20 3/20
Heute Beiträge
0/3 sssssss14
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
Viele Grüße, Thomas
Angehängte Dateien
Dateityp: txt Collatz151.txt (41,8 KB, 87x aufgerufen)
Mit Zitat antworten
Folgende 3 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag:
dreihirn (03.08.2023), Hartmut (03.08.2023), Wandersleben (03.08.2023)
  #2  
Alt 14.08.2023, 09:05
Benutzerbild von dreihirn
dreihirn dreihirn ist offline
Brikett
  
Registriert seit: 27.08.2020
Ort: Jena
Land:
Beiträge: 116
Abgegebene Danke: 60
Erhielt 108 Danke für 44 Beiträge
Aktivitäten Langlebigkeit
0/20 5/20
Heute Beiträge
0/3 ssssss116
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)
Mit Zitat antworten
  #3  
Alt 14.08.2023, 13:48
Gilgamesch Gilgamesch ist offline
Super System III
  
Registriert seit: 01.08.2023
Ort: Mindelheim
Land:
Beiträge: 14
Abgegebene Danke: 11
Erhielt 21 Danke für 10 Beiträge
Aktivitäten Langlebigkeit
0/20 3/20
Heute Beiträge
0/3 sssssss14
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
Mit Zitat antworten
Folgender Benutzer sagt Danke zu Gilgamesch für den nützlichen Beitrag:
dreihirn (14.08.2023)
  #4  
Alt 14.08.2023, 14:44
Benutzerbild von dreihirn
dreihirn dreihirn ist offline
Brikett
  
Registriert seit: 27.08.2020
Ort: Jena
Land:
Beiträge: 116
Abgegebene Danke: 60
Erhielt 108 Danke für 44 Beiträge
Aktivitäten Langlebigkeit
0/20 5/20
Heute Beiträge
0/3 ssssss116
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)
Mit Zitat antworten
  #5  
Alt 18.08.2023, 09:11
Benutzerbild von dreihirn
dreihirn dreihirn ist offline
Brikett
  
Registriert seit: 27.08.2020
Ort: Jena
Land:
Beiträge: 116
Abgegebene Danke: 60
Erhielt 108 Danke für 44 Beiträge
Aktivitäten Langlebigkeit
0/20 5/20
Heute Beiträge
0/3 ssssss116
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)
Mit Zitat antworten
  #6  
Alt 18.08.2023, 23:04
Gilgamesch Gilgamesch ist offline
Super System III
  
Registriert seit: 01.08.2023
Ort: Mindelheim
Land:
Beiträge: 14
Abgegebene Danke: 11
Erhielt 21 Danke für 10 Beiträge
Aktivitäten Langlebigkeit
0/20 3/20
Heute Beiträge
0/3 sssssss14
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
Viele Grüße,
Thomas
Mit Zitat antworten
Folgende 2 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag:
dreihirn (19.08.2023), Wandersleben (19.08.2023)
  #7  
Alt 19.08.2023, 10:40
Benutzerbild von dreihirn
dreihirn dreihirn ist offline
Brikett
  
Registriert seit: 27.08.2020
Ort: Jena
Land:
Beiträge: 116
Abgegebene Danke: 60
Erhielt 108 Danke für 44 Beiträge
Aktivitäten Langlebigkeit
0/20 5/20
Heute Beiträge
0/3 ssssss116
AW: Das 3n+1 / 5n+1 Problem
Hallo Thomas,
danke für das Rechnen.

 Zitat von Gilgamesch Beitrag anzeigen
...
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
...
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.
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
Mit Zitat antworten
  #8  
Alt 19.08.2023, 17:58
Gilgamesch Gilgamesch ist offline
Super System III
  
Registriert seit: 01.08.2023
Ort: Mindelheim
Land:
Beiträge: 14
Abgegebene Danke: 11
Erhielt 21 Danke für 10 Beiträge
Aktivitäten Langlebigkeit
0/20 3/20
Heute Beiträge
0/3 sssssss14
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.
Angehängte Dateien
Dateityp: zip Collatz_3_3_7_1655.zip (972,9 KB, 96x aufgerufen)
Mit Zitat antworten
Folgende 2 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag:
dreihirn (20.08.2023), Wandersleben (19.08.2023)
  #9  
Alt 20.08.2023, 09:29
Benutzerbild von dreihirn
dreihirn dreihirn ist offline
Brikett
  
Registriert seit: 27.08.2020
Ort: Jena
Land:
Beiträge: 116
Abgegebene Danke: 60
Erhielt 108 Danke für 44 Beiträge
Aktivitäten Langlebigkeit
0/20 5/20
Heute Beiträge
0/3 ssssss116
AW: Das 3n+1 / 5n+1 Problem
Hallo Thomas,
danke für die Daten.

 Zitat von Gilgamesch Beitrag anzeigen
Etwas Auffälliges ausser der Länge
kann ich nicht erkennen.
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.
Miniaturansicht angehängter Grafiken
Klicke auf die Grafik für eine größere Ansicht Name: folge-anfang.jpg Hits: 59 Größe: 12,9 KB ID: 6194   Klicke auf die Grafik für eine größere Ansicht Name: folge-mitte.jpg Hits: 50 Größe: 25,5 KB ID: 6195   Klicke auf die Grafik für eine größere Ansicht Name: folge-schluss.jpg Hits: 44 Größe: 11,6 KB ID: 6196  
__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)
Mit Zitat antworten
Folgende 2 Benutzer sagen Danke zu dreihirn für den nützlichen Beitrag:
Gilgamesch (20.08.2023), Wandersleben (20.08.2023)
  #10  
Alt 20.08.2023, 18:38
Gilgamesch Gilgamesch ist offline
Super System III
  
Registriert seit: 01.08.2023
Ort: Mindelheim
Land:
Beiträge: 14
Abgegebene Danke: 11
Erhielt 21 Danke für 10 Beiträge
Aktivitäten Langlebigkeit
0/20 3/20
Heute Beiträge
0/3 sssssss14
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:

Code:
Startwert:  2799
Runden:    14966
Schritte: 134261
Fixpunkt:      1
Höchster Wert:
4576380734615710479690106325689609211241863537762981964042455051075724332822215383625091530700741156
546681974982555045360453632 (127 Stellen)

Code:
Startwert: 14975
Runden:    51639
Schritte: 463293
Fixpunkt:     35
Höchster Wert:
9989323727783341288713747130739468253471810232357536641687347870748657993683879904466884139557940582
5553160183246255023839530657063922381301089297022146122314293811553434648714267582962923939302464618
9655985406114827467681702953665986109731506425351328900741453810959854609376  (276 Stellen)
Grüße,
Thomas
Mit Zitat antworten
Folgende 3 Benutzer sagen Danke zu Gilgamesch für den nützlichen Beitrag:
borromeus (21.08.2023), dreihirn (20.08.2023), Wandersleben (20.08.2023)
Antwort
Seite 1 von 2 1 2

« Vorheriges Thema | Nächstes Thema »
Themen-Optionen
Ansicht
Hybrid-Darstellung Hybrid-Darstellung

Forumregeln
Du bist nicht berechtigt, neue Themen zu erstellen.
Du bist nicht berechtigt, auf Beiträge zu antworten.
Du bist nicht berechtigt, Anhänge hochzuladen.
Du bist nicht berechtigt, deine Beiträge zu bearbeiten.
BB code ist An
Smileys sind An.
[IMG] Code ist An.
HTML-Code ist An.
Gehe zu

Ä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 +1. Es ist jetzt 13:00 Uhr.



Powered by vBulletin (Deutsch)
Copyright ©2000 - 2026, Jelsoft Enterprises Ltd.
©Schachcomputer.info