Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / Varianten des Collatz-Problems
- - By Ingo Althöfer Date 2016-07-21 19:53 Edited 2016-07-21 19:57
Hallo allerseits,

heute konnte ich auf einer längeren Zugfahrt wegen der schwülen Luft nichts
Ernsthaftes arbeiten und habe stattdessen etwas mit Zahlen herumgespielt.
Dabei kam ich auf eine Verallgemeinerung des Collatz-Problems.

Bei dem Collatz-Problem geht es um Folgen natürlicher Zahlen mit folgendem
Bildungsgesetz: n(0) gibt man vor.
Hat man schon n(t) für ein t berechnet, so ergibt sich n(t+1) wie folgt:
Wenn n(t) gerade ist, dann ist n(t+1) = n(t)/2.
Wenn n(t) ungerade ist, dann ist n(t+1) = 3*n(t) +1.

Die schon von Collatz formulierte Vermutung ist: Für jede natürlich Zahl n(0)
läuft die Folge irgendwann in den Zyklus 4 -> 2 -> 1 -> 4
Bisher gibt es keinen Beweis für die Vermutung. Paul Erdos sagte einmal,
dass die Mathematik noch nicht reif für dieses Problem sei.
Mann kann aber gut mit dem Computer - kursorisch oder systematisch -
Startwerte n(0) prüfen.

Im Zug habe ich heute - ganz ohne Computer - folgende Varianten des
Problems angeschaut: Sei u eine ungerade (natürliche) Zahl.
Dann beginne mit einem n(0) und setze bei bekanntem n(t)
n(t+1) = n(t)/2, falls n(t) gerade
und
n(t+1) = 3*n(t) + u bei ungeradem n(t).

u=1 ist das klassische Collatz-Problem.
Interessant fand ich im Zug den Fall u=5. Dafür gibt es mindestens vier Zyklen:
(a) 1 -> 8 -> 4 -> 2 -> 1
(b) 5 -> 20 -> 10 -> 5
(c) 19 -> 62 -> 31 -> 98 -> 49 -> 152 -> 76 -> 38 -> 19
(d) 23 -> 74 -> 37 -> 116 -> 58 -> 29 -> 92 -> 46 -> 23

Fragen:

* Gibt es neben diesen vier Zielzyklen weitere für das 3n+5-Problem?

* Gibt es andere u mit mehr als vier Zielzyklen im 3n+u-Problem?
* Falls ja, finde man "kleine" u, für die es möglichst viele Zielzyklen gibt.

Natürlich wird man mit Computerhilfe viel schneller Erkenntnisse gewinnen
als per Handrechnungen. Für schöne Einsichten spendiere ich bis zu
drei Exemplare des Buchs "Spiele - Rätsel - Zahlen" von Roland Voigt
und mir.

Ingo Althöfer.
Parent - - By Ulf Flörsheimer Date 2016-07-22 20:10
Hallo Ingo,

was hältst du von diesem schönen Zyklus?

1  359
2  1082
3  541
4  1628
5  814
6  407
7  1226
8  613
9  1844
10  922
11  461
12  1388
13  694
14  347
15  1046
16  523
17  1574
18  787
19  2366
20  1183
21  3554
22  1777
23  5336
24  2668
25  1334
26  667
27  2006
28  1003
29  3014
30  1507
31  4526
32  2263
33  6794
34  3397
35  10196
36  5098
37  2549
38  7652
39  3826
40  1913
41  5744
42  2872
43  1436
44  718
45  359

Gruß Ulf
Parent - - By Ingo Althöfer Date 2016-07-22 20:50
Hallo Ulf,

Ulf Flörsheimer schrieb:

was hältst du von diesem schönen Zyklus?
1  359
2  1082
3  ...
44  718
45  359


Hübsch!

Gibt es bei 3n+5 ausser den 5 gefundenen noch weitere?
Welche weiteren bekommt man, wenn man auch negative
Startwerte zulässt?

Ingo.
Parent - - By Ulf Flörsheimer Date 2016-07-22 21:00
Hallo Ingo,

ich habe mir noch kurz die Form

n(t+1) = 5*n(t) + 3 angeschaut. Hier gibt es die Kurzzyklen

a)       1       8       4       2
b)       3      18       9      48      24      12       6
c)      39     198      99     498     249    1248     624     312     156      78
d)      43     218     109     548     274     137     688     344     172      86
e)      51     258     129     648     324     162      81     408     204     102
f)      53     268     134      67     338     169     848     424     212     106
g)      61     308     154      77     388     194      97     488     244     122

Weitere habe ich nicht gefunden.

Gruß Ulf
Parent - By Ingo Althöfer Date 2016-07-23 09:29
Hallo Ulf,

sehr interessante Ergebnisse insgesamt. Danke für das Engagement.

Besonders interessant finde ich Deine Ergebnisse für die 5n+3-Regel.
Bei "zufälligem" Verhalten sollten die Folgen für grosse Startwerte
nach unendlich divergieren. Dass es trotzdem 7 Zyklen gibt, ist für
mich eine Riesenüberraschung.  Was hattest Du da als Abbruchkriterium
für die Folgen, die nicht in Zykel laufen?

Welche Zykel ergeben sich für
5n+1-Regel und für
5n-1-Regel?

Einen Preis bekommst Du auf jeden Fall.
Ist ein "EinStein würfelt nicht"-Spiel ok?
Schick doch per Email die Lieferadresse.

Ingo.

Ulf Flörsheimer schrieb:

n(t+1) = 5*n(t) + 3 angeschaut. Hier gibt es die Kurzzyklen
a)       1       8       4       2
b)       3      18       9      48      24      12       6
c)      39     198      99     498     249    1248     624     312     156      78
d)      43     218     109     548     274     137     688     344     172      86
e)      51     258     129     648     324     162      81     408     204     102
f)      53     268     134      67     338     169     848     424     212     106
g)      61     308     154      77     388     194      97     488     244     122

Weitere habe ich nicht gefunden.
Parent - By Ulf Flörsheimer Date 2016-07-22 21:09
Andere als diese habe ich nicht gefunden.

Für negative Startwerte erhalte ich:

a)      -5     -10
b)    -25     -70     -35    -100     -50
c)    -85    -250    -125    -370    -185    -550    -275    -820    -410    -205    -610    -305    -910    -455   -1360    -680    -340    -170

Das war's.
Parent - - By Ulf Flörsheimer Date 2016-07-23 09:09
In meinem gestrigen unsystematischen Wurschteln habe ich glatt übersehen, dass ich zwei Zyklen der Länge 44 gefunden hatte:

     187     566     283     854     427    1286     643    1934     967
    2906    1453    4364    2182    1091    3278    1639    4922    2461
    7388    3694    1847    5546    2773    8324    4162    2081    6248
    3124    1562     781    2348    1174     587    1766     883    2654
    1327    3986    1993    5984    2992    1496     748     374

     347    1046     523    1574     787    2366    1183    3554    1777
    5336    2668    1334     667    2006    1003    3014    1507    4526
    2263    6794    3397   10196    5098    2549    7652    3826    1913
    5744    2872    1436     718     359    1082     541    1628     814
     407    1226     613    1844     922     461    1388     694

Den unteren (allerdings beginnend mit 359) habe ich gestern schon gezeigt. Also gibt es mindestens 6 Zyklen mit 3x+5.

----------------------------------

Bei der Variante 5x+7 komme ich auf 6 Zyklen:

       1      12       6       3      22      11      62      31     162
      81     412     206     103     522     261    1312     656     328
     164      82      41     212     106      53     272     136      68
      34      17      92      46      23     122      61     312     156
      78      39     202     101     512     256     128      64      32
      16       8       4       2

       7      42      21     112      56      28      14

       9      52      26      13      72      36      18

      57     292     146      73     372     186      93     472     236
     118      59     302     151     762     381    1912     956     478
     239    1202     601    3012    1506     753    3772    1886     943
    4722    2361   11812    5906    2953   14772    7386    3693   18472
    9236    4618    2309   11552    5776    2888    1444     722     361
    1812     906     453    2272    1136     568     284     142      71
     362     181     912     456     228     114

      91     462     231    1162     581    2912    1456     728     364
     182

     119     602     301    1512     756     378     189     952     476
     238

