Collatz-Funktion

Die Collatz-Funktion

Letztmalig dran rumgefummelt: 17.05.08 22:01:34

Amerikanischer Mathematiker, der in den 50er Jahren die Programmiersprache LISP implementiert hat. Das Problem wurde 1937 von Lothar Collatz veröffentlicht. Seitdem haben sich viele Mathematiker mit dem Problem beschäftigt. Mehrfach wurden Preise für eine Lösung ausgelobt. 1970 bot H. S. M. Coxeter 50$ für einen Beweis der Vermutung und 100$ für ein Gegenbeispiel. Bryan Thwaites hat 1996 1000 englische Pfund versprochen. Paul Erdős sagte über das Collatz-Problem: „Mathematics is not yet ready for such problems.“ (Die Mathematik ist noch nicht bereit für solche Probleme.) Er bot 500 Pfund für eine Lösung.

1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Literatur
7. Linkliste zum Thema

Klassische algorithmisch lösbare Probleme

Logo für die Collatz-Funktion

Informatik-Profi-Wissen

Quellen:

Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ???

Technische und Theoretische Informatik Seite ???

1. Problembeschreibung

Das Collatz-Problem gehört zu den ungelösten Problemen der Mathematik. Es wird gelegentlich auch 3n+1-Problem, Syracuse-Vermutung (...), Kakutanis Problem (nach Shizuo Kakutani), Hasse-Algorithmus (nach Helmut Hasse), Thwaites-Vermutung (nach Bryan Thwaites) oder Ulams Problem (nach Stanislaw Marcin Ulam) genannt. Allgemein gesagt geht es darum, ob ein bestimmter rekursiver Algorithmus bei jeder Ausgangszahl gleich endet oder nicht.

Man beginne mit einer beliebigen natürlichen Zahl a₀ und bilde damit die rekursive Zahlenfolge

Die Collatz-Funktion

Die Folge endet, wenn sie den Wert 1 erreicht. Alternativ reicht es auch, dass die Folge einen Wert der Form 2ⁿ erreicht, da alle Zahlen der Form 2ⁿ bei 1 enden.

Vermutung:
Für jede natürliche Zahl a0 erreicht die Folge nach endlich vielen Schritten den Wert 1 und gerät dann in einen Zyklus: 1, 4, 2, 1…

Diese Vermutung konnte bisher weder bewiesen noch widerlegt werden.

Beispiele:
Sei a₀ = 5. Dann erhält man die Folge 5, 16, 8, 4, 2, 1. Für a₀ = 7 lautet die Folge 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Da auf jede ungerade Zahl n = 2k + 1 eine gerade Zahl folgt (3n + 1 = 3 * (2k + 1) + 1 = 6k + 4 ist gerade) betrachtet man oft auch das äquivalente Problem

Prinzipiell kann die Zahlenfolge eine der drei folgenden Eigenschaften haben:

die Folge endet bei 1.

die Folge wächst über alle Grenzen.

die Folge gerät in einen Zyklus.

Computer haben alle Zahlen bis 3 * 2⁵³ (Stand 1999) durchprobiert; immer endet die Zahlenfolge mit 1, bestätigt also die Vermutung.

Falls die Folge in einen Zyklus geraten könnte, müsste dieser aus mindestens 275.000 Zahlen bestehen, wie J. C. Lagarias 1985 zeigte.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

Der Lösungsalgorithmus für die McCarthy-Funktion

effiziente Lösung nur als rekursiver Algorithmus
gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf

3. Lösungsalgotihmus

Wenn es mindestens einen Lösungsansatz gibt, dann versuche, aus den gegebenen Wortpaaren identische Sätze auf beiden Seiten der Gleichung zu bilden. Wiederhole dies solange, bis keine weitere Möglichkeit mehr existiert.

Collatz für a₀=15

f(15) =15 · 3 + 1 = f(f(46))

f(46) = 46 : 2 = f(f(23))

f(23) = 23 · 3 + 1 = f(f(70))

f(70) = 70 : 2 = f(f(35))

f(45)=45+11=f(f(56))

f(56)=56+11=f(f(67))

f(67)=67+11=f(f(78))

