Die Vermutung von Collatz ist eine Vermutung in der Mathematik genannt nach Lothar Collatz, der es zuerst 1937 vorgeschlagen hat. Die Vermutung ist auch bekannt als 3n + 1 Vermutung, die Vermutung von Ulam (nach Stanisław Ulam), das Problem von Kakutani (nach Shizuo Kakutani), die Vermutung von Thwaites (nach Herrn Bryan Thwaites), der Algorithmus von Hasse (nach Helmut Hasse), oder das Problem von Syracuse; die Folge von beteiligten Zahlen wird die Hagelkorn-Folge oder Hagelkorn-Zahlen, oder als erstaunliche Zahlen genannt.

Nehmen Sie jede natürliche Zahl n. Wenn n sogar ist, teilen Sie ihn durch 2, um n / 2 zu bekommen. Wenn n seltsam ist, multiplizieren Sie ihn mit 3 und tragen Sie 1 bei, um 3n + 1 vorzuherrschen. Wiederholen Sie den Prozess (der "Hälfte Oder Dreifach Plus Ein", oder HOTPO genannt worden ist) unbestimmt. Die Vermutung ist, dass, egal was Zahl Sie damit anfangen, Sie immer schließlich 1 reichen werden. Das Eigentum ist auch Einheit genannt worden.

Paul Erdős hat angeblich über die Vermutung von Collatz gesagt: "Mathematik ist für solche Probleme noch nicht reif" und hat auch 500 $ für seine Lösung angeboten.

2007 arbeiten Forscher Kurtz und Simon, aufbauend früher durch J.H. Conway in den 1970er Jahren, hat bewiesen, dass eine natürliche Generalisation des Problems von Collatz algorithmisch unentscheidbar ist.

Behauptung des Problems

Denken Sie die folgende Operation auf einer willkürlichen positiven ganzen Zahl:

• Wenn die Zahl sogar ist, teilen Sie sie durch zwei.
• Wenn die Zahl seltsam ist, verdreifachen Sie sie und fügen Sie diejenige hinzu.

In der arithmetischen Modulnotation, definieren Sie die Funktion f wie folgt:

:

Bilden Sie jetzt eine Folge, indem Sie diese Operation wiederholt durchführen, mit jeder positiven ganzen Zahl beginnend, und das Ergebnis an jedem Schritt als der Eingang am folgenden nehmend.

In der Notation:

:

(der ist: Ist der Wert von angewandten zu rekursiv Zeiten)

oder

:

{a_ {ich}} = \frac {1} {2} {a_ {i-1}} - \frac {1} {4} (5a_ {i-1} +2) ((-1) ^ {a_ {i-1}}-1)

</Mathematik>

(der für sogar und für den sonderbaren trägt).

Die Collatz-Vermutung ist: Dieser Prozess wird schließlich die Nummer 1 erreichen, unabhängig von der positive ganze Zahl am Anfang gewählt wird.

Dieser kleinste ich solch, dass = 1 den Gesamtarbeitsschluss von n genannt wird. Die Vermutung behauptet, dass jeder n einen bestimmten Gesamtarbeitsschluss hat. Wenn, für einen n, solch ein ich nicht bestehe, sagen wir, dass n unendlichen Gesamtarbeitsschluss hat und die Vermutung falsch ist.

Wenn die Vermutung falsch ist, kann es nur sein, weil es eine Startzahl gibt, die eine Folge verursacht, die 1 nicht enthält. Solch eine Folge könnte in einen sich wiederholenden Zyklus eingehen, der 1, oder Zunahme ohne bestimmten ausschließt. Keine solche Folge ist gefunden worden.

Beispiele

Zum Beispiel, mit n = 6 anfangend, bekommt man die Folge 6, 3, 10, 5, 16, 8, 4, 2, 1.

n = 11 nimmt zum Beispiel länger, um 1 zu reichen: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Die Folge für n = 27, verzeichnet und grafisch dargestellt unten, macht 111 Schritte, auf mehr als 9000 vor dem Absteigen zu 1 kletternd.