Schönes Wochenende!
Ulf
Parent - - By Ulf Flörsheimer Date 2016-07-23 09:36
Und ein allerletzter Nachtrag:

Für die Formel 3x+13 fand ich 10 Zyklen:

       1      16       8       4       2

      13      52      26

     131     406     203     622     311     946     473    1432     716
     358     179     550     275     838     419    1270     635    1918
     959    2890    1445    4348    2174    1087    3274    1637    4924
    2462    1231    3706    1853    5572    2786    1393    4192    2096
    1048     524     262

     211     646     323     982     491    1486     743    2242    1121
    3376    1688     844     422

     227     694     347    1054     527    1594     797    2404    1202
     601    1816     908     454

     251     766     383    1162     581    1756     878     439    1330
     665    2008    1004     502

     259     790     395    1198     599    1810     905    2728    1364
     682     341    1036     518

     283     862     431    1306     653    1972     986     493    1492
     746     373    1132     566

     287     874     437    1324     662     331    1006     503    1522
     761    2296    1148     574

     319     970     485    1468     734     367    1114     557    1684
     842     421    1276     638

Parent - - By Ingo Althöfer Date 2016-07-23 10:04
Sehr interessante Struktur...

Ulf Flörsheimer schrieb:

Für die Formel 3x+13 fand ich 10 Zyklen:
-  1      16       8       4       2
-  13      52      26
-  131     406    ...

Diese ersten drei Zykel wirken jeder für sich individuell.

Was danach kommt, sind aber sieben "Geschwister", die alle
die gleiche Länge 13 haben. Ob es Zufall ist, dass diese 13
auch in der Bildungsvorschrift vorkommt?

Zitat:

-    211     646     323     982     491    1486     743    2242    1121
    3376    1688     844     422

- 227 ...
- 251 ...
- 259 ...
- 283 ...
- 287 ...
- 319 ...

Viel Stoff für Vermutungen...

Ingo.
Parent - By Ulf Flörsheimer Date 2016-07-23 10:36
Der Dritte hat übrigens die Länge 39, was ja auch entfernt mit der 13 zu tun hat.

Und bei der 5x+3 Variante sind es leider nur 6 Zyklen (die vier von dir genannten) und meine zwei.
Parent - - By Ingo Althöfer Date 2016-07-23 16:05
Hallo allerseits,

Ulf Flörsheimer hat ja auf die Schnelle sehr schöne Untersuchungen
zu Varianten des 3n+1-Problems gemacht - und sich damit einen
Spielepreis verdient (mindestens zwei weitere Spielepreise sind noch
zu vergeben - auch ein "EinStein würfelt nicht" mit Edelholzbrett!) .

Per Mail hat mir Ulf mitgeteilt, dass er seine Rechnungen mit Hilfe der
Interpreter-Sprache "ARIBAS" von Otto Forster durchgeführt hat. Eines
der erfreulichen Features bei ARIBAS ist, dass mit "fast beliebig
langen" integers gerechnet werden kann. ARIBAS ist kostenlos unter
einer GNU-Lizenz verfügbar. Die Download-Page dafür ist erreichbar
über
https://www.mathematik.uni-muenchen.de/~forster/sw/aribas.html

Jedenfalls habe ich jetzt schon mal einen schönen Fundus für meine
kommende Optimierungs-Vorlesung für Lehramts-Studenten in Mathe
und Informatik.

Ingo Althöfer.

PS. In meinem Mathe-Studium, Anfang der 1980er Jahre in Bielefeld,
spielte Otto Forster eine zentrale Rolle. Seine Lehrbücher 1 und 2 zur
Analysis halfen, dass ich nicht in der "Freistil"-Analysis von Prof. Heinz
Helling unterging.
Parent - - By Michael Bechmann Date 2016-07-23 23:52 Edited 2016-07-24 00:04
152
76
38
19
62
31
98
49
152

---
116
58
29
92
46
23
74
37
116

Ich hatte mit Excel mal einige Startwerte geprüft ... und festgestellt, dass die Zahlenfolge irgendwann immer in ein Zyklus kommt.

A1: Startwert einsetzen
A2: =WENN(REST(A1;2)=0;A1/2;A1*3+5)

Danach bei A2 mit der Maus die Formel nach unten ausfüllen lassen.

... und festgestellt, dass die Zahlenfolge irgendwann immer in ein Zyklus kommt.

Zum Spaß hatte ich meinen Geburtstag, also eine 8stellige ungerade Zahl als Startwert eingesetzt und die 205. Zahl wahr 152 und es ergab ab dort den Zyklus von oben.

Prinzipiell kommt man offenbar immer nach einigen weiteren Zahlen in den "152"-Zyklus.

Bei mehrstelligen Startwerten fällt auf, dass die Tendenz zu kleineren Zahlen auffallen, also A/2 mehr "wirkt" als A1*3+5
Ich habe keinen Startwert gefunden, der zu immer größeren Werten führt.

Man müsste ein allgemeingültiges Gesetz finden, welches bestimmt, unter welchen Bedingungen der Startzahl ausnahmsweise kein Zyklus zustandekommt.
Das müssen Zahlentheoretiker herausfinden.
Parent - - By Ulf Flörsheimer Date 2016-07-24 08:11 Edited 2016-07-24 08:59
Hallo Michael,

Michael Bechmann schrieb:

Ich hatte mit Excel mal einige Startwerte geprüft ... und festgestellt, dass die Zahlenfolge irgendwann immer in ein Zyklus kommt.


im Prinzip geht's ja genau um diese Frage. Bei dem ursprünglichen Problem (dem mit der Formel 3*x+1) war die Frage, die Collatz sich gestellt hat, ob jede Startzahl in den Zyklus 4 - 2 - 1 mündet. Oder simpler: Ob jede Startzahl irgendwann die 1 erreicht. Bis heute kennt man kein Gegenbeispiel, aber es gibt Startzahlen, die "sich heftig wehren", z.B. 27 oder 63728127.

Nimmt man andere Formeln (z.B. 3*x+5), können die Werte in einem oder mehreren Zyklen enden oder ewig ziellos herumwandern (bzw. gegen unendlich divergieren).

Michael Bechmann schrieb:

... und festgestellt, dass die Zahlenfolge irgendwann immer in ein Zyklus kommt.


Man sollte bei mathematischen Fragen generell vorsichtig mit dem Wort "immer" sein, es sei denn, man kann es beweisen. Wer sagt dir, dass es nicht eine Startzahl mit 782 Stellen gibt, die in keinen Zyklus mündet?

Hier ein Beispiel, das ich im WWW gefunden habe: Die Behauptung lautet, dass a=n^29+14 und b=(n+1)^29+14 relativ prim zueinander sind, also als größten gemeinsamen Teiler immer 1 haben. Das klappt auch für viele n ... genauer gesagt bis n=345253422116355058862366766874868910441560096980654656110408105446268691941239624255384457677726969174087561682040026593303628834116200365400
Die hieraus resultierenden a und b haben jeweils 4076 Stellen und den größten gemeinsamen Teiler 736465429324998051630597252135070211278762438165848555890499935926691434253288170322016820144491199028074530098421051978869029450106895680461. Die Zahl hat 141 Stellen.

Michael Bechmann schrieb:

Prinzipiell kommt man offenbar immer nach einigen weiteren Zahlen in den "152"-Zyklus.


Leider stimmt diese Behauptung nicht: Nimm beispielsweise die Startzahlen 135, 791, 8423, 45611 die alle in unterschiedliche Zyklen laufen, aber keine in deinen "152"-Zyklus.  Dafür habe ich hier ein Beispiel für eine Startzahl, die ziemlich lange "herumirrt", bervor sie in deinem "152"-Zyklus landet: 891213

