Neues altes Zahlenspiel

By Ingo Althöfer Date 2024-09-11 11:01

Hallo an alle Freunde von Zahlenspielen,

im Sommer 1930 hat Lothar Collatz an der LMU
München studiert. Dort hörte er auch eine Vorlesung
bei Dr. Fritz Lettenmeyer und fertigte eine Mit-
Schrift an: "Elementare Zahlentheorie".
In der Vorlesung gab Lettenmeyer auch ein Bildungsgesetz
für eine Zahlenfolge: Man beginnt mit einer
ungeraden positiven Zahl n.

Ist n=1, stoppt man.

Ist n > 1, bildet man n+1 und teilt so lange durch
2, bis sich wieder eine ungerade Zahl ergibt. Auf
diese neue Zahl wendet man wieder die Regel an:
+1 und wiederholt durch 2 teilen.
Man kann leicht beweisen, dass die Folge für jede
Startzahl in endlich vielen Schritten in der 1 endet.

Nimmt man statt "n -> n+1" die Regel "n -> 3n+1",
hat man die weltberühmte Collatz-Regel mit der
zugehörigen offenen Frage. Collatz stellte sich die Frage
erstmals 1937.

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

In Anlehnung an die Lettenmeyer-Regel betrachte
man folgendes Zahlen-Spiel:
2 Spieler, die abwechselnd ziehen.
Wer am Zug ist, ist mit einer ungeraden Zahl n > 1 konfrontiert.
Der Spieler bildet entweder n+1 oder n-1.
Danach wird halbiert, bis wieder eine ungerade Zahl erreicht ist.
Ist diese = 1, hat der Spieler gewonnen, der das erreicht hat.
Ist sie > 1, ist der andere Spieler am Zug.

Bemerkung 1: Egal, mit welcher ungerade Zahl begonnen wird
und was die Spieler ziehen, endet das Spiel in endlich vielen
Zügen.

Bemerkung 2: Mit Rückwärtsanalyse kann man bestimmen,
welche ungeraden Zahlen für den Spieler am Zug gewonnen sind,
wenn beide perfekt spielen.

Beispiele:
* 3 darf zu 3-1 = 2 oder zu 3+1 = 4 verändert werden.
2 UND 4 werden auf 1 "runterhalbiert", also ist 3
ein trivialer Gewinn für den Spieler am Zug.

* 5 -> 4 -> 1 oder 5 -> 6 -> 3
Also siegt der Spieler am Zug, wenn er auf 4 geht.

* 7 -> 6 -> 3 oder 7 -> 8 -> 1
Also Sieg, indem man auf 8 zieht.

* 9 -> 8 -> 1 oder 9 -> 10 -> 5
Also Sieg durch Zug auf 8.

* 11 -> 10 -> 5 oder 11 -> 12 -> 3
Also Verlust, weil 5 und 3 beide für den Spieler am
Zug gewonnen sind.

* 13 -> 12 - > 3 oder 13 -> 14 -> 7,
also Verlust für 13.

Es ergibt sich folgende Status-Folge für die
nächsten Zahlen:

Stat(15) = win durch 16
Stat(17) = win durch 16

Stat(19) = Loss

Stat(21) = win durch 22
Stat(23) = win durch 22
Stat(25) = win durch 26
Stat(27) = win durch 26

Stat(29) = Loss

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

1993 habe ich das letzte Mal selbst programmiert!
Danach haben das immer nur Studenten und Doktoranden
für mich gemacht. Jetzt habe ich keine mehr...

Frage: Wer mag für ein größeres Anfangsstück der Menge
der ungeraden Zahlen die win-Loss-Stati mit Hilfe eines
Programms bestimmen?

Meine Vermutung:
Es kommen nie mehr als zwei "Loss" direkt hintereinander.
Stellen mit Doppel-Loss sind zum Beispiel 11,13 und 47,49.

