Posts mit dem Label collatz vermutung werden angezeigt. Alle Posts anzeigen
Posts mit dem Label collatz vermutung werden angezeigt. Alle Posts anzeigen

Montag, 6. Juni 2011

Collatz Vermutung weiterhin nur eine Vermutung

Es ist kaum paar Wochen her, als ich hier ein paar Bilderchen und ein Programm zur Collatzfolge (und auch collatzähnlichen Folgen) veröffentlicht habe, schon erscheint ein anfänglich interessanter Beweisvorschlag zur Collatzvermutung. Die Vorveröffentlichung von Gerhard Opfer (Professor Hamburg im Ruhestand, war Schüler von Collatz) umfasst etwa nur 14 Seiten zuzüglich Anhang:

hbam2011-09.pdf

Er verwendet fast durchgängig dabei die älteren Arbeiten von Lothar Berg und Günter Meinardus. Eine davon ist:
The 3n+1 Collatz Problem and Functional Equations (1995)

Der Beweisvorschlag von Opfer ist leider falsch. Wenn ich das richtig verstanden habe, stellt er eine neue unbewiesene Behauptung auf, die ähnlich schwierig zu beweisen sein dürfte wie das Collatzproblem selbst. Er scheint sich damit auf hohem Niveau im Kreis gedreht zu haben:
http://mathlesstraveled.com/2011/06/04/the-collatz-conjecture-is-safe-for-now/

Ich kenn mich da zu wenig aus. So wie sich das alles anhört, wären 14 Seiten und etwas Modifizieren von alten Arbeiten ein sehr sonderbares Ergebnis gewesen für dies alte, recht hartnäckige Problem. Die Pdf umfasst zwar 32 Seiten, die rund 20 Seiten Tabellen hab ich aber mal abgezogen, weil das für mich nach Anhang aussieht und nicht zum Beweis gehört.

Vielleicht erhalten wir auch die Aussage, dass das CollatzProblem nicht (formal) beweisbar ist. Ein Ansatz dazu kursiert bereits:
http://arxiv.org/abs/math/0312309
Scheint jedoch ebenfalls fehlerhaft.

Das ist der "neue" Albtraum nach Fermats Theorem (93 von Wiles bewiesen, 95 veröffentlicht). Ok, wir hätten noch die NP!=P Vermutung, was aber nicht so leicht zu erfassen ist wie das Collatz Problem und der Komplexitätstheorie zugehörig ist. Zahlentheoretische Probleme wie Fermats Theorem oder eben das Collatzproblem sind viel hübscher und garantieren einem 10, 20 Jahre Aufenthalt aufm Dachboden mit anschließender Sicherheitsverwahrung in der Klappse oder mit anschließendem Ruhm (letzteres trifft jedoch mit Wahrscheinlichkeit Null ein).
Nun gibt es auch noch die Riemannsche Vermutung, auch Zahlentheorie, involviert aber auch komplexe Analysis, die auch sehr schön ist, aber eben nicht mehr so leicht erfassbar. Es gibt natürlich noch eine Menge andere ungelöste Probleme, aber für heute reichts :)

Donnerstag, 28. April 2011

Collatz Folge mit Big Integers

Collatz Tool (Konsole, Windows / Linux):
- berechnet Collatz Folgen und collatzähnliche Folgen
- Ausgabe in CSV Format in Datei
- zwei Ausgabevarianten (vollständig und aggregiert)
- Optionen und Parameter über Konsoleneingabe konfigurierbar



Update 15.05.11: Version 0.5.
Update 14.05.11: Version 0.4.
Update 08.05.11: Windows Version hinzugefügt + Version 0.3.


Sourceforge Project (Download + SVN):
https://sourceforge.net/projects/collatztool/

Download:
Source:

collatz_0.5_src.zip

Windows 32bit:
collatz_0.5_win32bin.zip
(Kompiliert mit gcc 4.5.0, mingw32)

R Skripte:
collatz_r_scripts.zip


Aus Collatz Problem Bilder

Bilder der visualisierten Daten auf picasa



Ein Artikel auf matheplanet erinnerte mich wieder an ein altes Problem: die Collatz-Folge und die bisher noch ungelöste Frage, ob sie für jede Zahl irgendwann wieder bei Eins terminiert. Siehe auch im Wiki-Artikel zum Collatz-Problem.

Da ich ohnehin mal nach einer Möglichkeit gesucht hatte, mit beliebigen natürlichen Zahlen zu rechnen, fand ich nun etwas Zeit, mal das ganze anhand des Collatz-Problems umzusetzen. Denkbar einfach eigentlich, wenn man folgende Bibliothek verwendet:

http://sourceforge.net/projects/cpp-bigint/
(GPL)

Man kann das Collatz-Problem ein wenig modifizieren und erneut die Frage stellen, ob diese für eine beliebige Zahl terminiert oder in einem Zyklus landet. Statt mit dem Faktor 3 kann man auch 5 oder 7 oder ... nehmen.
Die Zahlen werden jedoch schnell recht groß, sodass die Integer Datentypen hinfällig sind. Zum Experimentieren hab ich also mal ein Mini C++ Programm geschrieben, das obige Bibliothek verwendet.


Beispiel mit Faktor 7 und Startzahl 7. Die Anzahl der Stellen wächst nahezu linear (entspricht logarithmischer Skalierung der Zahlen).

Bild 1 in Gnuplot
Bild 2 in R spaßeshalber mit Regressionsgeraden

--

Inzwischen hab ich das Programm noch erweitert, sodass per Konsole die Optionen eingegeben werden können.

collatz tool (2011/04/28) - License GPL v2
OPTIONS:
-f factor - collatz factor (3)
-s startnumber - number where to start (23)
-m maxloops - maximum of loops (10000)
-o output - output file where all the numbers and digits will be saved ("output.csv")


Eine Ausgabe:
./collatz -f 7 -m 1000 -s 7 -o "myoutput.csv"

Time: 605 ms
Finished!

Startnumber: 7 Factor: 7
Last number:
165059775843459228273519944627021462143091242535195009952629545650013760819089 (Length: 78)

1000 iterations done (of max. 1000).

Output successfully written to myoutput.csv


Der QuellCode kann im Folgenden heruntergeladen werden. Die BigInteger Bibliothek ist mit enthalten. Die GPL Lizenz ist dabei zu berücksichtigen.

Anbei die einfache sowie erweiterte Version und die gnuplot und R Dateien, wen es interessiert.

Download:
Source:

collatz_0.5_src.zip

Windows 32bit:
collatz_0.5_win32bin.zip
(Kompiliert mit gcc 4.5.0, mingw32)

R Skripte:
collatz_r_scripts.zip

Veraltet:
Windows 32bit:
collatz_0.3_win32bin.zip
collatz_0.3_src_vsproject.zip

Linux Source:
collatz_0.1.tar.bz2
collatz_0.3.tar.gz
gnuplot_r.zip

Weitere Artikel zu Collatz:

http://11235813tdd.blogspot.com/2011/05/collatz-folge-fortsetzung.html


http://11235813tdd.blogspot.com/2011/05/collatz-folge-fortsetzung-2.html

http://11235813tdd.blogspot.com/2011/06/collatz-vermutung-weiterhin-nur-eine.html