Schönen Sonntag.
Ulf
Parent - - By Ingo Althöfer Date 2016-07-24 08:59
Hallo Ulf,

danke für den interessanten Beitrag und die Erklärungen.

Ulf Flörsheimer schrieb:
Hier ein Beispiel, das ich im WWW gefunden habe:
Die Behauptung lautet, dass a=n^29+14 und b=(n+1)^29+14 relativ prim zueinander sind ...

Sehr interessant.
Mit Langzahl-Arithmetik lässt sich das für "viele" n leicht prüfen, obwohl
es um Primzahlen geht. Bei "relativ prim" reicht nämlich der euklidische
Algorithmus.

Fage: Wo im Web hast Du das denn gefunden?
Zu meiner Suchphrase a=n^29+14 gab Tante Google nämlich folgende Treffer:

* Nasenweltmeisterschaft: Auf die Länge kommt es an ...
* Flugzeug mit 29 Menschen an Bord verschwunden ...
* Liste der Kreisstraßen im Landkreis Ansbach ...
* Hiob 29:14 Gerechtigkeit war mein Kleid, das ich anzog wie einen ...
* Stellenausschreibung N 29-14 An der Universität Rostock ...
* Surah Al-'Ankabut [29] - Al-Qur'an al-Kareem - القرآن الكريم ...
* Blick hinter die Kulissen beim 14. Girls' und Boys' Day ...
* Elektronisches Anwaltspostfach geht an den Start ...
* Lizenzübergabe an 29 Trainer/Innen im FBK Aachen ...
* Tötungsdelikt an 29-jährigem Mann in Eschweiler 15.8.2015 ...

Zitat:
Dafür habe ich hier ein Beispiel für eine Startzahl, die ziemlich lange "herumirrt",
bervor sie in deinem "152"-Zyklus landet: 891213

Wie lange irrt sie denn?
Und was ist die grösste zwischendurch erreichte Zahl?

Ingo.
Parent - By Michael Bechmann Date 2016-07-24 09:18 Edited 2016-07-24 09:30
Zitat:
Dafür habe ich hier ein Beispiel für eine Startzahl, die ziemlich lange "herumirrt",
bervor sie in deinem "152"-Zyklus landet: 891213.


Bei Zahl Nr. 459 = 152, genau genommen beginnt der Zyklus schon mit Nr. 452 = 11, dann 38,19,62,31,98,49,152

Maximum bei Nr. 35 mit 146347712
Parent - - By Ulf Flörsheimer Date 2016-07-24 09:36
Moin,

ich habe bei Google huge smallest counterexample eingegeben und die erste Seite ausgewählt: http://math.stackexchange.com/questions/514/conjectures-that-have-been-disproved-with-extremely-large-counterexamples

"Für viele" meint flapsig formuliert, dass das angegebene n das kleinste Gegenbeispiel sei. Nun magst du mich faul nennen, aber mir fehlt die Zeit und die Lust 10^141 Rechnungen auszuführen Aber ernsthaft: Ich hab es numerisch bis 12.000.000 verifiziert.

Ansonsten hab ich zum verallgemeinerten Collatz (3x+5) noch mal ein kleines Programmchen geschrieben, das mir die längsten Sequenzen bis zum Abschluss der ersten Periode ausgibt:

==> var a:array[1001] of integer;
    end;
    v:=0;
    for i:=1 to 1000000 do
      a[0]:=x:=i;
      c:=0;
      ok:=true;
      while ok do
        (z,c):=(c,c+1);
        if x mod 2=0 then x:=x div 2 else x:=3*x+5 end;
        a[c]:=x;
        while z>=0 and ok do
          if a[z]=x
            then ok:=false
            else z:=z-1
          end
        end;
        if not ok then
          if c>=v then
            xm:=x;
            for j:=1 to c-z do
              if x mod 2=0 then x:=x div 2 else x:=3*x+5 end;
              if x<xm then xm:=x end
            end;
            writeln(i:7,z:5,c-z:5,xm:6);
            v:=c
          end
        end
      end
    end.
      1    0    4     1
      2    0    4     1
      3    8    8    19
      6    9    8    19
     12   10    8    19
     17   10    8    19
     21   13    8    19
     27   26    8    19
     54   27    8    19
     59   27    8    19
     77   30    8    19
     87   38    8    19
     99   67    8    19
    135  109    3     5
    270  110    3     5
    275  110    3     5
    365  113    3     5
    485  116    3     5
    645  119    3     5
    855  122    3     5
   1155  125    3     5
   1175  125    3     5
   1283  156    8    19
   1709  159    8    19
   2043  186    8    19
   4086  187    8    19
   4091  187    8    19
   4379  191    8    19
   4487  194    8    19
   5837  194    8    19
   5981  197    8    19
   7781  197    8    19
   7973  200    8    19
   8423  204    4     1
   9707  218    8    19
  11523  264    4     1
  20487  270    4     1
  20987  266    8    19
  23291  289    8    19
  31053  292    8    19
  32711  305    8    19
  43613  308    8    19
  45611  324    8    23
  60813  327    8    23
  71099  366    8    23
  94797  369    8    23
189594  370    8    23
189599  370    8    23
252797  373    8    23
299607  381    8    23
335867  394    8    19
447821  397    8    19
589563  404    4     1
597093  400    8    19
622779  426    8    23
668411  449    8    19
891213  452    8    19

Die Ausgabe liest sich wie folgt: Startzahl, Länge der Vorperiode, Länge des Zyklus, Kleinste Zahl des Zyklus (zur Klassifikation)

891213 ergibt mit 460 Iterationen den größten Wert für (Länge von Vorperiode + Zyklus) für alle Startwerte kleiner 1000000.