Meine Fragen:
* In welchen Stellungen hat der Spieler am Zug zwei Gewinnzüge?
* Gibt es unendlich viele Stellen mit zwei oder mehr "Loss" hintereinander?
* Gibt es ein k, so dass zwischen 2-hoch-k und 2-hoch-(k+1)
mehr als ein Doppel-Loss existiert?
* Erkennt jemand allgemeine Strukturen oder gar DIE Gesamtstruktur?

Rückmeldungen gerne im Forum oder mit PN.
Viele Grüße, Ingo.

By Michael Bechmann Date 2024-09-11 13:34 Edited 2024-09-11 13:41

Hallo, Herr Althöfer,

Nachfragen:

Darf der Spieler bei jedem Schritt bei ungeraden Zahlen zwischen n+1 oder n-1 wählen, oder ist er nach dem Startwert für alle folgenden Schritte auf "n+1" oder "n-1" festgelegt?

"2 Spieler, die abwechselnd ziehen." und "Ist diese = 1, hat der Spieler gewonnen, der das erreicht hat."
Das verstehe ich nicht: Ich ziehe die 2. Im ersten Schritt ist 2:2=1 und habe gewonnen. Wenn der Andere eine andere Zahl zieht, braucht nämlich mehr als einen Schritt um auf 1 zu kommen.

Was mit "stat" und "loss" gemeint ist, habe ich auch nicht verstanden.

Bei einer anderen beliebigen Zahl als Startwert kann man das Spiel mit Excel ausprobieren:
In A1 trage ich eine Startzahl ein
In A2 die Formel "=WENN(REST(A1;2)=1;A1+1;A1/2)" und ziehe mit der Maus an A2 nach unten durch. So entsteht eine rekursive Folge und ich sehe schlicht, in welcher Zeile die 1 steht.
Was mir dabei auffällt ist, dass sehr schnell eine Zweierpotenz 2^x entsteht und die in (x-1) Schritten die 1 erreicht ist.

mfg Milbe.

By Ingo Althöfer Date 2024-09-11 14:21

Hallo Herr Bechmann,
danke für die Nachfragen.

> Darf der Spieler bei jedem Schritt bei ungeraden Zahlen zwischen
> n+1 oder n-1 wählen,

Genau. Die Wahl gilt immer nur für den aktuellen Zug.

> "2 Spieler, die abwechselnd ziehen." und "Ist diese = 1, hat der Spieler
> gewonnen, der das erreicht hat."
> Das verstehe ich nicht: Ich ziehe die 2...

Die 2 kann niemand ziehen.
Das Spiel beginnt, indem ein Schiedsrichter oder ein Zufallsgenerator
eine ungerade Zahl n vorgibt und auch festlegt, welcher der beiden
Spieler am Zug ist.

> Was mit "stat" und "loss" gemeint ist, habe ich auch nicht verstanden.

"Stat" ist Abkürzung für "Status", "loss" ist englisch für "Verlust",
"win" ist englisch für Gewinn.

> Bei einer anderen beliebigen Zahl als Startwert kann man das Spiel
> mit Excel ausprobieren: ...

Mit Rückwärtsanalyse habe ich etwas anderes gemeint.
Ich glaube auch nicht, dass man die Rückwärtsanalyse
mit Excel durchführen kann - aber ich habe auch nie mit
Excel programmiert.

> ... Was mir dabei auffällt ist, dass sehr schnell eine Zweierpotenz
> 2^x entsteht und die in (x-1) Schritten die 1 erreicht ist.

Ich verstehe nicht, was Sie meinen.

Aber wenn das Spiel mit einer Zahl der Größenordnung 2^n beginnt,
dauert eine Partie nie wesentlich länger als n Züge.

Viele Grüße, Ingo Althöfer.

By Michael Bechmann Date 2024-09-11 14:52 Edited 2024-09-11 15:02

Hallo,