: {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 }\

Zahlen mit einem Gesamtarbeitsschluss, der länger ist als jeder kleinere Startwert, bilden eine Folge, die beginnt mit:

: 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, ….

Der längste Fortschritt für jede anfängliche Startzahl, die weniger als 100 Millionen 63,728,127 sind, der 949 Schritte hat. Für Startzahlen weniger als 1 Milliarde ist es 670,617,279, mit 986 Schritten, und für Zahlen weniger als 10 Milliarden, die es 9,780,657,630, mit 1132 Schritten ist.

Die Mächte zwei laufen zu einer schnell zusammen, weil halbierte Zeiten ist, um ein zu reichen und nie vergrößert wird.

Programm, um Hagelkorn-Folgen zu berechnen

Eine spezifische Hagelkorn-Folge kann leicht geschätzt werden, wie durch dieses Pseudocodebeispiel gezeigt wird:

:function-Hagelkorn (n)

:: während n> 1

::: zeigen Sie n

::: wenn n dann seltsam

ist

:::: Satz n = 3n + 1

::: sonst

:::: Satz n = n / 2

::: endif

:: endwhile

:: zeigen Sie n

Dieses Programm hinkt, wenn die Folge 1 reicht, um zu vermeiden, einen endlosen Zyklus 4, 2, 1 zu drucken. Wenn die Vermutung von Collatz wahr ist, wird das Programm immer hinken (halten an), egal was positive ganze Startzahl ihm gegeben wird.

M Zyklen kann nicht vorkommen

Die Vermutung konnte indirekt demzufolge des folgenden bewiesen werden:

• keine unendliche auseinander gehende Schussbahn kommt vor
• kein Zyklus kommt vor

Diese, wahr seiend, würden alle natürlichen Zahlen eine Schussbahn unten zu einer haben.

1977 hat R. Steiner, und 2000 und 2002, J. Simons und B. de Weger (gestützt auf der Arbeit von Steiner), das Nichtsein von bestimmten Typen von Zyklen bewiesen.

Notation

Um das zu erklären, beziehen wir uns auf die "Abkürzungs"-Definition der Karte von Collatz, für sonderbaren n und für sogar n.

Ein Zyklus ist eine Folge wo, und so weiter, bis zu in einem geschlossenen Regelkreis. Der einzige bekannte Zyklus ist (1,2).

Wenn der Zyklus aus einer zunehmenden Folge von von einer abnehmenden Folge von geraden Zahlen gefolgten ungeraden Zahlen besteht, wird es einen 1 Zyklus genannt. Wenn es aus einer zunehmenden Folge von ungeraden Zahlen besteht, dann eine abnehmende Folge von geraden Zahlen, dann eine andere zunehmende Folge von ungeraden Zahlen, dann eine andere abnehmende Folge von geraden Zahlen, wird es einen 2-Zyklen-genannt. Im Allgemeinen hat eine M Zyklus M Subfolgen von einer oder mehr ungeraden Zahlen, die mit der M Subfolgen von einer oder geraderen Zahlen verflochten sind.

Lehrsätze

• Steiner hat sich 1977 (anders erwiesen als das triviale (1,2)).
• Simons hat sich 2000 (gestützt auf der Methode von Steiner) erwiesen.
• Simons/deWeger 2003 hat ihren eigenen Beweis bis zu "68 Zyklen" erweitert: (Steiner hat in einer Usenet-Diskussion gefordert er konnte das bis zur M = 71 erweitern.) Darüber hinaus 68 gibt die Methode obere Grenzen für die Elemente in solch einem Zyklus zum Beispiel, "Wenn es einen 75-Zyklen-gibt, dann ist mindestens ein Element des Zyklus weniger als 2385×2." Deshalb, als erschöpfende Computersuchen weitergehen, können ein bisschen größere Zyklen ausgeschlossen werden.

Methoden des Beweises