891213, 2673644, 1336822, 668411, 2005238, 1002619, 3007862, 1503931, 4511
798, 2255899, 6767702, 3383851, 10151558, 5075779, 15227342, 7613671, 22841018
, 11420509, 34261532, 17130766, 8565383, 25696154, 12848077, 38544236, 1927211
8, 9636059, 28908182, 14454091, 43362278, 21681139, 65043422, 32521711, 975651
38, 48782569, 146347712, 73173856, 36586928, 18293464, 9146732, 4573366, 22866
83, 6860054, 3430027, 10290086, 5145043, 15435134, 7717567, 23152706, 11576353
, 34729064, 17364532, 8682266, 4341133, 13023404, 6511702, 3255851, 9767558, 4
883779, 14651342, 7325671, 21977018, 10988509, 32965532, 16482766, 8241383, 24
724154, 12362077, 37086236, 18543118, 9271559, 27814682, 13907341, 41722028, 2
0861014, 10430507, 31291526, 15645763, 46937294, 23468647, 70405946, 35202973
, 105608924, 52804462, 26402231, 79206698, 39603349, 118810052, 59405026, 2970
2513, 89107544, 44553772, 22276886, 11138443, 33415334, 16707667, 50123006, 25
061503, 75184514, 37592257, 112776776, 56388388, 28194194, 14097097, 42291296
, 21145648, 10572824, 5286412, 2643206, 1321603, 3964814, 1982407, 5947226, 29
73613, 8920844, 4460422, 2230211, 6690638, 3345319, 10035962, 5017981, 1505394
8, 7526974, 3763487, 11290466, 5645233, 16935704, 8467852, 4233926, 2116963, 6
350894, 3175447, 9526346, 4763173, 14289524, 7144762, 3572381, 10717148, 53585
74, 2679287, 8037866, 4018933, 12056804, 6028402, 3014201, 9042608, 4521304, 2
260652, 1130326, 565163, 1695494, 847747, 2543246, 1271623, 3814874, 1907437,
5722316, 2861158, 1430579, 4291742, 2145871, 6437618, 3218809, 9656432, 482821
6, 2414108, 1207054, 603527, 1810586, 905293, 2715884, 1357942, 678971, 203691
8, 1018459, 3055382, 1527691, 4583078, 2291539, 6874622, 3437311, 10311938, 51
55969, 15467912, 7733956, 3866978, 1933489, 5800472, 2900236, 1450118, 725059
, 2175182, 1087591, 3262778, 1631389, 4894172, 2447086, 1223543, 3670634, 1835
317, 5505956, 2752978, 1376489, 4129472, 2064736, 1032368, 516184, 258092, 129
046, 64523, 193574, 96787, 290366, 145183, 435554, 217777, 653336, 326668, 163
334, 81667, 245006, 122503, 367514, 183757, 551276, 275638, 137819, 413462, 20
6731, 620198, 310099, 930302, 465151, 1395458, 697729, 2093192, 1046596, 52329
8, 261649, 784952, 392476, 196238, 98119, 294362, 147181, 441548, 220774, 1103
87, 331166, 165583, 496754, 248377, 745136, 372568, 186284, 93142, 46571, 1397
18, 69859, 209582, 104791, 314378, 157189, 471572, 235786, 117893, 353684, 176
842, 88421, 265268, 132634, 66317, 198956, 99478, 49739, 149222, 74611, 223838
, 111919, 335762, 167881, 503648, 251824, 125912, 62956, 31478, 15739, 47222,
23611, 70838, 35419, 106262, 53131, 159398, 79699, 239102, 119551, 358658, 179
329, 537992, 268996, 134498, 67249, 201752, 100876, 50438, 25219, 75662, 37831
, 113498, 56749, 170252, 85126, 42563, 127694, 63847, 191546, 95773, 287324, 1
43662, 71831, 215498, 107749, 323252, 161626, 80813, 242444, 121222, 60611, 18
1838, 90919, 272762, 136381, 409148, 204574, 102287, 306866, 153433, 460304, 2
30152, 115076, 57538, 28769, 86312, 43156, 21578, 10789, 32372, 16186, 8093, 2
4284, 12142, 6071, 18218, 9109, 27332, 13666, 6833, 20504, 10252, 5126, 2563,
7694, 3847, 11546, 5773, 17324, 8662, 4331, 12998, 6499, 19502, 9751, 29258, 1
4629, 43892, 21946, 10973, 32924, 16462, 8231, 24698, 12349, 37052, 18526, 926
3, 27794, 13897, 41696, 20848, 10424, 5212, 2606, 1303, 3914, 1957, 5876, 2938
, 1469, 4412, 2206, 1103, 3314, 1657, 4976, 2488, 1244, 622, 311, 938, 469, 14
12, 706, 353, 1064, 532, 266, 133, 404, 202, 101, 308, 154, 77, 236, 118, 59,
182, 91, 278, 139, 422, 211, 638, 319, 962, 481, 1448, 724, 362, 181, 548, 274
, 137, 416, 208, 104, 52, 26, 13, 44, 22, 11, 38, 19, 62, 31, 98, 49, 152, 76

Größter Wert der Folge: 146347712

LG Ulf
Parent - - By Michael Bechmann Date 2016-07-24 09:43 Edited 2016-07-24 09:45
Moin,

das macht Excel aber wesentlich schneller und ohne zusätzlich zu installierenden Programme nebst Programm, dass man auch erst entwerfen muss.

Das Ergebnis ist natürlich gleich. siehe oben (9:30).   
Parent - - By Ulf Flörsheimer Date 2016-07-24 10:06
Hallo Michael,

das Programm, berechnet die obere Tabelle, also die Rekordhalter aller Startzahlen von 1 bis eine Million, die Längen der Vorperioden, die Zykluslängen und kategorisiert dabei, welcher Zyklus erreicht wurde. Das zugehörige Excel-Sheet hätte ich gerne von dir ...  zumal auch ich ein großer Excel-Fan bin.

Gruß Ulf
Parent - By Michael Bechmann Date 2016-07-24 10:37 Edited 2016-07-24 11:09
Hallo Ulf,

das Programm mag gut sein, aber die Frage war nicht nach 1.000.000 Folgen sondern nach einer einzigen, nämlich die mit dem Startwert 891213. Um einzelne der Folgen zu betrachten reichen Windows-Mittel.
Weil sie offenbar "sperrig" schien, habe ich sie als zusätzliche Herausforderung getestet.
Die Antwort hatten Sie mit dem Programm inzwischen (unabhängig von meiner Excel-Methode) selbst herausgefunden.

Nach der Anwendung des vorgestellten Programm muss man doch auch alle Zahlenfolgen der Reihe nach ansehen.

Das zugehörige Excel-Sheet müsste doch mit VBA machbar sein? Ich habe es nicht versucht, aber die Programmstruktur wäre dann auch sehr ähnlich.

Letzlich aber liefern auch Millionen Ergebnisse keine allgemeingültigen Aussagen. Auch wenn es 1 Millionen Zyklen gibt, bleibt die Frage ob es eine Zahl gibt, die es nach der rekursiven Bildungsvorschrift keinen Zyklus erzeugt, immer noch unbeantwortet.

Und wenn man eine von den Millionen Folgen findet, die scheinbar divergent oder irregulär ist, muss man für den Nachweis unendliche viele Zahlen in der Folge sehen (was unmöglich ist) oder beweisen, dass es bei diesem Startwert keinen Zyklus gibt.

Michael
Parent - By Michael Bechmann Date 2016-07-24 09:14 Edited 2016-07-24 09:28
Zitat:
Man sollte bei mathematischen Fragen generell vorsichtig mit dem Wort "immer" sein


Das stimmt. Ich war offenbar etwas voreilig. Es war aber immer bei meinen Beispielen (etwa 10 verschiedenen Startwerten) so: Man kam entweder zur Zahl 152 oder zu 1.

Die "wichtigere" Zahl ist offenbar aber 11. Wenn man die 11 findet, bekommt man auch 7 Zahlen später die 152.
38
19
62
31
98
49
152

Zitat:
Nimmt man andere Formeln (z.B. 3*x+5), können die Werte in einem oder mehreren Zyklen enden oder ewig ziellos herumwandern (bzw. gegen unendlich divergieren).


Es ist nötig, eine allgemeingültige mathematische Lösung zu finden mit einem math. Satzes nebst Beweis, bei welchen Startzahlen sich ziellose Folgen oder divergente Folgen ergeben.
Parent - - By Tommy Tulpe Date 2016-07-24 09:17
Hallo Herr Althöfer,

Ingo Althöfer schrieb:


(...)
PS. In meinem Mathe-Studium, Anfang der 1980er Jahre in Bielefeld,
spielte Otto Forster eine zentrale Rolle. Seine Lehrbücher 1 und 2 zur
Analysis halfen, dass ich nicht in der "Freistil"-Analysis von Prof. Heinz
Helling unterging.


ich habe nach meinem Abitur 1976 mit dem Mathematikstudium begonnen und da waren die beiden Analysis-Bücher von Otto Forster ziemlich neu auf dem Markt. Unser Dozent empfahl die Werke von Christian(?) Blatter, aber diese empfand ich als total unstrukturiert. Forsters Büchlein halfen auch mir sehr, den Stoff zu verstehen und mich auf Prüfungen vorzubereiten.

Nette Grüße von

Ulrich Haug

P.S.:
Erinnern Sie sich noch ein wenig an mich? Sie hatten mal einen tollen Artikel zu einer meiner Fernpartien verfasst im Schachmagazin 06/2013.
Parent - By Ingo Althöfer Date 2016-07-25 21:38
Lieber Herr Haug,

Tommy Tulpe schrieb:
Ingo Althöfer schrieb:
PS. In meinem Mathe-Studium, Anfang der 1980er Jahre in Bielefeld,
spielte Otto Forster eine zentrale Rolle. Seine Lehrbücher 1 und 2 zur Analysis ...

ich habe nach meinem Abitur 1976 mit dem Mathematikstudium
begonnen und da waren die beiden Analysis-Bücher von Otto Forster
ziemlich neu auf dem Markt. Unser Dozent empfahl die Werke von
Christian(?) Blatter, aber diese empfand ich als total unstrukturiert.
Forsters Büchlein halfen auch mir sehr, den Stoff zu verstehen und
mich auf Prüfungen vorzubereiten.

