WikiDer > Verdacht auf Collatz

Es Vermutung von Collatz ist eine Vermutung im Zahlentheorie das sagt das gewisse Wiederholung endet in allen Fällen mit der Zahl 1, eine beliebige Zahl ${displaystyle n}$ wird als Anfangswert gewählt.

Wiederholung

Such dir irgendeine aus gerade Zahl${displaystyle n}$ als Anfangswert und berechne eine andere Zahl durch die Zeilen:

• wenn ${displaystyle n}$ ist gerade, dividiere durch 2
• wenn ${displaystyle n}$ ungerade ist, multiplizieren Sie es mit 3 und addieren Sie 1

Die Vermutung ist, dass man bei wiederholter Anwendung dieser Regeln schließlich in endlich vielen Schritten zur Zahl 1 gelangt. Diese Vermutung wurde zuerst formuliert von Lothar Collatz im 1937. Bisher wurde die Vermutung weder bewiesen noch widerlegt.

1984 erwähnte Brian Hayes in der Kolumne Computer-Erholungen im Magazin Wissenschaftlicher Amerikaner die Zahlen in einer solchen Reihe Hagelschlagzahlen, Hagelschlagzahlen.

Mathematische Formulierung

spät ${Anzeigestil n>0}$ eine beliebige ganze Zahl sein. Definiere die Zeile ${Anzeigestil (a_{i})}$ durch

${displaystyle a_{0}=n}$

${displaystyle a_{i 1}={ egin{cases}a_{i}/2&{ ext{if }}a_{i}{ ext{ ist gerade}}/3a_{i} 1&{ ext{if }}a_{ i}{ ext{ ungerade ist}}end{cases}}}$

Es wird vermutet, dass bei jedem ${displaystyle a_{0}}$ einer ${displaystyle Nin Mathbb {N} }$ ist, was ${displaystyle a_{N}=1}$.

Beispiele

Graph der Schritte ab n=27

nehmen ${Anzeigestil n=12}$; die Reihe ${Anzeigestil a}$ sieht aus wie: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Mit dem Anfangswert ${Anzeigestil n=15}$ eine längere Reihe entsteht: 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Biene ${Anzeigestil n=27}$ es dauert 111 Schritte, bis (über ein Maximum über 9000) der Wert 1 erreicht ist: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242 , 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445 , 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858 , 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244 , 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Die längste Zeile für einen Startwert unter 1000 ist 178 Schritte lang für den Startwert 871.

Die längste Reihe für einen Startwert unter 1 Million ist 524 Schritte lang für den Startwert 837.799.

Die längste Zeile für einen Startwert unter 1 Milliarde ist 986 Schritte lang für den Startwert 670.617.279.

Optimierungen

Die Iterationen können beschleunigt werden durch:

• alle Faktoren 2 im Primzerlegung löschen.

  Immerhin solange ${displaystyle a_{i}}$ hat den Faktor 2, ist eine gerade Zahl und muss durch 2 geteilt werden.

• ungerade ${displaystyle a_{i}}$ multipliziere mit 3/2 und addiere 1/2 dazu.

  Denn eine ungerade Zahl multipliziert mit 3 bleibt ungerade und durch Addition von 1 entsteht eine gerade Zahl, die durch 2 teilbar ist.