Es hat viele Methoden des Angriffs auf das Problem gegeben. Lassen Sie zum Beispiel A und B ganze Zahlen sein. A seiend, wie oft "3n+1" Regel in einem Zyklus und B verwendet wird, der ist, wie oft die "N/2"-Regel verwendet wird. Lassen Sie x die niedrigste Zahl in einem Zyklus dann unabhängig davon sein, welche Ordnung die Regeln verwendet werden, haben wir:

:

\frac {3^A} {2^B} x + C = x

</Mathematik>

wo C das "Übermaß" ist, das durch "+1" in der Regel verursacht ist, und gezeigt werden kann, größer zu sein, als:

:

C \ge \frac {3^ {a-1}} {2^B }\

</Mathematik>

das Verwenden geometrischen Fortschritts. Das Umordnen von Shows, die die niedrigste Zahl im Zyklus befriedigt:

:

x\ge \frac {3^ {a-1}} {2^B-3^A }\

</Mathematik>

der einen niedrigeren gibt, der für die niedrigste Zahl in einem Zyklus für eine gegebene Zyklus-Länge gebunden ist. Für große Zyklen, wie man erwarten würde, neigte der Bruchteil 3/2 zu 1, so dass tiefer bestimmt groß sein würde.

Das Unterstützen von Argumenten

Obwohl die Vermutung nicht bewiesen worden ist, denken die meisten Mathematiker, die ins Problem geblickt haben, dass die Vermutung wahr ist, weil experimentelle Beweise und heuristische Argumente es unterstützen.

Experimentelle Beweise

Die Vermutung ist durch den Computer für alle Startwerte bis zu 5 × 2  5.764 überprüft worden. Alle Anfangswerte haben bis jetzt schließlich Ende im sich wiederholenden Zyklus {4,2,1} geprüft, der nur drei Begriffe hat. Es ist auch bekannt, dass {4,2,1} der einzige sich wiederholende mit weniger als 35,400 Begriffen mögliche Zyklus ist.

Solche Computerbeweise sind nicht ein Beweis, dass die Vermutung wahr ist. Wie gezeigt, in den Fällen der Vermutung von Pólya, der Vermutung von Mertens und der Zahl von Skewes, manchmal werden einzige Gegenbeispiele einer Vermutung gefunden, wenn man sehr große Anzahl verwendet. Seit dem folgenden Überprüfen aller natürlichen Zahlen ist ein Prozess, der nie vollendet werden kann, kann solch eine Annäherung nie demonstrieren, dass die Vermutung bloß wahr ist, dass keine Gegenbeispiele noch entdeckt worden sind.

Ein probabilistic heuristischer

Wenn man nur die ungeraden Zahlen in der durch den Prozess von Collatz als erzeugten Folge betrachtet, dann ist jede ungerade Zahl durchschnittlich 3/4 von der vorherigen. (Genauer ist das geometrische Mittel der Verhältnisse von Ergebnissen 3/4.) Gibt das ein heuristisches Argument nach, dass jede Hagelkorn-Folge im langen Lauf abnehmen sollte, obwohl das nicht Beweise gegen andere Zyklen nur gegen die Abschweifung ist. Das Argument ist nicht ein Beweis, weil es annimmt, dass Hagelkorn-Folgen von unkorrelierten probabilistic Ereignissen gesammelt werden. (Es stellt wirklich streng fest, dass die 2-adic Erweiterung des Prozesses von Collatz zwei Abteilungsschritte für jeden Multiplikationsschritt für fast alle 2-adic Startwerte hat.)

Strenge Grenzen

Obwohl es streng nicht bekannt ist, ob alle positiven Zahlen schließlich ein gemäß der Wiederholung von Collatz reichen, ist es bekannt, dass viele Zahlen so tun. Insbesondere Krasikov und Lagarias haben gezeigt, dass die Zahl von ganzen Zahlen im Zwischenraum [1, x], die schließlich reichen, man ist mindestens zu x proportional.

Andere Formulierungen der Vermutung

Rückwärts

