Quelltext der Seite Collatz Conjecture

{{#projektinfo:50}}
==Collatzsche Vermutung==
===Mathematischer Hintergrund===
Die 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

====In Worte gefasst====

# Man nehme eine beliebige natürliche (d.h. ganze, positive) Zahl A.
#:
# Wenn es sich um eine gerade Zahl handelt, teile man sie so lange durch zwei, bis man bei einer ungeraden Zahl ankommt.
#:
#Diese ungerade Zahl multipliziere man mit drei und addiere eins hinzu. Das Ergebnis ist wieder eine gerade Zahl.
#:
#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.

====Beispiele====

: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

Ein Rechner, der am Collatz-Conjecture-Projekt teilnimmt, macht also nichts anderes, als die Gültigkeit der Collatzschen Vermutung bei sehr großen Zahlen nachzurechnen, indem er, von großen Zahlen ausgehend, die Collatzsche Reihe durchrechnet.

===Kritische Betrachtung===
Strukturelle 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:

:a: 1, 4, 7, 10, 13, 16, 19, 22, 25, ...

Wenn die Reihe fortgeführt wird, ist ersichtlich, dass nur die Zweierpotenzen mit geradem Exponenten (hoch 2, hoch 4, hoch 6) in der Reihe auftauchen. Die Collatzsche Vermutung gilt also, wenn sichergestellt wird, dass für jede beliebige Anfangszahl A irgendwann eine Zweierpotenz mit geradem Exponenten erreicht wird.

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 verbleibender 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.

Aus diesen Überlegungen erscheint die Wahrscheinlichkeit groß, dass alleine „durch bloßen Zufall“ irgendwann eine der besagten Zahlen getroffen und Collatz somit bestätigt wird, ganz gleich, wie die Anfangszahl lautet. Gleichzeitig ist damit die Chance eher als gering zu bewerten, dass das BOINC-Projekt ''Collatz Conjecture'' tatsächlich auf eine Anfangszahl stößt, für die die Collatz-Reihe entweder über alle Grenzen wächst, oder aber nicht in den trivialen Zyklus 4-2-1-4-2-1-... mündet, was die Collatzsche Vermutung widerlegen könnte.

Collatz Conjecture hilft also, die geäußerten Überlegungen zur Collatz-Reihe zu bestätigen und hat die geringe Chance, den konkreten Gegenbeweis in Form einer Zahl zu bringen.

== Berechnung mit ATI-Grafikkarten ==
Nach einigen Anfangsschwierigkeiten bei der ATI-Unterstützung scheint BOINC 6.10.16 in Verbindung mit dem Catalyst-Treiber 9.10 stabil zu laufen.

=== Voraussetzungen ===
Grafikkarten 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:
*http://developer.amd.com/gpu/ATIStreamSDK/ATIStreamSDKv1.4Beta/pages/ATIStreamSystemRequirements.aspx

Passende Treiber sind bei AMD / ATI zu finden unter:
*http://support.amd.com/de/gpudownload/Pages/index.aspx

=== BOINC ===
Empfohlen wird BOINC ab Version 6.10.10. 

=== Anwendungen ===
Es 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 [http://boinc.thesonntags.com/collatz/power_apps.php].

== Berechnung mit NVIDIA-Grafikkarte ==
=== Voraussetzungen ===
CUDA-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

=== BOINC ===
BOINC ab Version 6.4.7 wird benötigt.

=== Anwendungen ===
Es wird zudem eine optimierte Anwendung benötigt. Diese wird i. d. R. automatisch vom Manager heruntergeladen, ansonsten ist sie erhältlich auf [http://boinc.thesonntags.com/collatz/power_apps.php].
<br><br>
Für das Projekt gibt es mehrere Anwendungen, die sich von wenigen Minuten (mini-collatz auf) bis hin zu mehreren Stunden oder Tagen vergrößern (large-collatz). Zudem kann man bei NVIDIA zwischen CUDA und OpenCL differieren, je nachdem, mit welcher Software die Berechnung auf der Grafikkarte schneller vonstatten geht.

Es besteht bei der Berechnungsdauer eine große Schwankungsbreite. Anfolgend einige Beispiele (ohne Nutzung weiterer Optimierungen, wie [[app_config.xml]]):
* micro_collatz

* mini_collatz 
** NVIDIA 460SE (~25min - opencl | ~13min - cuda)
** NVIDIA 660TI (~2-3Minuten), 680 (~2-3Minuten)

* solo_colaltz
** NVIDIA 460SE (~3,5h - cuda) 
** NVIDIA 660TI (~36min - cuda55(Windows 64 bit) | ~32min - cuda40(Linux 64 bit))

* large_collatz
** NVIDIA 460SE (~2,45d - cuda), 
** NVIDIA 660TI (~9,42h - cuda55(Windows 64 bit))

==Badges==
Die Badges h&auml;ngen von der Gesamtzahl der errechneten Credits ab. Das Symbol stellt eine [http://de.wikipedia.org/wiki/Beno%C3%AEt_Mandelbrot Mandelbrot-Fraktur] dar. <br />
<br />
{| border="1" cellpadding="5" style="margin:1px 1px 1px 0; border:1px #417dbe solid; border-collapse:collapse; empty-cells:show; text-align:center;"
! style="background-color:#234471; color:#ffffff;" | '''Bronze'''<br><sup>100 Tausend Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Silber'''<br><sup>1 Million Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Gold'''<br><sup>5 Millionen Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Amethyst (violett)'''<br><sup>20 Millionen Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Rubin (rot)'''<br><sup>100 Millionen Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Saphir (blau)'''<br><sup>500 Millionen Credits</sup>
! style="background-color:#234471; color:#ffffff;" | '''Smaragd (grün)'''<br><sup>2 Milliarden Credits</sup>
|-
|[[Bild:badge_100K.png]]
|[[Bild:badge_1M.png]]
|[[Bild:badge_5M.png]]
|[[Bild:badge_20M.png]]
|[[Bild:badge_100M.png]]
|[[Bild:badge_500M.png]]
|[[Bild:badge_2G.png]]
|}<br />

==Weblinks==
*[http://boinc.thesonntags.com/collatz/apps.php Anwendungen]
*[http://boinc.thesonntags.com/collatz/rss_main.php RSS-Feed]