• Die Vermutung kann auch optimiert werden. Es muss nur nachgewiesen werden, dass alle ${displaystyle n=a_{0}in mathbb {N} }$ eine Zahl ${displaystyle iin mathbb {N} }$ ist, für die gilt ${displaystyle a_{i}$. Denn wenn es so ist ${displaystyle n}$ so eine nummer ${Anzeigestil i}$ in der Zeile auftritt, dann hat diese Zahl ${Anzeigestil i}$ eine andere nummer ${Anzeigestil j}$ vermeide es, weniger zu sein als ${Anzeigestil j}$, und so weiter, bis 1 ergibt.
• Die letzte Aussage muss wiederum nur für Zahlen bewiesen werden ${displaystyle n=3!!{pmod {4}}}$. Bei Zahlen, die gleich 0 oder 2 modulo 4 sind, ist dies sofort ersichtlich, da sie im ersten Schritt durch 2 geteilt werden ${displaystyle n}$ dass Modulo 4 gleich 1 ist, wird nach dem ersten Schritt ${Anzeigestil 3n 1}$, also modulo 4 gleich 0 und dann durch 4 teilbar, danach nach den nächsten beiden Schritten ${Anzeigestil(3n 1)/4$.
• Durch Berechnung einer höheren Potenz von 2 modulo können mehr Zahlen ausgeschlossen werden. Beispielsweise ${displaystyle n=3!!{pmod {16}}}$. Man bekommt ${displaystyle n=3!!{pmod {16}}, 3n 1=10!!{pmod {16}}, 3/2n 1/2=5!!{pmod {8}}, 9/2n 5/2 =0!!{pmod {8}}, 9/16n 5/16$. Modulo 1024 bleiben nur noch 64 Möglichkeiten (das sind 6,25%). Modul 1024² nur 2 % bleiben.
• Bei der ungeraden Zahl ${Anzeigestil n=2^{p}q-1}$ kann direkt zu ${Displaystil 3^{p}q-1}$. Indem wir die obige Optimierung auf ungerade Zahlen anwenden, erhalten wir: ${displaystyle 2^{p}q-1, 2^{p-1}3q-1, 2^{p-2}3^{2}q-1,ldots ,3^{p}q-1}$.

Hinweise

Es gibt einige Hinweise darauf, dass die Vermutung von Collatz richtig ist.

Seit 2020, für alle untenstehenden Zahlen ${Displaystil 2^{68}}$ überprüft, ob sie die Vermutung erfüllen.^[1] Das Problem bei der Überprüfung besteht darin, dass sie die Vermutung nur widerlegen kann. Wenn die Vermutung wahr ist, kann auf diese Weise kein Beweis dafür gefunden werden.

Außerdem, wenn du zu allen gehst seltsam Wenn man sich Zahlen ansieht, ist jede Zahl im Durchschnitt 3/4 der Zahl davor, und wenn das lange genug wiederholt wird, wird die Zahl immer kleiner.

Erweiterung auf größere Domains

Iterationen über alle ganzen Zahlen

Eine logische Erweiterung bezieht sich auf alle ganzen Zahlen, nicht nur auf die positiven. In diesem Fall sind 5 Zyklen bekannt

Die verallgemeinerte Vermutung von Collatz besagt, dass jede ganze Zahl in einen dieser 5 Zyklen fällt

Besonderheiten

Es gibt Zahlen ${displaystyle n}$ um das zu schaffen ${Anzeigestil p-1}$ Die Zeiten sollten durch 2 geteilt werden und die ${displaystyle p}$- sollte mit 3 multipliziert und um 1 erhöht werden. Diese Zahlen haben die Form ${Displaystil 2^{p-1}}$ mod ${Displaystil 2^{p}}$. Wenn sie durch 2 geteilt werden, werden sie zu ${Displaystil 2^{p-2}}$ mod ${Displaystil 2^{p-1}}$. Wiederholen Sie dies, bis sie ${Displaystil 2^{0}}$ mod ${Displaystil 2^{1}}$ einbiegen in.

Es ist auch möglich, Nummern zu erstellen, die ${Anzeigestil p-1}$ Die Zeiten müssen mit 3 multipliziert und um 1 erhöht werden. Nach jedem Mal muss 3 plus 1 natürlich durch 2 geteilt werden.

• ${Anzeigestil n=2^{p-1}-1}$ mod ${Displaystil 2^{p}}$. Dies ist eine ungerade Zahl.
• Multipliziert mit 3 wird ${Displaystil 2^{p-1}-3}$ mod ${Displaystil 2^{p}}$.
• Plus 1: ${Displaystil 2^{p-1}-2}$ mod ${Displaystil 2^{p}}$.
• Geteilt durch 2: ${Displaystil 2^{p-2}-1}$ oder ${Anzeigestil 2^{p-2}-1 2^{p-1}=3*2^{p-2}-1}$ mod ${Displaystil 2^{p}}$

Dies entspricht ${Displaystil 2^{p-2}-1}$ mod ${Displaystil 2^{p-1}}$Wo zuerst ${displaystyle p}$ stand jetzt ${Anzeigestil p-1}$. Wiederholen Sie dies, bis 0 übrig bleibt. Dann ist ${Displaystil 2^{0}-1}$ mod ${Displaystil 2^{1}}$ und das bedeutet, dass ${displaystyle p}$ sogar.

Mit dem Computer

Beispiel in Programmiersprache PHP:

$n=12;drucken$n;während($n!==1){($n&1)?$n=($n*3)1:$n/=2;drucken' '.$n;}

BOINC

Es gibt auch ein Verteiltes Rechnen Projekt, das versucht, mehr Einblick in die Vermutung zu geben Das nennt man Collatz-Vermutung und läuft unter BOINC.

Externer Link

• Collatz-Vermutung, die Website des Distributed Computing-Projekts