Ich vermute, dass es hauptsächlich darauf ankommt, dass der Schiedsrichter oder der Zufall eine geeigneten Startwert vorzugeben.
Für die Regel nach dem Startwert gibt es kaum Optionen, um strategische Entscheidungen zu treffen: Der Spieler kann sich nur für "n+1" oder "n-1" entscheiden.

zu den Zweierpotenzen

Beispiel: Ich verwende die Regel "Rest/2 = 1" addieren 1 und dann im nächsten Schritt zwangsläufig (wegen Rest/2 = 0) durch 2 dividieren.

Ich nehme eine zufällige hinlänglich große Zahl als Startwert: 267112462 (Die habe ich mit einer Zufallsfunktion "ermittelt", hier mit Excel "=Zufallsbereich(1;10000000000) ) und der Zufall hat mir den Gefallen getan,
nach einigen Schritten eine "größere" Zweierpotenz zu geben, hier 256=2^8 und in 7 weiteren Schritten hat man das Ziel, also 1, erreicht.
Meistens endet es auf 8;4;2;1 oder 4;2;1 - aber die Folge endet stets auf Zweierpotenzen.
Das müsste man mathematisch aber auch beweisen, nicht nur vermuten.

Das scheint ein wesentlicher Teil der von Ihnen erwähnten "allgemeinen Struktur" zu sein.

267112462
133556231
133556232
66778116
33389058
16694529
16694530
8347265
8347266
4173633
4173634
2086817
2086818
1043409
1043410
521705
521706
260853
260854
130427
130428
65214
32607
32608
16304
8152
4076
2038
1019
1020
510
255
256
128
64
32
16
8
4
2
1

By Ingo Althöfer Date 2024-09-11 14:56

Michael Bechmann schrieb:

Meistens endet es auf 8;4;2;1 oder 4;2;1 -
aber die Folge endet stets auf Zweierpotenzen.
Das müsste man mathematisch aber auch beweisen, nicht nur vermuten.

Das ist so, Beweis einfach.

Aber zurück zum Spiel. Ich schlage eine Musterpartie zwischen uns beiden vor.
Um Ihnen einen kleinen Vorteil zu gewähren, gebe ich als Startzahl 89 vor.
Sie dürfen entscheiden, ob Sie beginnen wollen oder ich.
Falls Sie beginnen wollen, machen Sie einfach Ihren ersten Zug.

Gutes Gelingen, Ingo Althöfer.

By Michael Bechmann Date 2024-09-11 15:11

Wir machen es mal: 89. Wo dabei der Vorteil ist, erkenne ich noch nicht.

89 ist eine ungerade Zahl und habe die Option 89-1 oder 89+1.

Ich nehme 89-1=88.

By Ingo Althöfer Date 2024-09-11 15:12

Michael Bechmann schrieb:

Wir machen es mal: 89. Das ist eine ungerade Zahl und habe die Option 89-1 oder 89+1.
Ich nehme 89-1=88.

Sehr schön. 88-44-22-11, also bin ich bei 11 dran.
Ich gehe von 11 auf 10 und fühle mich gut.

By Michael Bechmann Date 2024-09-11 15:29 Edited 2024-09-11 15:32

Der Regel nach 10:2=5 und dann 5+1 = 6.

("5-1" wäre ein wenig doof. ☺️)

By Ingo Althöfer Date 2024-09-11 15:43

Michael Bechmann schrieb:

Der Regel nach 10:2=5 und dann 5+1 = 6.

("5-1" wäre ein wenig doof. ☺️)

Immerhin hätte 5-1 gewonnen.

6 -> 3.
Dann spiele ich auf 3+1 -> 2 -> 1.
Also habe ich gewonnen.

Aber ich sehe, die Regeln sind jetzt klar angekommen.
Viele Grüße, Ingo.

By Michael Bechmann Date 2024-09-11 16:33 Edited 2024-09-11 16:35

Ich habe mir noch mal die klassische Collatzfolge angesehen "n -> 3n+1" und stelle fest, dass sie auch auf "4-2-1" endet, unabhängig, welchen Startwert ich(!) nehme.
Soweit ich weiß ist das aber noch nicht vollständig bewiesen.

So konnte ich "Das ist so, Beweis einfach." nicht so ohne weiteres akzeptieren.

By Ingo Althöfer Date 2024-09-11 16:40

Bitte keinen Nebenschauplatz aufmachen.
Einfach das Spiel mit Zügen n-1 und n+1 analysieren.

By Wolfram Bernhardt Date 2024-09-11 14:47

Hallo Ingo!

Alles klar, ich mache mich bei nächster Gelegenheit dran.

Liebe Grüße
Wolfram

PS: Wie Du siehst, habe ich es immer noch nicht geschafft, mich bei schachcomputer.info anzumelden. Ich spiele wohl zu viel

By Wolfram Bernhardt Date 2024-09-11 16:57 Edited 2024-09-11 17:20

Hallo Ingo!

Wie groß ist denn ein "größeres Anfangsstück"? Ich habe hier gerade etwa Code zusammengesteckt, der den Stat() für die Zahlen bis 2.000.000.000 berechnet (dauert ca. 20 Sekunden).

Für diesen Raum kann ich zu den Fragen etwas sagen:

* In welchen Stellungen hat der Spieler am Zug zwei Gewinnzüge?
Überraschenderweise nur bei einer: der 3.

* Gibt es unendlich viele Stellen mit zwei oder mehr "Loss" hintereinander?
Antwort a)
Im Raum bis 1.000.000.000 gibt es 14 Double-Losses.
Im Raum bis 2.000.000.000 kommen keine weiteren hinzu, ist aber eher ein Zufall.
Jeder Doubleloss liegt grob beim 4fachen des vorherigen:

DoubleLoss: 11, 13
DoubleLoss: 47, 49
DoubleLoss: 191, 193
DoubleLoss: 767, 769
DoubleLoss: 3071, 3073
DoubleLoss: 12287, 12289
DoubleLoss: 49151, 49153
DoubleLoss: 196607, 196609
DoubleLoss: 786431, 786433
DoubleLoss: 3145727, 3145729
DoubleLoss: 12582911, 12582913
DoubleLoss: 50331647, 50331649
DoubleLoss: 201326591, 201326593
DoubleLoss: 805306367, 805306369

Der nächste wäre demnach bei um die 3.200.000.000 zu erwarten, also außerhalb meines jetzigen Bereichs.
Das sieht doch recht stetig aus, darum vermute ich, es gibt unendlich viele DoubleLosses.

Antwort b)
Mehr als 2 Losses hintereinander gibt es nicht.

* Gibt es ein k, so dass zwischen 2-hoch-k und 2-hoch-(k+1) mehr als ein Doppel-Loss existiert?

Nein. In Intervallen, in denen ein DoubleLoss liegt, liegt kein weiteres. Aber nicht in jedem Intervall liegt ein DoubleLoss.
In diesem Zahlenraum trifft sogar zu, dass ab dem Intervall 8-16 in jedem zweiten Intervall genau ein DoubleLoss liegt.
(Das ergibt sich natürlich auch aus der erwähnten Ver-4-fachung der Doublelosses)

DoubleLoss in Intervall 8 - 16: 11, 13
DoubleLoss in Intervall 32 - 64: 47, 49
DoubleLoss in Intervall 128 - 256: 191, 193
DoubleLoss in Intervall 512 - 1024: 767, 769
DoubleLoss in Intervall 2048 - 4096: 3071, 3073
DoubleLoss in Intervall 8192 - 16384: 12287, 12289
DoubleLoss in Intervall 32768 - 65536: 49151, 49153
DoubleLoss in Intervall 131072 - 262144: 196607, 196609
DoubleLoss in Intervall 524288 - 1048576: 786431, 786433
DoubleLoss in Intervall 2097152 - 4194304: 3145727, 3145729
DoubleLoss in Intervall 8388608 - 16777216: 12582911, 12582913
DoubleLoss in Intervall 33554432 - 67108864: 50331647, 50331649
DoubleLoss in Intervall 134217728 - 268435456: 201326591, 201326593
DoubleLoss in Intervall 536870912 - 1073741824: 805306367, 805306369