f(78)=78+11=f(f(89))

f(89)=89+11=f(f(100))

f(100)=100+11=f(f(111))

f(111)=111-10=101

f(101)=101-10=91

McCarthy für x=5

f(5)=5+11=f(f(16))

f(16)=16+11=f(f(27))

f(27)=27+11=f(f(38))

f(38)=38+11=f(f(49))

f(49)=49+11=f(f(60))

f(60)=60+11=f(f(71))

f(71)=71+11=f(f(82))

f(82)=80+11=f(f(93))

f(93)=93+11=f(f(104))

f(104)=104-10=94

f(94)=94+11=f(f(105))

f(105)=105-10=95

f(95)=95+11=f(f(106))

f(106)=106-10=96

f(96)=96+11=f(f(107))

f(107)=107-10=97

f(97)=97+11=f(f(108))

f(108)=108-10=98

f(98)=98+11=f(f(109))

f(109)=109-10=99

f(99)=95+11=f(f(110))

f(110)=110-10=100

f(100)=100+11=f(f(111))

f(111)=111-10=101

f(101)=101-10=91

4. Programmvorschläge

Was auch immer ich tue, muss ich rekursiv lösen und die Mächtigkeit schon für kleine Argumente ist durch die Anzahl der Zwischenwerte enorm. Auch wird eine extreme Rekursionstiefe erreicht und somit der Speicher maximal ausgelastet. Effizient ist die Abarbeitung aber trotzdem noch, da keine weitere Lösungsmöglichkeit existiert.

Die nachfolgend beschriebene Lösung wurde mit Turbo-PASCAL 7.0 erstellt

FUNCTION mc_carthy__kleiner_100 (up_zahl:BYTE):BYTE;

BEGIN{begin mc_carthy__kleiner_100}
IF up_zahl<=100
THEN
BEGIN{begin of then}
mc_carthy__kleiner_100:=mc_carthy__kleiner_100(mc_carthy__kleiner_100(up_zahl+11));
END{end of then}
ELSE
BEGIN{begin of else}
mc_carthy__kleiner_100:=up_zahl-10;
END;{end of else}
END;{end of mc_carthy__kleiner_100}

FUNCTION mc_carthy__groesser_100 (up_zahl:BYTE):BYTE;

BEGIN{begin mc_carthy__groesser_100}
mc_carthy__groesser_100:=up_zahl-10;
END;{end of mc_carthy__groesser_100}

5. Zusammenfassung

Hier greifen wir unter anderem die Argumente für einen Algorithmus auf und vergleichen, ob Übereinstimmung in allen Punkten gegeben ist.

Endlichkeit der Beschreibung ist gegeben
Eindeutigkeit ist gegeben - jeder Schritt ist für jede Bedingung eindeutig fest vorgegeben und lässt keine Abweichung zu

Effektivität ist gegeben - jeder Schritt ist ausführbar

Terminierung ist nicht gegeben - der Algorithmus läuft nach erreichen des Zwischenergebnisses 91 ewig und generiert einen Stapelüberlauf

Determiniertheit ist gegeben, der Folgeschritt nach einer Operation ist immer bekannt

6. Weiterführende Literatur

der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwnde keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.

http://www.panix.com/~derwisch/hannes/elug/lisp/scheme.pdf
http://www-is.informatik.uni-oldenburg.de/~dibo/teaching/java9900/vorlesungen/vorlesung7/tsld031.htm
http://www.lexikon-definition.de/LISP.html