Es gibt eine andere Annäherung, um die Vermutung zu beweisen, die von unten nach oben in Betracht zieht

Methode, den so genannten Graphen von Collatz anzubauen. Der Collatz Graph ist ein Graph, der durch die umgekehrte Beziehung definiert ist

Also, anstatt zu beweisen, dass alle natürlichen Zahlen schließlich 1 führen, können wir beweisen, dass 1 zu allen natürlichen Zahlen führt. Für jede ganze Zahl n, n  1 (mod 2) iff 3n + 1  4 (mod 6). Gleichwertig, (n  1)/3  1 (mod 2) iff n  4 (mod 6). Mutmaßlich bildet diese umgekehrte Beziehung einen Baum abgesehen von der 1-2-4 Schleife (das Gegenteil der 1-4-2 Schleife der unveränderten Funktion f definiert in der Behauptung des Problems oben). Wenn die Beziehung 3n + 1 der Funktion f durch die allgemeine Ersatz-"Abkürzungs"-Beziehung (3n + 1)/2 ersetzt wird, wird der Graph von Collatz durch die umgekehrte Beziehung, definiert

Mutmaßlich bildet diese umgekehrte Beziehung einen Baum abgesehen von einer 1-2 Schleife (das Gegenteil der 1-2 Schleife der Funktion f (n) revidiert, wie angezeigt, oben).

Als eine abstrakte Maschine, die in der Basis zwei rechnet

Wiederholte Anwendungen der Funktion von Collatz können als eine abstrakte Maschine vertreten werden, die Schnuren von Bit behandelt. Die Maschine wird die folgenden drei Schritte auf jeder ungeraden Zahl durchführen, bis nur ein "1" bleiben:

1. Hängen Sie 1 am (richtigen) Ende der Zahl im binären (das Geben 2n + 1) an;
2. Fügen Sie das zur ursprünglichen Zahl durch die binäre Hinzufügung (das Geben 2n + 1 + n = 3n + 1) hinzu;
3. Entfernen Sie das ganze Schleppen "0" s (d. h. teilen Sie sich wiederholt durch zwei, bis das Ergebnis seltsam ist).

Diese Vorschrift ist zur Computerwissenschaft einer Hagelkorn-Folge in der Basis zwei einfach gleichwertig.

Beispiel

Die Startnummer 7 wird in der Basis zwei als 111 geschrieben. Die resultierende Hagelkorn-Folge ist:

111

1011

10001

1101

101

1

Als eine Paritätsfolge

Für diese Abteilung, denken Sie die Funktion von Collatz in der ein bisschen modifizierten Form

:

Das kann getan werden, weil, wenn n, 3n + 1 seltsam ist, immer gleich ist.

Wenn P (…) die Gleichheit einer Zahl ist, die P (2n) = 0 und P (2n + 1) = 1 ist, dann können wir die Hagelkorn-Paritätsfolge für eine Nummer n als p = P (a), wo = n, und = f (a) definieren.

Mit dieser Form für f (n) kann es gezeigt werden, dass die Paritätsfolgen für zwei Zahlen, die M und n in den ersten K-Begriffen abstimmen werden, wenn, und nur wenn M und n gleichwertiger modulo 2 sind. Das deutet an, dass jede Zahl durch seine Paritätsfolge, und außerdem dass einzigartig identifiziert wird, wenn es vielfache Hagelkorn-Zyklen gibt, dann müssen ihre entsprechenden Paritätszyklen verschieden sein.

Der Beweis ist einfach: Es ist leicht, mit der Hand nachzuprüfen, dass Verwendung des f k Zeiten zur Zahl a fungiert · 2 + wird b das Ergebnis a geben · 3 + d, wo d das Ergebnis ist, die F-Funktion k Zeiten zu b anzuwenden, und ist c, auf wie viele ungerade Zahlen während dieser Folge gestoßen wurde. So wird die Gleichheit der ersten k Zahlen rein durch b bestimmt, und sich die Gleichheit (k + 1) th Zahl wenn das am wenigsten bedeutende Bit ändern wird, geändert zu sein.

