Posts mit dem Label collatz problem werden angezeigt. Alle Posts anzeigen
Posts mit dem Label collatz problem 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 :)

Samstag, 14. Mai 2011

Collatz Folge - Fortsetzung #2

(15.05. Inzwischen nochmal nachgelegt zu Version 0.5)

Collatz Tool

Soeben Collatz Tool v0.4 "geupdatet". Bilder der Collatz Folgen sind nun online als Webalbum unter picasa zu finden.

Darunter sind Screenshots aus dem aktuellen OpenGL Projekt zu sehen, an dem ich arbeite. Für den ersten Härtetest dienten quasi die Daten der Collatz Folgen. Bei einer Million Daten merkte man dann doch schon die Belastung bei der GPU Übertragung (DisplayListenKompilierung), jedoch liefen die Kernfunktionen flüssig (auf einen dual-core mit NVidia 9800GT 512MB).

Die Daten werden dabei blockweise aufgereiht, sodass die ersten bspw. 512 Werte der Collatz Folge (bei steigender Startnummer nach Terminierung) neben den nächsten 512 Werten anliegen. So ergeben sich 512 Stränge mit je 512 Werten. Man sieht wie die Kurven steigen und dann irgendwann wieder bei 1 terminieren. Dann fängt die nächste Folge mit dem nächsten Startwert an.


Screenshot aus dem View3d Projekt (128x128 Daten)

Mittwoch, 11. Mai 2011

Collatz Folge - Fortsetzung

Habe das Programm zur Collatz Folge weiterentwickelt.
Siehe Collatz Tool.
Einige Resultate in Kurzfassung:
(Die folgenden Bilder und weitere finden sich auch auf picasa)


Collatz: 23 bis 5022 - Verlauf der Zahlen


Collatz: 23 bis 5022
oberes TeilDiagramm: Anzahl der Rechenschritte bis Terminierung bei 1
Das Wachstum der Rechenschrittanzahl scheint immer schwächer anzuwachsen (ähnlich der log-Funktion, siehe nächstes Bild). Und wieder sind periodische Muster zu erkennen.
unteres TeilDiagramm: größte Zahl, die in der Folge erreicht wurde.


Collatz: 23 bis 5022 (wie eben, nur logarithmische Skalierung)


Collatz: 23 bis 5022 (wie oben, nur logarithmische Skalierung)


Collatz: 280 bis 289 je Zahl ein Farbwert der Regenbogenpalette

Würde gerne ein bissl mehr dazu raussuchen, wäre bestimmt auch ein nettes Seminarthema, aber mehr Zeit werde ich dem hier nicht widmen. Ich mag jedoch das Problem: eine einfache Fragestellung, eine einfache Formel, keine einfache Lösung. Typisch Zahlentheorie. Das erste "zahlentheoretische" Problem, mit dem ich mich damals vor etwa 8 Jahren befasst habe - in PHP - hatte mit gd (graf. Lib, kam ca. 2003 mit PHP 4.3 raus) rumgespielt. Das war ineffizient, aber geil. ;)

(Bilder wurden mit R erstellt)

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