zur Hauptseite

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)

	Das Collatz-Problem gehört zu den ungelösten Problemen der Mathematik. Es wird gelegentlich auch 3n+1-Problem, Syracuse-Vermutung (...), Kakutanis Problem (nach Shizuo Kakutani), Hasse-Algorithmus (nach Helmut Hasse), Thwaites-Vermutung (nach Bryan Thwaites) oder Ulams Problem (nach Stanislaw Marcin Ulam) genannt. Allgemein gesagt geht es darum, ob ein bestimmter rekursiver Algorithmus bei jeder Ausgangszahl gleich endet oder nicht.
	Man beginne mit einer beliebigen natürlichen Zahl a₀ und bilde damit die rekursive Zahlenfolge *Die Collatz-Funktion*
	Die Folge endet, wenn sie den Wert 1 erreicht. Alternativ reicht es auch, dass die Folge einen Wert der Form 2ⁿ erreicht, da alle Zahlen der Form 2ⁿ bei 1 enden.
	Vermutung: Für jede natürliche Zahl a0 erreicht die Folge nach endlich vielen Schritten den Wert 1 und gerät dann in einen Zyklus: 1, 4, 2, 1… Diese Vermutung konnte bisher weder bewiesen noch widerlegt werden.
	Beispiele: Sei a₀ = 5. Dann erhält man die Folge 5, 16, 8, 4, 2, 1. Für a₀ = 7 lautet die Folge 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Da auf jede ungerade Zahl n = 2k + 1 eine gerade Zahl folgt (3n + 1 = 3 * (2k + 1) + 1 = 6k + 4 ist gerade) betrachtet man oft auch das äquivalente Problem
	Prinzipiell kann die Zahlenfolge eine der drei folgenden Eigenschaften haben: die Folge endet bei 1. die Folge wächst über alle Grenzen. die Folge gerät in einen Zyklus. Computer haben alle Zahlen bis 3 * 2⁵³ (Stand 1999) durchprobiert; immer endet die Zahlenfolge mit 1, bestätigt also die Vermutung. Falls die Folge in einen Zyklus geraten könnte, müsste dieser aus mindestens 275.000 Zahlen bestehen, wie J. C. Lagarias 1985 zeigte.

	Der Lösungsalgorithmus für die McCarthy-Funktion
	effiziente Lösung nur als rekursiver Algorithmus
	gegenseitige Rekursion - die Funktionen für größer 100 und kleiner 100 für die Zwischenwerte rufen sich gegenseitig auf

	Was auch immer ich tue, muss ich rekursiv lösen und die Mächtigkeit schon für kleine Argumente ist durch die Anzahl der Zwischenwerte enorm. Auch wird eine extreme Rekursionstiefe erreicht und somit der Speicher maximal ausgelastet. Effizient ist die Abarbeitung aber trotzdem noch, da keine weitere Lösungsmöglichkeit existiert.
	Die nachfolgend beschriebene Lösung wurde mit Turbo-PASCAL 7.0 erstellt FUNCTION mc_carthy__kleiner_100 (up_zahl:BYTE):BYTE; BEGIN{begin mc_carthy__kleiner_100} IF up_zahl<=100 THEN BEGIN{begin of then} mc_carthy__kleiner_100:=mc_carthy__kleiner_100(mc_carthy__kleiner_100(up_zahl+11)); END{end of then} ELSE BEGIN{begin of else} mc_carthy__kleiner_100:=up_zahl-10; END;{end of else} END;{end of mc_carthy__kleiner_100} FUNCTION mc_carthy__groesser_100 (up_zahl:BYTE):BYTE; BEGIN{begin mc_carthy__groesser_100} mc_carthy__groesser_100:=up_zahl-10; END;{end of mc_carthy__groesser_100}

	Hier greifen wir unter anderem die Argumente für einen Algorithmus auf und vergleichen, ob Übereinstimmung in allen Punkten gegeben ist.
	Endlichkeit der Beschreibung ist gegeben
	Eindeutigkeit ist gegeben - jeder Schritt ist für jede Bedingung eindeutig fest vorgegeben und lässt keine Abweichung zu
	Effektivität ist gegeben - jeder Schritt ist ausführbar
	Terminierung ist nicht gegeben - der Algorithmus läuft nach erreichen des Zwischenergebnisses 91 ewig und generiert einen Stapelüberlauf
	Determiniertheit ist gegeben, der Folgeschritt nach einer Operation ist immer bekannt


	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

	Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwnde keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.
	http://www.panix.com/~derwisch/hannes/elug/lisp/scheme.pdf
	http://www-is.informatik.uni-oldenburg.de/~dibo/teaching/java9900/vorlesungen/vorlesung7/tsld031.htm
	http://www.lexikon-definition.de/LISP.html