Die Collatz-Vermutung kann als das Angeben umformuliert werden, dass die Hagelkorn-Paritätsfolge für jede Zahl schließlich in den Zyklus 0  1  0 eingeht.

Als ein Anhängsel-System

Weil Collatz in der Form fungieren

Hagelkorn-Folgen können durch den äußerst einfachen geschätzt werden

mit der Produktion herrscht

über

ein  bc, b  a, c  aaa. In diesem System wird die positive ganze Zahl n durch eine Schnur von n a's und Wiederholung der Anhängsel-Operationshalte auf jedem Wort der Länge weniger als 2 vertreten. (Angepasst von De Mol.)

Die Collatz-Vermutung stellt gleichwertig fest, dass dieses Anhängsel-System, mit einer willkürlichen begrenzten Schnur von a's als das anfängliche Wort, schließlich hinkt (sieh für ein bearbeitetes Beispiel).

Erweiterungen auf größere Gebiete

Das Wiederholen auf allen ganzen Zahlen

Eine offensichtliche Erweiterung soll alle ganzen Zahlen, nicht nur positive ganze Zahlen einschließen. In diesem Fall gibt es insgesamt 5 bekannte Zyklen, in die alle ganzen Zahlen scheinen, schließlich unter der Wiederholung von f zu fallen. Diese Zyklen werden hier verzeichnet, mit dem wohl bekannten Zyklus für positiven n anfangend.

Sonderbare Werte werden im kühnen verzeichnet. Jeder Zyklus wird mit seinem Mitglied des am wenigsten absoluten Werts verzeichnet (der immer seltsam ist oder Null) zuerst.

Die Verallgemeinerte Collatz-Vermutung ist die Behauptung, dass jede ganze Zahl, unter der Wiederholung durch f, schließlich in einen dieser fünf Zyklen fällt.

Das Wiederholen mit sonderbaren Nennern oder 2-adic ganzen Zahlen

Die Standardkarte von Collatz kann zu (positiv oder negativ) rationale Zahlen erweitert werden, die sonderbare Nenner, wenn geschrieben, in niedrigsten Begriffen haben. Die Zahl wird genommen, um seltsam zu sein, oder sogar gemäß, ob sein Zähler seltsam oder gleich ist. Eine nah zusammenhängende Tatsache ist, dass sich die Karte von Collatz bis zu den Ring von 2-adic ganzen Zahlen ausstreckt, der den Ring von rationals mit sonderbaren Nennern als ein Subring enthält.

Die Paritätsfolgen, sind wie definiert, oben für Bruchteile nicht mehr einzigartig. Jedoch kann es gezeigt werden, dass jeder mögliche Paritätszyklus die Paritätsfolge für genau einen Bruchteil ist: Wenn ein Zyklus Länge n hat und ungerade Zahlen genau M Zeiten an Indizes k, …, k einschließt, dann ist der einzigartige Bruchteil, der diesen Paritätszyklus erzeugt

:

Zum Beispiel hat der Paritätszyklus (1 0 1 1 0 0 1) Länge 7 und hat 4 ungerade Zahlen an Indizes 0, 2, 3, und 6. Der einzigartige Bruchteil, der diesen Paritätszyklus erzeugt, ist

:

der ganze Zyklus zu sein: 151/47  250/47  125/47  211/47  340/47  170/47  85/47  151/47

Obwohl die zyklischen Versetzungen der ursprünglichen Paritätsfolge einzigartige Bruchteile sind, ist der Zyklus, der Bruchteil jeder Versetzung nicht einzigartig, der die folgende Zahl im Schleife-Zyklus ist:

: (0 1 1 0 0 1 1) 

: (1 1 0 0 1 1 0) 

: (1 0 0 1 1 0 1) 

: (0 0 1 1 0 1 1) 

: (0 1 1 0 1 1 0) 

: (1 1 0 1 1 0 0) 