* Erkennt jemand allgemeine Strukturen oder gar DIE Gesamtstruktur?

Auf die Schnelle nicht. Und damit habe ich leider etwas mit Donald Trump gemeinsam, der erkennt gar nichts, erst Recht keine Strukturen. Mein Gott, war das schlimm heute morgen. Aber ich schweife ab.

Liebe Grüße
Wolfram

By Ingo Althöfer Date 2024-09-11 17:23 Upvotes 1

Hallo Wolfram,

das sieht schon richtig gut aus!
Und mit Deinen Daten und meinem Startstück bis 161
kann ich eine ziemlich präzise Vermutung aufstellen.

> Im Raum bis 1.000.000.000 gibt es 14 Double-Losses...
> Jeder Doubleloss liegt grob beim 4fachen des vorherigen:

> DoubleLoss: 11, 13

Mitte ist 12 = 4+8

> DoubleLoss: 47, 49

Mitte ist 48 = 16+32

> DoubleLoss: 191, 193

Mitte ist 192 = 64+128

> DoubleLoss: 767, 769

Mitte ist 768 = 256+512

usw.

Normal ist die Sequenz WWL WWL WWL bis auf die LL-Stellen
und bis auf einige WWWW-Stellen.

Die WWWW-Blöcke sind bei
3, 5, 7, 9
Mitte 6 = 2+4

21, 23, 25, 27
Mitte 24 = 8+16

93, 95, 97, 99
Mitte 96 = 32+64
usw

Sehr interessant, dass die Struktur so einfach ist.

Dank und Gruss, Ingo.

By Wolfram Bernhardt Date 2024-09-11 17:34 Edited 2024-09-11 17:37

Ich habe hier gerade noch ein Ergebnis, das mich etwas an meinem Code zweifeln lässt, aber es scheint wahr zu sein:

Ich habe mir noch die Frage gestellt: Wenn man gewinnt, geschieht das öfter durch -1 oder +1?

Es stellt sich heraus: Exakt(!!) gleich oft.

-1 zum Gewinnen gewählt: 333333333
+1 zum Gewinnen gewählt: 333333333

Bei den Zahlen bis 2.000.000.000 ist Hälfte ungerade.
Und offenbar führt

* 1/3 der Stellungen durch -1-Wählen zum Gewinn
* 1/3 durch +1-Wählen zum Gewinn und
* 1/3 ist verloren.

Kann da was dran sein?

Ach, doch. Klar. Es gibt ja keine Doppel-Gewinne. Das heisst, von zwei aufeinanderfolgenden Gewinn-Stellungen geht immer eine nach oben (7 +1 -> 8) und die nächste nach unten (9 -1 -> 8). Doch, dann stimmt das wohl

Liebe Grüße
Wolfram

By Ingo Althöfer Date 2024-09-12 08:53

Lieber Wolfram,

danke für Dein Programmier-Einsatz.
Ich hatte vorher per Hand die spieltheoretischen Werte bis n=150
ermittelt und dabei das Gefühl bekommen, dass es eine glatte
Struktur geben dürfte. Dass es aber so glatt wird wie von Dir
gefunden, hatte ich nicht erwartet.
Jedenfalls kann das "n-1,n+1 Spiel" jetzt als vollständig gelöst betrachtet werden.

Etwas anders scheint es beim "n+1,n+3 Spiel" zu sein. Da habe ich bisher
nur die Vermutung zustande gebracht, dass Loss-Stellungen nie als Einzel
auftreten, sondern immer mindestens als Zweier-Gruppen.

Viele Grüße, Ingo.

By Wolfram Bernhardt Date 2024-09-12 10:54