Unser Dozent hatte den Erwe und den Forster empfohlen.
Ich Dumkopf habe beide sofort gekauft, ohne mich
zu informieren. Mit dem Erwe konnte ich nichts anfangen,
aber immerhin war der Forster ein Volltreffer.

Zitat:
Erinnern Sie sich noch ein wenig an mich? ...

Natürlich, das war damals eine tolle Sache.

Aktuell werden ja die Go-Programm so stark, dass sie für
Fern-Go ernsthafte Hilfen sind. Und die deutsche Go-Bundesliga,
die online läuft, wird irgendwann erste Fälle von unerlaubter
Computerhilfe zu beklagen haben, wahrscheinlich schon in
der kommenden Saison.

Viele Grüsse, Ihr
Ingo Althöfer.
Parent - - By Ulf Flörsheimer Date 2016-07-26 22:09 Upvotes 1
Hallo,

ich habe mich noch ein wenig mit der verallgemeinerten Form 3x+5 beschäftigt. Dabei ist mir etwas seltsames aufgefallen. Ich habe die Zahlen von 1 bis 100.000 betrachtet und geschaut, in welchen Zyklus sie laufen. Dabei erhielt ich dieses Ergebnis:

Zyklus  mittl. Vorperiode  Anzahl
1    96,69      140.991
5    112,69      200.000
19    102,56      496.421
23    77,82      92.970
187    57,64      32.530
347    62,28      37.088
Gesamt  98,50      1.000.000

Tatsächlich ist der Zyklus, der sich mit Länge 8 aus der Zahl 19 ergibt, für fast der Hälfte der Startzahlen "das angesteuerte Ziel", auch der kurze Zyklus, der sich aus der 5 ergibt, wird in 20% der Fälle zur "Senke", während die mit 44 Elementen sehr langen Zyklen gerade mal mit 3,25% bzw. 3,7% "angesteuert" werden. Ich hätte eher erwartet, dass sich aus der größeren Zykluslänge mehr Möglichkeiten ergeben, um in diesen Zyklus zu gelangen.

Auch interessant ist, wie sehr sich die mittleren Vorperioden unterscheiden: Bei dem 19-er und 5-er Zyklus sind sie merklich länger als bei den vielelementigen Zyklen.

Dies deckt sich mit meiner Beobachtung, dass bei den Zahlen mit den jeweils längsten Vorperioden der 19-er Zyklus klar dominiert. Schon seltsam, finde ich ...

Gruß Ulf
Parent - - By Ingo Althöfer Date 2016-07-27 09:37
Hallo Ulf,

Ulf Flörsheimer schrieb:

... verallgemeinerten Form 3x+5 beschäftigt. Dabei ist mir etwas seltsames
aufgefallen. Ich habe die Zahlen von 1 bis 100.000 betrachtet und geschaut,
in welchen Zyklus sie laufen. Dabei erhielt ich dieses Ergebnis: ...

Tatsächlich ist der Zyklus, der sich mit Länge 8 aus der Zahl 19 ergibt, für fast
der Hälfte der Startzahlen "das angesteuerte Ziel", auch der kurze Zyklus, der
sich aus der 5 ergibt, wird in 20% der Fälle zur "Senke", während die mit 44
Elementen sehr langen Zyklen gerade mal mit 3,25% bzw. 3,7% "angesteuert"
werden. ..

Auch interessant ist, wie sehr sich die mittleren Vorperioden unterscheiden: Bei
dem 19-er und 5-er Zyklus sind sie merklich länger als bei den vielelementigen Zyklen...

wirklich sehr spannende Beobachtungen.
So etwas kann man natürlich nur haben, wenn es mehr als einen Zielzyklus gibt.

Vermutlich wird sich bei anderen 3n+(2x+1)-Problemen etwas ähnliches zeigen,
vielleicht sogar auch bei 3n+1 für negative Startzahlen (da gibt es ja mehrere
Zielzyklen).

Gruss, Ingo.
Parent - - By Ulf Flörsheimer Date 2016-07-27 19:32
Hallo Ingo,

wenn ich jetzt keinen elementaren Denk- oder Programmierfehler mache, wird mir das Problem so langsam ein wenig unheimlich: Ich habe die Statistik mal insofern erweitert, als ich jetzt alle 5.000.000 Startzahlen (also jeweils alle Zahlen von 1 bis 5 Mio., von 1 bis 10 Mio., von 1 bis 15 Mio. etc.) eine Statistik über mittlere Vorperiodenlänge und erreichten Zyklus ausgebe. Ich erhalte dabei das hier:

--------------------------------
Startwerte von 1 bis 5000000
  1   113.28     702377   14.05%
  5   129.43    1000000   20.00%
19   119.39    2487195   49.74%
23    94.38     462786    9.26%
187    74.48     163205    3.26%
347    78.99     184437    3.69%
--------------------------------
Startwerte von 1 bis 10000000
  1   120.54    1403521   14.04%
  5   136.59    2000000   20.00%
19   126.63    4976195   49.76%
23   101.59     924691    9.25%
187    81.67     326513    3.27%
347    86.26     369080    3.69%
--------------------------------
Startwerte von 1 bis 15000000
  1   124.80    2104863   14.03%
  5   140.78    3000000   20.00%
19   130.86    7465247   49.77%
23   105.84    1386336    9.24%
187    85.84     489667    3.26%
347    90.49     553887    3.69%
--------------------------------
Startwerte von 1 bis 20000000
  1   127.81    2806386   14.03%
  5   143.77    4000000   20.00%
19   133.86    9954282   49.77%
23   108.85    1847607    9.24%
187    88.82     652807    3.26%
347    93.53     738918    3.69%
--------------------------------
Startwerte von 1 bis 25000000
  1   130.11    3510835   14.04%
  5   146.09    5000000   20.00%
19   136.19   12445276   49.78%
23   111.29    2307399    9.23%
187    91.20     813951    3.26%
347    95.93     922539    3.69%
--------------------------------
Startwerte von 1 bis 30000000
  1   132.07    4209751   14.03%
  5   147.96    6000000   20.00%
19   138.10   14932707   49.78%
23   113.09    2770029    9.23%
187    92.99     978918    3.26%
347    97.77    1108595    3.70%
--------------------------------
Startwerte von 1 bis 35000000
  1   133.60    4916444   14.05%
  5   149.53    7000000   20.00%
19   139.68   17426767   49.79%
23   114.87    3227565    9.22%
187    94.67    1136942    3.25%
347    99.47    1292282    3.69%
--------------------------------
Startwerte von 1 bis 40000000
  1   135.07    5613358   14.03%
  5   150.95    8000000   20.00%
19   141.09   19911083   49.78%
23   116.10    3692307    9.23%
187    95.97    1304759    3.26%
347   100.79    1478493    3.70%
--------------------------------
Startwerte von 1 bis 45000000
  1   136.31    6315329   14.03%
  5   152.16    9000000   20.00%
19   142.32   22401047   49.78%
23   117.34    4152438    9.23%
187    97.17    1468137    3.26%
347   102.03    1663049    3.70%
--------------------------------
Startwerte von 1 bis 50000000
  1   137.37    7020436   14.04%
  5   153.27   10000000   20.00%
19   143.42   24892293   49.78%
23   118.52    4613310    9.23%
187    98.37    1627782    3.26%
347   103.16    1846179    3.69%
--------------------------------
Startwerte von 1 bis 55000000
  1   138.33    7732823   14.06%
  5   154.23   11000000   20.00%
19   144.39   27381811   49.79%
23   119.66    5069051    9.22%
187    99.20    1786336    3.25%
347   104.22    2029979    3.69%
--------------------------------
Startwerte von 1 bis 60000000
  1   139.31    8420151   14.03%
  5   155.16   12000000   20.00%
19   145.33   29869376   49.78%
23   120.34    5536136    9.23%
187   100.16    1956954    3.26%
347   105.02    2217383    3.70%
--------------------------------