Außerdem für die Einzigartigkeit sollte die Paritätsfolge, d. h., nicht partitionable in identische Subfolgen "erst" sein. Zum Beispiel kann Paritätsfolge (1 1 0 0 1 1 0 0) in zwei identische Subfolgen (1 1 0 0) (1 1 0 0) verteilt werden. Das Rechnen des 8-Elemente-Folge-Bruchteils gibt

: (1 1 0 0 1 1 0 0) 

Aber wenn reduziert, auf niedrigste Begriffe {5/7} ist es dasselbe als diese der 4-Elemente-Subfolge

: (1 1 0 0) 

Und das ist, weil die 8-Elemente-Paritätsfolge wirklich zwei Stromkreise des durch die 4-Elemente-Paritätsfolge definierten Schleife-Zyklus vertritt.

In diesem Zusammenhang ist die Vermutung von Collatz zum Ausspruch gleichwertig, der (0 1) der einzige Zyklus ist, der durch positive ganze Zahlen (d. h. 1 und 2) erzeugt wird.

Das Wiederholen auf reellen Zahlen oder komplexen Zahlen

Die Collatz-Karte kann als die Beschränkung zu den ganzen Zahlen der glatten echten und komplizierten Karte angesehen werden

:

der zu vereinfacht

Wenn die Standardkarte von Collatz, die oben definiert ist, durch das Ersetzen der Beziehung 3n + 1 mit der allgemeinen Ersatz-"Abkürzungs"-Beziehung (3n + 1)/2 optimiert wird, kann es als die Beschränkung zu den ganzen Zahlen der glatten echten und komplizierten Karte angesehen werden

:

der dazu vereinfacht.

Collatz fractal

Das Wiederholen der obengenannten optimierten Karte im komplizierten Flugzeug erzeugt Collatz fractal.

Der Gesichtspunkt der Wiederholung auf der echten Linie wurde von Chamberland (1996), und auf dem komplizierten Flugzeug von Letherman, Schleicher und Wood (1999) untersucht.

Optimierungen

Weil gibt eine Paritätsfolge-Abteilung oben eine Weise, Simulation der Folge zu beschleunigen. Um vorn k Schritte auf jeder Wiederholung (das Verwenden der F-Funktion von dieser Abteilung) zu springen, zerbrechen Sie die aktuelle Zahl in zwei Teile, b (die k am wenigsten bedeutenden Bit, die als eine ganze Zahl interpretiert sind), und (der Rest der Bit als eine ganze Zahl). Das Ergebnis des Springens vorn k Schritte kann als gefunden werden:

:f (2 + b) = 3 + d (b).

Der c und die D-Reihe werden für alle möglichen K-Bit-Zahlen b vorberechnet, wo d (b) das Ergebnis ist, die F-Funktion k Zeiten zu b anzuwenden, und c (b) die Zahl von ungeraden Zahlen gestoßen unterwegs ist. Zum Beispiel, wenn k=5, Sie vorn 5 Schritte auf jeder Wiederholung springen können, indem Sie die 5 am wenigsten bedeutenden Bit einer Zahl und des Verwendens trennen:

: c (0.. 31) = {0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5 }\

: d (0.. 31) = {0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242}.

Das verlangt, dass 2 Vorberechnung und Lagerung die resultierende Berechnung durch einen Faktor von k, einem Raum-Zeit-Umtausch beschleunigt.

Zum speziellen Zweck, nach einem Gegenbeispiel zur Vermutung von Collatz zu suchen, führt diese Vorberechnung zu einer noch wichtigeren Beschleunigung wegen Tomás Oliveiras e Silva und wird in der Rekordbestätigung der Vermutung von Collatz verwendet. Wenn, für einige gegeben b und k, die Ungleichheit

:f (2 + b) = 3 + d (b) + b