Hallo Ingo,

freut mich sehr, wenn ich da helfen konnte. Ich hatte gestern tatsächlich spontan eine ganz gut Idee, mit der sich das einfach und recht effizient implementieren liess und dann fix läuft, ohne dass ich groß optimiert habe. Das müsste genauso auch für n+1/n+3 funktionieren.

Würde es was bringen, das auch mal durchlaufen zu lassen?

By Ingo Althöfer Date 2024-09-12 11:59

Hallo Wolfram,

Wolfram Bernhardt schrieb:

Ich hatte gestern tatsächlich spontan eine ganz gut Idee, ...
Das müsste genauso auch für n+1/n+3 funktionieren.

Würde es was bringen, das auch mal durchlaufen zu lassen?

Ja, unbedingt.
Dank und Gruß, Ingo.

By Wolfram Bernhardt Date 2024-09-13 17:07

Hallo Ingo!

Ich habe auf +1/+3 umgestellt. Die Ergebnisse sind ähnlich regelmäßig wie bei -1/+1. Und wenn ich richtig aufgepasst habe, treffen alle Deine Annahmen zu.

1)
Es gibt deutlich mehr Doublelosses. Und ihre Anzahl verdoppelt sich sehr stabil pro Intervall:

DoubleLosses in Intervall 2 - 4: 0
DoubleLosses in Intervall 4 - 8: 0
DoubleLosses in Intervall 8 - 16: 1
DoubleLosses in Intervall 16 - 32: 2
DoubleLosses in Intervall 32 - 64: 3
DoubleLosses in Intervall 64 - 128: 7
DoubleLosses in Intervall 128 - 256: 14
DoubleLosses in Intervall 256 - 512: 27
DoubleLosses in Intervall 512 - 1024: 55
DoubleLosses in Intervall 1024 - 2048: 110
DoubleLosses in Intervall 2048 - 4096: 219
DoubleLosses in Intervall 4096 - 8192: 439
DoubleLosses in Intervall 8192 - 16384: 878
DoubleLosses in Intervall 16384 - 32768: 1755
DoubleLosses in Intervall 32768 - 65536: 3511
DoubleLosses in Intervall 65536 - 131072: 7022
DoubleLosses in Intervall 131072 - 262144: 14043
DoubleLosses in Intervall 262144 - 524288: 28087
DoubleLosses in Intervall 524288 - 1048576: 56174
DoubleLosses in Intervall 1048576 - 2097152: 112347
DoubleLosses in Intervall 2097152 - 4194304: 224695
DoubleLosses in Intervall 4194304 - 8388608: 449390
DoubleLosses in Intervall 8388608 - 16777216: 898779
DoubleLosses in Intervall 16777216 - 33554432: 1797559
DoubleLosses in Intervall 33554432 - 67108864: 3595118
DoubleLosses in Intervall 67108864 - 134217728: 7190235
DoubleLosses in Intervall 134217728 - 268435456: 14380471
DoubleLosses in Intervall 268435456 - 536870912: 28760942
DoubleLosses in Intervall 536870912 - 1073741824: 57521883

2) Triple-Losses gibt es nun auch, viele. Aber keine 4fach- oder höhere Loss-Serien.

3) Double-Wins (also Gewinn bei +1 oder +3) gibt es nun auch sehr viele: 71428571 Stück.

4) Und was führt öfter zum Gewinn? (Dabei sind die Stellungen aus Punkt 3 nicht mitgezählt)

+1 zum Gewinnen gewählt: 285714285
+3 zum Gewinnen gewählt: 285714285

Erstaunt mich wieder, ist aber wohl derselbe Effekt wie vorher; was für die 5 die +3, ist für die 7 die +1.
Allgemeiner: Für jede Zahl, für die +3 gewinnt, gewinnt ihr ungerader Nachfolger mit +1, ist keine allzu große Erkenntnis

Liebe Grüße
Wolfram