HerunterladenAdministrationWerkzeugePersönliche Werkzeuge |
AnsichtenCollatz ConjectureAus SETI.Germany Wiki
Das Collatz-Problem (auch: (3n+1)-Vermutung) beschäftigt sich mit der Vermutung, dass die Collatz-Folge für jede natürliche Zahl früher oder später die „1“ erreicht und in einem trivialen Muster (4-2-1-4-2-1...) weiterläuft. Lothar Collatz entdeckte diesen Zusammenhang im Jahr 1937, sprach aber 1952 erstmals mit einem Kollegen darüber, welcher die bis heute nicht widerlegte Vermutung verbreitete. Das Boinc-Projekt Collatz Conjecture beschäftigt sich mit der Suche nach einer Zahl, für die die Vermutung nicht gilt, also widerlegt werden kann.
[bearbeiten] Collatzsche Vermutung[bearbeiten] Mathematischer HintergrundDie Collatzsche Reihe hat die folgende rekursive Definition für eine beliebige Anfangszahl A aus der Menge der natürlichen Zahlen: C[n] = A C[n+1] = { A/2 für A mod(2) = 0 { 3A+1 für A mod(2) = 1
1) Man nehme eine beliebige natürliche (d.h. ganze, positive) Zahl A 2) Wenn es sich um eine gerade Zahl handelt, teile man sie so lange durch zwei, bis man bei einer ungeraden Zahl ankommt 3) Diese ungerade Zahl multipliziere man mit drei und addiere eins hinzu. Das Ergebnis ist wieder eine gerade Zahl 4) Die Schritte 2. und 3. werden solange wiederholt, bis das Ergebnis 1 lautet. Die Collatzsche Vermutung besagt nun, dass, ganz gleich mit welcher Zahl begonnen wird, die Reihe stets früher oder später bei "1" landet'
C(A=3) : 3, 10, 5, 16, 8, 4, 2, 1 C(A=4) : 4, 2, 1 C(A=5) : 5, 16, 8, 4, 2, 1 C(A=6) : 3, 10, 5, 16, 8, 4, 2, 1 C(A=7) : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
[bearbeiten] Kritische BetrachtungStrukturelle Untersuchungen von Collatz-Reihen bzw. des Collatz-Problems liefern starke Hinweise dafür, dass die Collatzsche Vermutung mit hoher Wahrscheinlichkeit richtig zu sein scheint. Betrachten wir eine beliebige Zahl A aus der Menge der natürlichen Zahlen. Um die 1 zu erreichen und damit in die trivialen Zyklus 4-2-1-4-2-1-... überzugehen, muss die Collatz-Reihe von A auf eine Potenz von zwei treffen. Wenn es sich bei A nicht bereits um eine Zweierpotenz handelt, ist dies nur bei den Zweierpotenzen aus der Reihe a = 3n+1 möglich, da die wiederholte Anwendung dieser Operation stets wieder zu einer Zahl aus eben dieser Reihe führt:
Weiterhin kann beobachtet werden, dass viele Collatz-Reihen das Muster 5-16-8-4-2-1-... aufweisen. Wenn die Operation "3n+1" also auch zu einem zehnfachen einer (beliebigen) Zweierpotenz führt, wird durch mehrfaches Halbieren zwingend die 5 als letzter verbliebender Primfaktor getroffen und die Collatz-Vermutung erfüllt. Damit ist die Zahl derjenigen Werte, die, wenn sie in einer Collatz-Reihe auftauchen, die Collatzsche Vermutung definitionsgemäß bestätigen werden, überaus groß und wächst mit jeder Zahl an, die irgendwo in einer Reihe einmal auftaucht.
[bearbeiten] Berechnung mit ATI-GrafikkartenNach einigen Anfangsschwierigkeiten bei der ATI-Unterstützung scheint BOINC 6.10.16 in Verbindung mit dem Catalyst-Treiber 9.10 stabil zu laufen. [bearbeiten] VoraussetzungenGrafikkarten mit einer CAL 1.3 kompatiblen GPU (ab Radeon HD2000 Serie) und Catalysttreiber ab Version 8.12. Eine Liste von unterstützten Grafikkarten ist bei AMD / ATI zu finden unter: Passende Treiber sind bei AMD / ATI zu finden unter: [bearbeiten] BOINCEmpfohlen wird BOINC ab Version 6.10.10. [bearbeiten] AnwendungenEs wird zudem eine optimierte Anwendung benötigt. Diese wird bei Verwendung von BOINC ab Version 6.10.10 automatisch heruntergeladen. Ansonsten ist sie erhältlich auf [1]. [bearbeiten] Berechnung mit NVIDIA-Grafikkarte[bearbeiten] VoraussetzungenCUDA-fähige Grafikkarten ab Treiberversion 190.38. Eine Auflistung, welche Grafikkarten CUDA-fähig sind, ist unter http://www.nvidia.de/object/cuda_learn_products_de.html zu finden. Entsprechende Treiber sind bei NVIDIA zu finden: http://www.nvidia.de/Download/index.aspx?lang=de [bearbeiten] BOINCBOINC ab Version 6.4.7 wird benötigt. [bearbeiten] AnwendungenEs wird zudem eine optimierte Anwendung benötigt. Diese wird i.d.R. automatisch vom Manager heruntergeladen, ansonsten ist sie erhältlich auf [2]. [bearbeiten] Links |
|||||||||||||||||||||||||||||||||||||||||||||||
Alle Zeitangaben in WEZ +2. Es ist jetzt 16:02 Uhr.