hält für den ganzen a, dann kann das erste Gegenbeispiel, wenn es besteht, nicht b modulo 2 sein. Zum Beispiel muss das erste Gegenbeispiel weil f (2n) = n seltsam sein; und es müssen 3 mod 4 weil f (4n + 1) = 3n + 1 sein. Für jeden Startwert, der nicht ein Gegenbeispiel zur Vermutung von Collatz ist, gibt es einen k, für den solch eine Ungleichheit hält, so überprüfend, dass die Vermutung von Collatz für einen Startwert so gut ist wie Überprüfung einer kompletten Kongruenz-Klasse. Als k Zunahmen muss die Suche nur jene Rückstände b überprüfen, die durch niedrigere Werte von k nicht beseitigt werden. Auf der Ordnung von 3 Rückständen überleben. Zum Beispiel sind die einzigen überlebenden Rückstände mod 32 7, 15, 27, und 31; nur 573,162 Rückstände überleben mod 2 = 33,554,432.

Funktion von Syracuse

Wenn k eine sonderbare ganze Zahl ist, dann ist 3k + 1 sogar, so können wir 3k + 1 = 2k , mit k' seltsam und ein  1 schreiben. Wir definieren eine Funktion f vom Satz von sonderbaren ganzen Zahlen in sich, genannt die Funktion von Syracuse, indem wir f (k) = k  nehmen.

Einige Eigenschaften der Funktion von Syracuse sind:

• f (4k + 1) = f (k) für den ganzen k darin.
• Für den ganzen p  2 und h seltsam, f (2 h  1) = 2 · 3h  1 (hier ist f Funktionswiederholungsnotation).
• Für den ganzen sonderbaren h, f (2h  1)  (3h  1)/2

Die Syracuse-Vermutung ist, dass für den ganzen k darin, dort eine ganze Zahl n  1 solcher dass f (k) = 1 besteht. Lassen Sie gleichwertig E der Satz von sonderbaren ganzen Zahlen k sein, für den dort eine ganze Zahl n  1 solcher dass f (k) = 1 besteht. Das Problem ist, dem E = zu zeigen. Der folgende ist der Anfang eines Versuchs eines Beweises durch die Induktion:

1, 3, 5, 7, und 9 sind bekannt, Elemente von E zu sein. Lassen Sie k eine sonderbare ganze Zahl sein, die größer ist als 9. Nehmen Sie an, dass die ungeraden Zahlen bis zu und einschließlich k  2 in E sind und uns versuchen lassen zu beweisen, dass k in E ist. Da k seltsam ist, k + 1 ist sogar, so können wir k + 1 = 2h für p  1, h seltsam, und k = 2h  1 schreiben. Jetzt haben wir:

• Wenn p = 1, dann k = 2h  1. Es ist leicht, dass f (k) h   1 zu überprüfen; dann f (k ) = k, und als k  mod 4 können wir noch dem k  E zeigen.

Der problematische Fall ist dass wo p  2, h nicht vielfach 3 und h  (1) mod 4. Hier, wenn wir schaffen, das für jede sonderbare ganze Zahl k , 1  k   k  2 zu zeigen; 3k   E werden wir getan.

Siehe auch

• Rückstand klassenkluge affine Gruppen
• Modularithmetik
• BOINC
• Verteilte Computerwissenschaft

Referenzen

Verweisungen und Außenverbindungen

Papiere