Die Prozentsätze verändern sich dabei so wenig, dass ich mich frage, ob es nicht möglich sein müsste, bei soviel Regelmäßigkeit von einer Zahl a priori sagen zu können, zu welchem Zyklus sie gehört. Aber ein Versuch, mich dieser Frage zu nähern, übersteigt wohl meine Fähigkeiten. Vielleicht ist es ja auch ein Trugschluss.

Auffallend auch, wenn man die Zahlen in ihrer Reihenfolge nach nach längsten Vorperioden durchmustert, wie oft die Rekordhalter in den 19-er Zyklus münden, obwohl der 5-er Zyklus im Mittel signifikant längere Vorperioden besitzt:

         1     0    4    1
         2     0    4    1
         3     8    8   19
         6     9    8   19
        12    10    8   19
        17    10    8   19
        21    13    8   19
        27    26    8   19
        54    27    8   19
        59    27    8   19
        77    30    8   19
        87    38    8   19
        99    67    8   19
       135   109    3    5
       270   110    3    5
       275   110    3    5
       365   113    3    5
       485   116    3    5
       645   119    3    5
       855   122    3    5
      1155   125    3    5
      1175   125    3    5
      1283   156    8   19
      1709   159    8   19
      2043   186    8   19
      4086   187    8   19
      4091   187    8   19
      4379   191    8   19
      4487   194    8   19
      5837   194    8   19
      5981   197    8   19
      7781   197    8   19
      7973   200    8   19
      8423   204    4    1
      9707   218    8   19
     11523   264    4    1
     20487   270    4    1
     23291   289    8   19
     31053   292    8   19
     32711   305    8   19
     43613   308    8   19
     45611   324    8   23
     60813   327    8   23
     71099   366    8   23
     94797   369    8   23
    189594   370    8   23
    189599   370    8   23
    252797   373    8   23
    299607   381    8   23
    335867   394    8   19
    447821   397    8   19
    589563   404    4    1
    622779   426    8   23
    668411   449    8   19
    891213   452    8   19
   1540011   467    8   19
   1563051   489    8   19
   2219523   726    8   19
   4439046   727    8   19
   4439051   727    8   19
   5261091   735    8   19
   6235371   743    8   19
   8091527   808    8   19
10788701   811    8   19
14384933   814    8   19
17960891   835    8   19
19934019   861    8   19
20717799   905    8   19
41435598   906    8   19
41435603   906    8   19
55247469   909    8   19
73663287   912    8   19
95591579   977    8   19
113293719   985    8   19
226587438   986    8   19
226587443   986    8   19
282914811  1007    8   19
502959639  1013    8   19
558213731  1039    8   19

Das ist schon alles außerordentlich exorbitant und seltsam merkwürdig.

Gruß Ulf
Parent - - By Wolfram Bernhardt Date 2016-07-27 23:39
Hallo!

Ich lese diesen interessanten Thread leider erst jetzt, sonst hätte ich das auch schnell mal eingetippt.

Deinen Beitrag über die Prozentzahlen finde ich besonders spannend.

Dass bei "1-5Mio." und "1-10Mio." dieselben Prozentzahlen auftauchen, müsste ja bedeuten, dass auch im Bereich "5Mio.-10Mio." dieselben Prozente auftauchen.
Und je größer der geprüfte Bereich ist, desto stabiler werden offenbar die Anteile.

Bringt es vielleicht etwas, heraufzufinden, wie *klein* man einen Bereich wählen kann, so dass die Prozente etwas in dem Bereich bleiben?

Du hast jetzt die Prozente auf zwei Stellen hinter dem Komma berechnet, im Idealfall ergibt sich diese Verteilung also mit 10.000 Zahlen.
Wenn sich diese Verteilung für 10.000 beliebige, aufeinanderfolgende Zahlen bestätigt, kann man vielleicht wirklich etwas voraussagen...

Ist erstmal nur sone Idee...

Viele Grüße,
     Wolfram
Parent - - By Ingo Althöfer Date 2016-07-28 09:09
Hallo Wolfram,

schön, dass Du dazugestossen bist.

Ich habe übrigens immer noch einen halbhohen Stapel Papier
mit Deinen/unseren Ergebnissen zu den Mosaiken mit 16
Teilen und den daraus legbaren 4x4-Gittern.
Dafür haben inzwischen einige Leute aus der AFoL-Szene
weitergehende Lösungen gefunden. Siehe dazu den folgenden
"Monster"-Thread im 1000-Steine-Forum:
http://www.1000steine.de/de/gemeinschaft/forum/?entry=1&id=362485#id362485
Das beste Ergebnis waren gefundene Lösungen für Mosaike mit
4 Farben und entsprechend 256 Teilen.

AFoL steht für "Adult Fans of LEGO", also "erwachsene LEGO-Freunde".

Ingo.
Parent - - By Wolfram Bernhardt Date 2016-07-28 18:57
Hallo Ingo!

Ich erinnere mich noch gut an die sehr schönen Stunden, die ich mit den Rätsel verbracht habe. Wir hatten ja sogar Lösungen gefunden, die auch an den Rändern zu jeweils gegenüberliegenden Rand gepasst haben. Und Spielereien mit magischen Quadraten.

Die größeren Rätsel sind auch sehr interessant. 16x16 mit 256 Teilen ist schon ein ziemlich großer Suchraum.
Den Thread in dem Lego-Forum habe ich mir durchgelese, da gibt es ja ein paar Leute, die sich mit dem Problem intensiv befasst haben und auch wissen, was sie tun. Insbesondere Dietmars Posts gefallen mir.

Ich habe ein paar Ideen zum großen Problem, weiss aber nicht, ob ich dazu komme. Wenn, würde ich mich auch im Lego-Forum melden.

Aber super, dass Du immer so schöne Aufgaben hast. Dieses Collatz-Problem ist auch sehr hübsch!
Da ich aber glaube, dass hier in Forum schon alles Wesentliche dazu geschrieben wurde, habe ich im Moment nichts beizutragen.

Aber immerhin kann ich auf eine nette Aufgabe hinweisen, die mich deshalb so fasziniert, weil ich mir daran seit längerem die Zähne ausbeisse.
Es wurde in der c't veröffentlicht und auch von einigen Leuten gelöst:

http://www.heise.de/ct/ausgabe/2015-23-Knobelaufgabe-c-t-Racetrack-2845878.html

Das Interessante daran ist, dass man (oder besser "ich") mit meinen üblichen "Waffen" hier gar nichts erreiche. Ob man da nun brute-force oder mit frühem Abschneiden, ob man depth-first oder breath-first sucht... immer explodiert einem weiter hinten im Suchbaum die Komplexität. Okay, das ist oft so. Aber das wirklich Gemeine ist, dass sich frühere Züge (und eben vor allem Fehler) erst deutlich später auswirken. Was man früh falsch macht, kommt das erst spät ans Licht. Und dann ist auch nicht mehr einfach festzustellen, welcher frühere Zug die Misere eingeleitet hat. Das ist ähnlich wie bei Schach, aber bei diesem Problem ist der Branching-Faktor viel viel höher und man sucht sich unten sinnlos tot, weil man weiter oben Fehler gemacht hat.

Zuletzt hatte ich eine nette Idee, mit der ich vermutlich doch zum Ende komme, aber die ist in der Implementierung doch komplexer als ich erst dachte und.. naja, man kommt ja zu nix

Viele Grüße,
      Wolfram
Parent - - By Ingo Althöfer Date 2016-07-28 20:09
Hallo Wolfram,

Wolfram Bernhardt schrieb:
... Insbesondere Dietmars Posts gefallen mir.

Als Problemlöser ist er ein Tier.

Zitat:
... Collatz-Problem ist auch sehr hübsch!
Da ich aber glaube, dass hier in Forum schon alles Wesentliche dazu geschrieben wurde ...

Ha. Mathematik ist nie fertig!

Zitat:
http://www.heise.de/ct/ausgabe/2015-23-Knobelaufgabe-c-t-Racetrack-2845878.html

