Hallo Thomas,

jetzt habe ich Deine Darstellungen besser einordnen können.
Du schriebst ja "bis zum ersten mal 5 oder 7 auftaucht".

Die 5 kommt in der Mitte der einen Runde zur 13 vor:
13 -> 40-20-10-5 -> 26-13

Und die 7 kommt in ihrer eigenen 1-Runden-"Lösung" vor
und in der Mitte der 1-Runden-Lösung zur 9:

9 -> 28-14-7 -> 36-18-9

Somit interpretiere ich, was Du gerechnet hast, so, dass es
zumindest bis 100 Millionen nur die drei Basiszykel zu 7, 9, 13 gibt.

Viele Grüße, Ingo.

__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)

Hallo Ingo,

Ja genau, so war es gedacht.

Viele Grüße, Thomas

Hallo Thomas,

ein paar Stunden habe ich gebraucht, um Deine
Daten zu verdauen - und bin mehr und mehr begeistert.
Startwert 95 im 3n+1/5n+1 ist ideal, wenn man als
Lehrer einer Vertretungsstunde einen Klugscheißer in
der Klasse hat.

Man erklärt der Klasse das 3n+1-Problem und läßt
"die Bestien" dann auf Startwert 27 los. Da braucht es
gut 100 "Einzel"schritte, um zur 1 zu gelangen. Nun
stelle man sich einen Schüler vor, der nach 7 oder 8
Minuten kräht, er habe es raus. Die anderen sind derweil
noch heftig am "arbeiten". Dem Überflieger gibt man dann
eine "kleine" Erweiterungsaufgabe:
Das 3n+1/5n+1-Problem mit Startwert 95 und verrät
ihm auch noch, dass am Ende 7 rauskommt. Er solle das
auch noch mal schnell verifizieren.

Hintergrund: Es gibt eine Leistungsszene im Kopfrechnen,
in der auch SchülerInnen und StudentInnen aus Jena vorne
dabei sind. Einer von denen wurde Weltmeister und sass
auch bei mir in der Vorlesung...

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

Ähnlich zu dem 3n+1/5n+1 ist das
15n+1/n+1-Problem:
Ungerades n wird mit 15 multipliziert, dann plus 1.
Runterhalbieren, bis ungerade.
Dann plus 1. Wieder runterhalbieren.
(Es ergibt sich der gleiche Quotient 15/16 wie beim 3/5-Problem.)

Gibt es da auch solch einen "Klugscheißer-Schreck" wie
die 95 bei 3/5 ?

Die ersten drei Werte geben übrigens 1-Zyklen:
1 -> 16-8-4-2-1 -> 2-1

3 -> 46-23 -> 24-12-6-3

5 -> 76-38-19 -> 20-10-5

Ob es weitere Zyklen gibt, weiß ich nicht.

Dank und viele Grüße, Ingo.

__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)

Hallo zusammen,

ich muss eine kleinere (größere?) Korrektur an meiner Auswertung anbringen.

Zum Spaß hatte ich die Berechnungen mal mit einer C++ Library für 128 Bit Integers wiederholt, und Abweichungen festgestellt.
Es stellte sich heraus, das mein Check für einen 64-Bit Überlauf an einer Stelle um eine Zeile verrutscht war und deswegen nicht richtig griff.

Bereits ab dem Startwert 1489 kommt man in einen Bereich > 64 Bit, d.h. > 18446744073709551615.
Und schon ab 3859 wird auch der 128 Bit Bereich verlassen, d.h. > 340282366920938463463374607431768211455.

Für den Bereich 1489 - 3859 kommt aber offenbar auch alles zurück zu der "Fixrunde 7".

Ich vermute das sich das auch so fortsetzt, aber man bräuchte eine C++ Library für Integers beliebiger Größe um das zu überprüfen.
Solche Libraries gibt es, wenn ich dazu komme probiere ich das mal aus.

Viele Grüße, Thomas