• Günther J. Wirsching. Das Dynamische nach der Funktion Erzeugte System. Nummer 1681 in Vortrag-Zeichen in der Mathematik. Springer-Verlag, 1998.
• Keith Matthews 3x + 1 Seite: Rezension des Fortschritts, plus verschiedene Programme
• Marc Chamberland. Eine dauernde Erweiterung 3x + 1 Problem zur echten Linie. Dynam. Contin. Getrennte Impuls Systeme 2:4 (1996), 495-509.
• Simon Letherman, Dierk Schleicher und Reg Wood: (3n + 1) - Problem und Holomorphic Dynamik. Experimentelle Mathematik 8:3 (1999), 241-252.
• Ohira, Reiko & Yamashita, Michinori Eine Generalisation des Problems von Collatz
• Urata Toshio haben Einige Holomorphic-Funktionen mit dem Collatz Problem in Verbindung gestanden
• Matti K. Sinisalo: Auf den minimalen Zyklus-Längen der Folgen von Collatz, des Vorabdrucks, Juni 2003, Universität von Oulu
• Paul Stadfeld: Entwurf für den Misserfolg: Wie man ein Gegenbeispiel zur Collatz-Vermutung baut
• De Mol, Liesbeth, "Anhängsel-Systeme und Collatz ähnliche Funktionen", Theoretische Informatik, 390:1, 92-101, Januar 2008 (Vorabdruck Nr. 314).
• Van Bendegem, Jean Paul, "Die Collatz-Vermutung: Eine Fallstudie im Mathematischen Problem-Lösen", Logische und Logikphilosophie, Band 14 (2005), 7-23
• Belaga, Edward G., "Über 3x+1 Mysterium", Universität des Straßburger Vorabdrucks, 1998 nachdenkend.
• Belaga, Edward G.; Mignotte, Maurice, "Vorsichtig in die Collatz Wildnis spazieren gehend: Numerieren Sie algorithmisch Theoretisch, Zufällig", das Vierte Kolloquium auf der Mathematik und Informatik: Algorithmen, Bäume, Combinatorics und Probabilities, am 18-22 September 2006, Institut Élie Cartan, Nancy, Frankreich
• Belaga, Edward G.; Mignotte, Maurice, "3x+1 Vermutung in 3x+d Zusammenhang", Experimentelle Mathematik, Band 7, Ausgabe 2, 1998 einbettend.
• Steiner, R.P.; "Ein Lehrsatz auf dem syracuse Problem", Verhandlungen der 7. Manitoba Konferenz für die Numerische Mathematik, Seiten 553-559, 1977.
• Simons, J.; de Weger, B.; "Theoretische und rechenbetonte Grenzen für die M Zyklen 3n + 1 Problem", Acta Arithmetica, (Online-Version 1.0, am 18. November 2003), 2005.
• Sinyor, J.; "3x+1 Problem als ein Schnur-Neuschreiben-System", Internationale Zeitschrift von Mathematik und Mathematischen Wissenschaften, Band 2010 (2010), Artikel-Personalausweis 458563, 6 Seiten.

Bücher

• Kerl, Richard K., Ungelöste Probleme in der Zahlentheorie, dem Springer, 2004. Internationale Standardbuchnummer 0-387-20860-7. Vgl pp.336-337, "E17: Versetzungsfolgen" und die Collatz-Vermutung.

Allgemein

• Verteiltes Rechenprojekt, das die Vermutung von Collatz für größere Werte nachprüft.
• Ein andauerndes verteiltes Rechenprojekt von Eric Roosendaal prüft die Vermutung von Collatz für größere und größere Werte nach.
• Ein anderes andauerndes verteiltes Rechenprojekt von Tomás Oliveira e Silva setzt fort, die Vermutung von Collatz (mit weniger Statistik nachzuprüfen, als die Seite von Eric Roosendaal, aber mit weiteren Fortschritten gemacht).
• Eine belebte Durchführung, die Arithmetik der willkürlichen Präzision verwendet.
• Hagelkorn-Muster besprechen verschiedene Resonatore zusammen mit dem Verwenden wichtiger Zahlen im Problem (wie 6 und 3^5), um Muster zu entdecken.
• Collatz Pfade durch Jesse Nochella, Wolfram-Demonstrationsprojekt.
• Seite, die erlaubt, die Annahme für eine gegebene Zahl zu studieren und zu zeigen
• Zyklen von Collatz? über Zyklen, sehr grundlegend, enthält auch einige ungewöhnliche Graphen (HTML)
• Zyklen von Collatz? (pdf) über Schleifen, zusammengepressten Text, ziemlich grundlegend (pdf)
• Folge von Collatz für jede Zahl bis zu 500 Ziffern in der Länge.