Wenn ich mich nicht vertue, sollte es mit Rückwärts-Analyse
(und Rechnerhilfe) zu lösen sein.
Zustände sind Vektoren, deren erster Bestandteil der Ort und
der zweite Bestandteil die aktuelle Bewegungsrichtung sind.
Mehr verrate ich aber nicht.

Jetzt habe ich Dir hoffentlich nicht das Wochenende verdorben.
Ingo.
Parent - By Wolfram Bernhardt Date 2016-07-28 20:26
Ingo Althöfer schrieb:

Als Problemlöser ist er ein Tier.


War auch mein Eindruck.

Ingo Althöfer schrieb:

Wenn ich mich nicht vertue, sollte es mit Rückwärts-Analyse
(und Rechnerhilfe) zu lösen sein.
Zustände sind Vektoren, deren erster Bestandteil der Ort und
der zweite Bestandteil die aktuelle Bewegungsrichtung sind.
Mehr verrate ich aber nicht.


Das war eine der früherenSachen, an die ich gedacht hatte. Aber damit kam ich auch nicht hin. Es lief darauf hinaus, dass man vom Ziel zum Start läuft und das änderte dann nichts am Problem.

Mein aktueller Ansatz ist, dass ich zunächst den kürzesten Weg suche, der mit gerade Strecken zum Ziel führt und die Hinternisse nicht kreuzt. Das ist sehr einfach.

Die richtige Suche orientiert sich dann an dieser "Protostrecke". Je weiter man in ihrer Umgebung vorankommt, desto mehr Punkte gibt es in der Suche. Ich vermute (und hoffe inständig!), dass das dann recht direkt auf Ziels zuläuft...
Parent - - By Ingo Althöfer Date 2016-07-28 09:02 Edited 2016-07-28 09:04
Hallo Ulf,

sehr interessante Beobachtung.
Ich sehe inzwischen folgende Verallgemeinerung
der Collatzvermutung:

VERMUTUNG
Für eine beliebige natürliche Zahl x werde die 3*n + (2x + 1)-Variante
des Collatzproblems betrachtet.
(i) Dann gibt es endlich viele Zyklen Z(1), ... Z(k(x)), so dass jeder
beliebige natürliche Startwert in einen davon läuft.
(ii) Es gibt eine Wahrscheinlichkeitsverteilung p(1), ..., p(k(x)), so
dass asymptotisch für jedes i Anteil p(i) der Startwerte in den Zyklus
Z(i) läuft.

Frage: Wenn das stimmen sollte, sind dann alle p(i) rationale Zahlen?
  (Wenn ich wetten müsste, würde ich auf "ja" setzen, aber sicher bin
   ich nicht.)

Experimentell sollte man sich zu (i) und (ii) für relativ viele x "Gewissheit"
verschaffen können. Was Beweise angeht, dürfte es wirklich hartes Brot sein.

*********************************************************

Für ein einfacheres Problem ist die Sache wahrscheinlich leichter angreifbar.
Statt das Problem mit Abbildungsvorschrift n --> 3*n + (2x + 1)
betrachte man das einfachere
n --> n/2, falls n gerade und
n --> n + (2x + 1) für ungerade n.
Man lässt also den Faktor 3 weg im Vergleich mit den Problemen weiter oben.

Hier habe ich vor ein paar Tagen mal bewiesen: Jede Startzahl läuft in einen
Zyklus, der mindestens eine UNGERADE Zahl aus {1, 3, ..., 2x+1} enthält.
Es gibt (für x > 0) mindestens zwei Zyklen und natürlich höchstens x+1 viele.
(In allen per Hand beobachteten Fällen war die Zykelzahl nicht grösser als
O(Wurzel(x)).)
In diesem Problem hat man also ein Analogon zur Vermutung (i) von oben
schon bewiesen. Es sollte auch Aussage (ii) gelten. Über einen Beweis müsste
man nachdenken. Hier könnte auch die Anregung von Wolfram helfen, nach
konkreten Intervallen zu suchen, für die sich jeweils immer die gleiche Verteilung
ergibt.

Viele Grüsse, Ingo.
Parent - By Ingo Althöfer Date 2016-07-28 18:09
Hallo Zahlen-Freaks,

Ingo Althöfer schrieb:
Für ein einfacheres Problem ist die Sache wahrscheinlich leichter angreifbar.
... Man betrachte das einfachere
n --> n/2, falls n gerade und
n --> n + (2x + 1) für ungerade n
für eine natürliche Zahl x ...

... bewiesen ist: Jede Startzahl läuft in einen Zyklus, der mindestens eine
UNGERADE Zahl aus {1, 3, ..., 2x+1} enthält.
...
Über einen Beweis müsste man nachdenken.

Das habe ich jetzt gerade gemacht - und eine wunderschön einfache
Struktur gefunden. Am besten erkläre ich sie zunächst an einem Beispiel:

Sei 2x+1 = 15. Dafür ergeben sich die Zyklen
1->16->8->4->2->1  mit 4 geraden Zahlen (16, 8, 4, 2)
3->18->9->24->12->6->3  mit 4 gerade Zahlen (18, 24, 12, 6)
5->20->10->5  mit 2 geraden Zahlen (20,10)
7->22->11->26->13->28->14->7  mit 4 geraden Zahlen (22, 26, 28, 14)
15->30->15  mit einer geraden Zahl (30)

Es läßt sich jetzt leicht beweisen, dass genau
4/15 "aller" Startwerte in den 1-Zyklus laufen
4/15 "aller" Startwerte in den 3-Zyklus laufen
2/15 "aller" Startwerte in den 5-Zyklus laufen
4/15 "aller" Startwerte in den 7-Zyklus laufen
1/15 "aller" Startwerte in den 15-Zyklus laufen.
Diese Häufigkeitsverteilung gilt für jeden Block
von 15 aufeinanderfolgenden natürlichen Zahlen.

Der Nenner ist gerade der Wert 2x+1; die Zähler ergeben sich
aus den Anzahlen gerader Zahlen in den Zyklen.

Ich habe den Sachverhalt zwar nur für eine Handvoll von x-Werten
geprüft (nämlich für x= 1, 2, 3, 4, 5, 6, 7), bin aber sicher, dass
folgende Vermutung richtig ist:

Vermutung: Sei x natürliche Zahl und das System zu 2x+1 wie
oben betrachtet. Dann kommen in den sich ergebenden Zyklen
genau 2x+1 gerade Zahlen vor. Hat ein Zyklus k gerade Zahlen,
so ist die Häufigkeit des Konvergierens in ihn genau k/(2x+1).
Diese Verteilung ergibt sich für jeden Block von 2x+1 aufeinander
folgenden Startwerten.

Mein Bauchgefühl sagt mir, dass ein Beweis nicht schwer, sondern in
erster Linie Fleißarbeit sein dürfte.

Ingo.
Parent - - By Frank Brenner Date 2016-08-17 21:13 Upvotes 1

> Frage: Wenn das stimmen sollte, sind dann alle p(i) rationale Zahlen?  (Wenn ich wetten müsste, würde ich auf "ja" setzen, aber sicher bin ich nicht.)


Ob die p(i) alle gegen rationale Zahlen konvergieren kann ich weder mathematisch beweisen (hab ich auch noch nicht versucht, das wäre glaube ich eine Aufgabe für Genies)   noch bisher  empirisch nachweisen können.

Jeder Startwert der durch 5 teilbar ist landet auch im 5er Zyklus. p(5) ist also 20%

Mittlerweile habe ich die Verteilung bis 1000 Milliarden berechnet und man kann anhand der Beobachtung der Ziffernfolgen bestenfalls beim 347er Zyklus eine Konvergenz bei 3.7% aller Startwerte ganz schwach erhoffen.

Bei den anderen p(i) müsste man noch größere Bereiche berechnen um hier überhaupt eine  konvergenz mit dem Auge zu "sehen". 

Hier die Liste mit den Verteilungen bis 1000.000.000.000
Leider habe ich verdaddelt die größte auftauchende Zahl und den Startwert der zur längsten Sequenz für jeden Block  führt  zu speichern ...