Hallo Thomas,

wie war denn Dein bisheriges Programm mit den
Overflows umgegangen?

Dank und viele Grüße, Ingo.

__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)

Liebe Leute, online bin ich in einem Schreib-Forum aktiv, wo jeden
Monat ein anderes Thema gegeben ist, zu dem Kurzgeschichten
mit höchstens 10.000 Zeichen gesucht werden. Für den August 2023
lautet das Thema "Dumm gelaufen." Dazu ist mir aus dem Stehgreif
folgende Geschiche eingefallen.

3n+1 für Klugscheißer
Ingo Althöfer
Eingereicht am 2. August 2023 beim Schreiblust-Wettbewerb.

Igor war ein Oberschlauer, zumindest in Mathe. Rechnen
konnte er wie ein Teufel, sei es im Kopf oder auf dem
Papier. Auf die Klassenkameraden in der 5c blickte er
mit Arroganz hinab.

Eines Tages gab es eine Vertretungsstunde durch den
Mathelehrer, Herrn Osterhage. Der wollte sich in der
Stunde nicht verausgaben und stellte zu Beginn eine
ganz einfache Rechenregel vor:

Wenn die aktuelle Zahl n ungerade ist, bildet man 3n+1.
Das Ergebnis ist eine gerade Zahl. Die teilt man so
lange durch 2, bis es nicht mehr geht. Dann bildet man
wieder „mal 3 plus 1“, teilt dann wieder durch 2, bis
es ungerade wird, usw. Hier habt ihr ein Beispiel:

1 -> 4 -> 2 -> 1.
Aha, von der 1 kommt man also ganz schnell wieder zur 1.

Probieren wir die 3.
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
Also führt auch die 3 nach kurzer Zeit zur 1.

Und wisst ihr was? Schlaue Leute vermuten, dass, egal
mit welcher ungeraden Zahl es losgeht, man immer zur 1
gelangt. Und jetzt seid ihr dran: Fangt, jeder für sich,
bei der 27 an und rechnet auf dem Papier, bis ihr bei
der 1 seid. Wer das als erster richtig fertig hat,
bekommt ein Duplo!

Das ließ Igor sich nicht zwei Mal sagen. Nach 6 Minuten
und 28 Sekunden [sic!] hatte er die vollständige Lösung
mit ihren 93 Schritten, während alle anderen noch mit
den Griffeln in der Hand schwitzten.

Igor rannte vor, um sich das Duplo abzuholen. Aber Herr
Osterhage hatte eine Überraschung für ihn in Petto. Leise,
um die anderen nicht zu stören, sagte er: „Gut gemacht,
Igor. Aber ich biete Dir ein Upgrade an: Statt des einen
Duplo bekommst Du drei, wenn Du die folgende etwas
schwerere Aufgabe löst.“

Beim 3n+1/5n+1-Problem passiert folgendes: Es geht mit
einer ungeraden Zahl n los. Dazu bildet man 3n+1 und
halbiert dann so oft, bis man wieder bei einer ungeraden
Zahl m ist. Dazu bildet man 5m+1 und halbiert wieder
runter bis zu einer ungeraden Zahl.

Hier ist ein einfaches Beispiel:
7 -> 22 -> 11 -> 56 -> 28 - > 14 -> 7.
Die 7 landet also nach einer Runde wieder bei sich selbst.
Wenn Du es schaffst, bis zum Ende der Stunde auszurechnen,
wie man ausgehend von der 95 zur 7 gelangt, bekommst Du
drei Duplos. Willst Du Dich darauf einlassen?

Igor, etwas zu laut: „Natürlich, da werde ich mich mal
etwas anstrengen. Super, drei Duplos für lau.“ Er begann
und rechnete und rechnete und rechnete ... und hörte auch
das Pausenklingeln nicht. Herr Osterhage kam zu ihm und
fragte: „Na Igor, wie weit bist Du?“ „Noch nicht ganz fertig.
Können Sie mich bitte in der Klasse einschließen? Die drei
Duplos bekomme ich doch auch, wenn ich es bis zum Ende der
großen Pause geschafft habe?! Bitte!“

Ossi tat ihm den Gefallen. Igor schaffte es aber nicht -
und musste sich zu Beginn der nächsten Stunde den Spott
der Klassenkameraden gefallen lassen.

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

Erläuterungen:

* Das 3n+1-Problem und die zugehörige Vermutung stammten
von Lothar Collatz aus dem Jahr 1937.

* Das 3n+1/5n+1-Problem hat der Klugscheißer Ingo A 2023
formuliert. Er hat auch die Vermutung aufgestellt, dass,
egal bei welcher ungeraden Zahl man beginnt, am Ende entweder
7 oder 9 oder 13 herauskommt.

* Die Identifizierung der 95 als besonders schwerer Startwert
für das 3n+1/5n+1-Problem gelang Thomas Zipproth.

* Die Lösung für 95 wird Ende des Monats August verraten.

* Ossi war der Lieblingslehrer von Ingo A. In acht der neun
Jahre auf dem Gymnasium unterrichtete er ihn in Mathe. Dieser
Fixpunkt half dem hyperaktiven Kind als stabilisierende Größe
im Schulalltag.

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

Herzliche Grüße, Ingo.

__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)

Hallo Ingo,

Open Source ist sowieso besser, deshalb im Anhang jetzt der komplette Source Code in C (auch zur Kontrolle) und das Ergebnis.
Der Code sollte mit den Kommentaren leicht verständlich sein und ist ja auch nur 60 Zeilen lang.

Man sollte halt nicht spät nachts oder in Zeitnot etwas programmieren, nur weil es einen interessiert.
Sollte ich nach 35 Jahren Software Entwicklung eigentlich wissen.

Ein Auszug aus dem Ergebnis:

1: Startwert
2: Anzahl Runden
3: Anzahl Veränderungen des Wertes
4: Größter vorkommender Wert

Die Overflows werden dann allmählich häufiger:

Viele Grüße, Thomas

Angehängte Dateien

Collatz35.txt (13,5 KB, 12x aufgerufen)

Das Programm in FreeBasic würde etwa so aussehen:


Dim As UInt64 max64_3 = 18446744073709551615 / 3 - 1
Dim As UInt64 max64_5 = 18446744073709551615 / 5 - 1
Dim As UInt64 biggest_number
Dim As Integer runde

Function sequence(n As UInt64) As Integer
Dim As Integer count = 0
runde = 1
biggest_number = 0

Do
If n > max64_3 Then Return -1 ' Check auf Overflow (nach der Multiplikation)

n = 3 * n + 1
count += 1
If n > biggest_number Then biggest_number = n

While (n Mod 2) = 0
n /= 2
count += 1
Wend
If n < 8 Then Return count

If n > max64_5 Then Return -1 ' Check auf Overflow (nach der Multiplikation)

n = 5 * n + 1
count += 1
If n > biggest_number Then biggest_number = n

While (n Mod 2) = 0
n /= 2
count += 1
Wend
runde += 1
If n < 8 Then Return count

If count > 1000000 Then ' Infinite Loop
Return -2
End If
Loop
End Function

Sub Main()
Dim As UInt64 n
Dim As Integer count

For n = 5 To 372
count = sequence(n)
If count = -1 Then
Print n; " Overflow"
ElseIf count = -2 Then
Print n; " Infinite Loop"
Else
Print n; " "; runde; " "; count; " "; biggest_number
End If
Next
End Sub

Schaut für mich übersichtlicher aus als das C-Programm. Aber C war noch nie wirklich für übersichtlichen Quellcode bekannt, lach.

Für diejenigen, die sich in FreeBasic nicht so gut auskennen: count += 1 ist eine Kurzform für count = count + 1. Entsprechend bedeutet n /= 2 einfach n = n / 2

Ein entsprechendes Turbo-Pascal-Programm sieht ziemlich ähnlich aus, ich habe es aber nicht getestet.

program CollatzSequence;

uses
sysutils;

const
max64_3: UInt64 = 18446744073709551615 div 3 - 1;
max64_5: UInt64 = 18446744073709551615 div 5 - 1;

var
biggest_number: UInt64;
runde: Integer;

function Sequence(n: UInt64): Integer;
var
count: Integer;
begin
count := 0;
runde := 1;
biggest_number := 0;

repeat
if n > max64_3 then
Exit(-1); // Check auf Overflow (nach der Multiplikation)

n := 3 * n + 1;
Inc(count);
if n > biggest_number then
biggest_number := n;

while (n mod 2) = 0 do
begin
n := n div 2;
Inc(count);
end;
if n < 8 then
Exit(count);

if n > max64_5 then
Exit(-1); // Check auf Overflow (nach der Multiplikation)

n := 5 * n + 1;
Inc(count);
if n > biggest_number then
biggest_number := n;

while (n mod 2) = 0 do
begin
n := n div 2;
Inc(count);
end;
Inc(runde);
if n < 8 then
Exit(count);

if count > 1000000 then
Exit(-2); // Infinite Loop
until False;
end;

var
n: UInt64;
count: Integer;

begin
for n := 5 to 372 do
begin
count := Sequence(n);
if count = -1 then
WriteLn(n, ' Overflow')
else if count = -2 then
WriteLn(n, ' Infinite Loop')
else
WriteLn(n, ' ', runde, ' ', count, ' ', biggest_number);
end;
end.

__________________
Mein Profil beim ICCF (International Correspondence Chess Federation)
https://www.iccf.com/player?id=89948&tab=3

Stimmt, bei den Programmiersprachen gibt es ganz unterschiedliche Präferenzen.
Der komplette C Code, erzeugt denselben Output, mal etwas schwerer lesbarer

#include"stdio.h"
#include"stdint.h"
#define z c++;if(n>b)b=n;while((n%2)==0){n/=2;c++;}
uint64_t u=18446744073709551615/3-1,v=18446744073709551615/5-1,b;int r;int s(uint64_t n){int c=0;r=1;b=0;
for(;; ){if(n>u)return-1;n=3*n+1;z if(n<8)return c;if(n>v)return-1; n=5*n+1;z r++;if(n<8)return c;if(c>1000000)return-2;}}
int main(){for(uint64_t n=5;n<373;n++){int c=s(n);if(c==-1)printf("%4I64u Overflow\n",n);
if(c==-2)printf("%4I64u Infinite Loop\n",n);if(c>=0)printf("%4I64u %4d %5d %16I64u\n",n,r,c,b);}}

Liebe Leute,

Ihr kommt etwas vom Thema ab. Trotzdem möchte ich
auch eine Erinnerung beisteuern. Um 1990 herum war
ich in Kontakt mit Wolfgang Delmare, der damals auch
Schachprogrammierer war.

Im Gespräch erzählte er über ein abgebrochenes
Gespräch mit einem anderen Programmierer (Helmut
Horacek?). Auch wenn es vielleicht nicht Helmut war,
kürze ich ihn mal mit HH ab und Wolfgang mit WD.

HH: Wie lang ist denn Dein Schachprogramm?
WD: Meinst Du in Zeilen oder in Kommandos?
HH: Genau.
WD: Das ist aber nicht das Gleiche. Meinst Du Zeilen
oder meinst Du Kommandos?
HH: Aber man schreibt doch in jede Zeile nur ein Kommando.
WD: Ich nicht. Meist kriege ich zwei bis drei Kommandos in eine Zeile.

Wolfgang zu mir: An der Stelle brach HH das Gespräch ohne
weitere Erklärung ab.

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

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.

__________________
Fließendes Wasser kennt keinen Kampf (Takagawa Kaku; alter Go-Meister)