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, 77x 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)

Das Basic-Programm ebenso wie das TurboPascal Programm sind - immer vorausgesetzt ich habe keinen Fehler gemacht - eins zu eins Umsetzungen des vorher geposteten C-Programms. Dementsprechend müssten sie auch dieselben Ergebnisse liefern.

Mein Post sollte nur helfen, den Code besser zu verstehen, da FreeBasic und Pascal als imperative Sprachen teilweise besser zu verstehen sind, wenn man in der C-Programmierung nicht so drin ist. Geht mir jedenfalls so.

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

Hallo Hartmut,

wir schreiben aneinander vorbei.
Es ist mir egal, ob 15n+1/n+1 mit dieser oder jener Programmiersprache
attackiert wird. Ich traue Euch beiden zu, richtig zu programmieren.

Der Punkt ist: Ich habe zuletzt 1992 programmiert (Zillions ausgenommen,
aber das ist ja etwas anderes) und kann nicht mehr programmieren. Wobei
ich beim Betrachten von Programmcode schon noch die eine oder andere
Ungereimtheit erkenne.

Zur Erinnnerung: 15n+1/n+1 hat die drei Fixpunkte
1
3
5
(und vielleicht weitere).

Viele Grüße, Ingo.

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

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

Viele Grüße, Thomas

Angehängte Dateien

Collatz151.txt (41,8 KB, 76x aufgerufen)

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)

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