Bis 1 Billion hat mein Rechner etwa 2 Tage gebraucht.

Code:


Verteilung - 100 Mio
1->   14039538
5->  
19->  9224554
23->  49786765
187-> 3256495
347-> 3692648

Verteilung - 1 mrd
1->   140384072
5->  
19->  92206715
23->  497917492
187-> 32547881
347-> 36943840

Verteilung - 10 Mrd
1->   1403463398
5->  
19->  922283095
23->  4979221818
187-> 325308457
347-> 369723232

Verteilung  - 100 Mrd
1->   14038998539
5->  
19->  9227451157
23->  49783417187
187-> 3251449770
347-> 3698683347

Verteilung - 1000 Mrd
1->   140469118273
5->  
19->  92254140547
23->  497785885830
187-> 32491242486
347-> 36999612864

Parent - - By Ingo Althöfer Date 2016-08-18 19:54
Hallo Herr Brenner,

danke für Ihre Berechnungen und Gedanken.

Nur zur Klarstellung für andere Leser: Es geht um das 3n+5-Problem:
* Bei einer geraden Zahl wird durch 2 geteilt.
* Bei einer ungeraden Zahl n geht es mit 3*n + 5 weiter.

Frank Brenner schrieb:

Ob die p(i) alle gegen rationale Zahlen konvergieren kann ich weder
mathematisch beweisen (hab ich auch noch nicht versucht, das wäre
glaube ich eine Aufgabe der Genies)   noch bisher  empirisch nachweisen können.

Jeder Startwert der durch 5 teilbar ist landet auch im 5er Zyklus. p(5) ist also 20%

Richtig: Jede Zahl, die durch 5 teilbar ist, ist es auch nach dem nächsten Schritt.
Und jede Zahl, die nicht durch 5 teilbar ist, ist es auch nach dem nächsten
Schritt nicht.

Ob alle durch 5 teilbaren Startwerte in den Zyklus 5->20->10->5 laufen, ist
äquivalent zur Frage, ob beim 3n+1-Problem alles in den 1->4->2->1-Zyklus
läuft.

Zitat:

Mittlerweile habe ich die Verteilung bis 1000 Milliarden berechnet und man
kann anhand der Beobachtung der Ziffernfolgen bestenfalls beim 347er Zyklus
eine Konvergenz bei 3.7% aller Startwerte ganz schwach erhoffen.

Scheint mir aber auch spekulativ.

Zitat:
...
Hier die Liste mit den Verteilungen bis 1000.000.000.000
Leider habe ich verdaddelt die größte auftauchende Zahl und den
Startwert der zur längsten Sequenz für jeden Block  führt  zu speichern ...

Frage aus Interesse: Mit welcher Arithmetik ist Ihr
Programm gelaufen?

*****
Auch wenn ich es nicht glaube, wöre es besonders spannend, wenn
beim 3n+5-Problem z.B. gälte:
alle durch 5 teilbaren Startwerte enden in einem Zyklus
ABER
nicht alle anderen Startwerte enden in einem Zyklus.

Ingo Althöfer.
Parent - - By Frank Brenner Date 2016-08-19 01:57
Im wesentlichen werden 64 Bit Zahlen (unsigned long long) verwendet.
Sobald ein Element größer ist als 6.148.914.691.236.517.203 ( (2^64-1-5) div 3) werden 128 bit Zahlen verwendet und zwar solange bis das Element wieder bequem in 64 bit passt.

Dieser 128 Bit Zahlentyp besteht dann aus hi und lo zu jeweils 64 Bit. Addition wird dann hier mit Übertrag berechnet.

Bei relativ kleinen Startwerten bis 1 billion gelangt die Berechnung  eher selten in den (langsameren) 128Bit  Pfad des Programms, so dass insgesamt die Laufzeit sehr schnell ist durch die 64 bit Arithmetik die von der CPU direkt ausgeführt wird.

Ob es größere Startwerte gibt die nicht in einem der 6 Zyklen landen, kann ich nicht beantworten. Bis 1 billion jedenfalls haben sich alle Startwerte für einen der 6 Zyklen entschieden.

> Ob alle durch 5 teilbaren Startwerte in den Zyklus 5->20->10->5 laufen, ist äquivalent zur Frage, ob beim 3n+1-Problem alles in den 1->4->2->1-Zyklus läuft.


Oh. Das sehe ich jetzt auch.  Die folge i1,i2,i3,i4..... 1  der normalen Collatz folge (2x+1) ist äquivalent zu 5*i1 , 5*i2, 5*i3 .... 5*1  zur 2x+5 Collatz folge.
Parent - By Frank Brenner Date 2016-08-19 15:19

> Die folge i1,i2,i3,i4..... 1  der normalen Collatz folge (2x+1) ist äquivalent zu 5*i1 , 5*i2, 5*i3 .... 5*1  zur 2x+5 Collatz folge.


Ich meine natürlich die 3x+1 Collatz bzw die 3x+5 verallgemeinerte Collatz Folge.
Parent - By Frank Brenner Date 2016-08-21 16:10
Was mir aufgefallen ist:

Wenn die normale Collatz folge 3x+1 mit einem n Bit Wert durchgeführt wird und anschließend eine m Bit Zahl genommen wird (m>n) die zumindest an den untersten n Bit mit der zuerst gewählten Zahl übereinstimmt,  dann durchläuft der Collatz Algorithmus in den ersten n+k Schritten jeweils den gleichen Zweig, wobei k die Anzahl der *3+1  Operationen  entspricht.

Wenn wir also den Pfad im Algorithmus mit 0 bezeichnen wenn durch 2 geteilt wird und  mit 1 bezeichnen wenn (*3+1)/2 gerechnet wird (die Division ist ja stets möglich) so gibt es einen mindestens n fachen Synchronen Pfaddurchlauf durch den Collatz Algorithmus für jede beliebige noch so große m Bit zahl die an den ersten n Bits mit unserer Referenzzahl übereinstimmt.

Wenn wir n = 32 setzen, so erzielen ca. 99% aller 32 Bit Zahlen innerhalb der ersten 32 Schritten eine echte Verkleinerung der Startzahl.
Diese 99% lässt sich dann auch auf die Menge der natürlichen Zahlen erweitern:
Für jedes noch so großes N (mit milliarden von stellen und mehr) aus den natürlichen Zahlen erzielt der Collatz Algorithmus bei 99% aller Zahlen im Bereich {0,1,2,...N} innerhalb der ersten 32 Schritten mindestens einmal eine echte Verkleinerung des Startwertes.

Dies ist insofern bemerkenswert, weil wenn der Beweis für ALLE natürlichen Zahlen gelänge die Collatz Vermutung bewiesen wäre.

Es ist möglich die 99% noch zu vergrößern:
So erzielen 99.11% aller 34 Bit zahlen in den ersten 38 Schritten eine Verkleinerung.
Dies lässt sich hier ebenfalls auf die Menge aller natürlichen Zahlen erweitern.

Schwierig ist aber die Tatsache dass für jedes noch so großes N es eine Startzahl gibt die in den ersten N Schritten niemals einen Folgenwert erzielt der kleiner ist als die Startzahl.
Von daher werden niemals exakt 100% erreicht
Für jedes noch so große N gibt es sogar unendlich viele Startzahlen die in den ersten N Schritten sich nicht verkleinern.
Parent - By Agamemnon Date 2016-07-27 05:05 Upvotes 1
Zitat:
Paul Erdos sagte einmal,
dass die Mathematik noch nicht reif für dieses Problem sei.


"Halt, Paul," entfuhr es da Kurt mit gödelhaftem Kichern,
"Magst du auch eine Ewigkeit nachsinnen:
Du kannst das Wahre nicht beweisen,
die Lüge nicht widerlegen
- wenn dir die Götter nicht hold sind."

Gruß
Jörg
Up Topic Hauptforen / CSS-Forum / Varianten des Collatz-Problems

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill