Zur Bildung von Sequenzen in der Collatz-Hypothese (3n + 1)

Ich bin von Aufgaben wie dem Collatz-Problem angezogen. Sie sind einfach zu formulieren und trainieren Ihren Kopf perfekt, insbesondere algorithmisches Denken, was für den Programmierer sehr nützlich ist.

Die Aufgabe ist ganz einfach formuliert:

Nimm eine natürliche Zahl n. Wenn es gerade ist, teilen Sie es durch 2, und wenn es ungerade ist, multiplizieren Sie es mit 3 und addieren Sie 1 (wir erhalten 3n + 1). Wir führen die gleichen Aktionen für die resultierende Anzahl aus und so weiter.

Collatz 'Hypothese ist, dass wir früher oder später eine bekommen werden, egal welche Anfangszahl n wir nehmen.

Algorithmisch sieht es so aus:

while (number > 1) { if (number % 2 === 0) number = number / 2; else number = 3 * number +1; } 

Nehmen Sie zum Beispiel n = 5. Es ist ungerade, was bedeutet, dass wir die Aktion für die ungerade ausführen, dh 3n + 1 => 16. 16 ist gerade, das heißt, wir führen die Aktion für die gerade aus, dh n / 2 => 8 => 4 => 2 => 1.
Die bei n = 5: 16, 8, 4, 2, 1 gebildete Sequenz.

Ich bitte Sie, mir meine Mathematik zu verzeihen. Lassen Sie mich wissen, wenn ich irgendwo einen Fehler mache.

Lassen Sie uns die Gesamtzahl der Informationen über das Gerät und die tatsächliche Anzahl der Informationen über das Gerät herausgreifen. Bezeichnen Sie diese Schritte.

Betrachten Sie die Reihenfolge für n = 7:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Insgesamt gibt es 16 Schritte. Und die wahren Schritte , die tatsächlich in einen anderen Zahlensatz geworfen werden, sind 5 davon:

7, 11, 17, 13, 5.

Der wahre Schritt Sa (n) ist die Anzahl der Operationen 3n + 1 für die Anzahl, die erforderlich ist, um die Einheit zu erreichen.

Die Idee wird am Beispiel einer Tabelle deutlich:

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
2	5	3	17	11	7	9	25	33	43	57	39	105
4	10	6	34	22	14	18	49	65	86	59	78	203
8	20	12	35	23	15	19	50	66	87	114	79	209
16	21	13	68	44	28	36	51	67	89	115	153	210
32	40	24	69	45	29	37	98	130	182	118	156	211
64	42	26	70	46	30	38	99	131	173	119	157	406
128	80	48	75	88	56	72	100	132	174	228	158	407
256	84	52	136	90	58	74	101	133	177	229	305	409
512	85	53	138	92	60	77	102	134	178	230	306	418

In einer solchen Tabelle ist die Reihenfolge, ihr eigenes Muster, bereits sichtbar.
Wie Sie sehen können, wird die Zweierpotenz niemals ungerade, daher kommt es auf eine einfache Teilung an.
Eine Sequenz aus Sa (0) wird durch nur 1 Formel gebildet.

$$

$$P (0, k) = 2 * 2 ^ k.$$

Es müssen keine wahren Schritte unternommen werden, durch einfache Teilung wird alles auf Einheit reduziert.
Wenn Sie dies wissen, können Sie alle Zahlen, die ein Vielfaches von zwei sind, aus der Tabelle streichen.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
	5	3	17	11	7	9	25	33	43	57	39	105
	21	13	35	23	15	19	49	65	87	59	79	203
	85	53	69	45	29	37	51	67	89	115	153	209
	341	113	75	93	61	77	99	131	173	119	157	211
	1365	213	141	181	117	81	101	133	177	229	305	407

Jetzt ist es schwieriger, das Muster zu erfassen, aber es gibt eines. Das Interessanteste ist jetzt die Bildung von Sequenzen. Nicht nur so, die nächste Ziffer nach 5 ist 21 und danach 85.
Tatsächlich ist Sa (1) die Sequenz A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). Es wird durch die Formel gebildet:

$$

$$P (k) = {4 ^ k-1 \ über 3}.$$

Die gleiche Sequenz kann durch eine rekursive Formel beschrieben werden:

$$

$$P (k) = 4k_0 + 1, mit \ k_0 = 1.$$

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 · 5 + 1 = 21;$
$$$P (21) = 4 · 21 + 1 = 85;$
Usw…

Eine Reihe des ersten Schritts wird erstellt, obwohl er auf unbestimmte Zeit fortgesetzt werden kann. Fahren wir mit Schritt zwei fort. Die Übergangsformel zu Schritt 2 kann aus einer ungeraden Formel ausgedrückt werden.
Zu wissen, dass wir das Ergebnis teilen werden $$$3n + 1$ mehrmals kann es geschrieben werden als $$$2 ^ {2 \ alpha}$ wo $$$\ alpha$ - Anzahl der Abteilungen.

$$

$$P (k) = {3n + 1 \ over2 ^ {2 \ alpha}}; \\ 2 ^ {2 \ alpha} P (k) = 3n + 1; \\ 3n = 2 ^ {2 \ alpha} P. (k) -1;$$

Die endgültige Formel hat folgende Form:

$$

$$n (P (k), \ alpha) = {2 ^ {2 \ alpha} P (k) -1 \ over3};$$

Wir führen auch eine Anpassung für ein $$$\ beta$ wie $$$2 ^ {2 \ alpha + \ beta}$ so dass die Option, die Zahl nicht ein Vielfaches von 3 durch 3 zu teilen, passiert.

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

Lassen Sie uns die Formel überprüfen, da das Alpha unbekannt ist, und auf 5 aufeinanderfolgende Alpha prüfen:

$$

$$n (5, \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} * 5-1 \ over3};$$

$$$n (5,0,1) = (2 ^ {0 + 1} * 5-1) /3=3.$
$$$n (5,1,1) = (2 ^ {2 + 1} * 5-1) /3=13.$
$$$n (5,2,1) = (2 ^ 5 * 5-1) /3=53.$
$$$n (5,3,1) = (2 ^ 7 * 5-1) /3=213.$
$$$n (5,4,1) = (2 ^ 9 * 5-1) /3=853.$

Somit beginnt sich die Sequenz des zweiten Schritts zu bilden. Es kann jedoch festgestellt werden, dass 113 nicht der Reihe nach ist. Es ist wichtig zu bedenken, dass die Formel aus 5 berechnet wurde.

n = 113 in der Tat:
$$$n (85,0,2) = (2 ^ {0 + 2} * 85-1) /3=113.$

Zusammenfassend:

Lot von $$$Sa (n + 1)$ generiert durch Funktion $$$n (P (k), \ alpha, \ beta)$ von jedem Element der Menge aus $$$Sa (n)$ .

Wenn Sie dies wissen, können Sie die Tabelle trotzdem kürzen, indem Sie alle Vielfachen von Alpha entfernen.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7) ...
	5	3	17	11	7	9	...
		113	75	201	267	715	...
		227	151	401	1073	1425	...

Um es klar zu machen, hier ein Beispiel, wie die Elemente einer Menge aus $$$Sa (2)$ Generieren Sie Elemente der Menge aus $$$Sa (3)$ für Alpha von 0 bis 4.

P (k) = 3	P (k) = 113	P (k) = 227
3 aus α = 0 erzeugt: Nichts 13 aus α = 1 erzeugt: 17 69 277 1109 4437 53 aus α = 2 erzeugt: 35 141 565 2261 9045 213 aus α = 3 erzeugt: Nichts 853 aus α = 4 erzeugt: 1137 4549 18197 72789 291157	113 aus α = 0 erzeugt: 75 301 1205 4821 19285 453 aus α = 1 erzeugt: Nichts 1813 aus α = 2 erzeugt: 2417 9669 38677 154709 618837 7253 aus α = 3 erzeugt: 4835 19341 77365 309461 1237845 29013 aus α = 4 erzeugt: Nichts	227 aus α = 0 erzeugt: 151 605 2421 9685 38741 909 aus α = 1 erzeugt: Nichts 3637 aus α = 2 erzeugt: 4849 19397 77589 310357 1241429 14549 aus α = 3 erzeugt: 9699 38797 155189 620757 2483029 58197 aus α = 4 erzeugt: Nichts

Wenn wir diese Mengen kombinieren, erhalten wir die Menge aus Sa (3):

17, 35, 69, 75, 141, 151, 277, 301, 565, 605, 1109, 1137, 1205, 2261, 2275, 2417, 2421, 4437, 4549, 4821, 4835, 4849, 9045, 9101, 9669, 9685, 9699, 17749, 18197, 19285, 19341, 19397, 19417 ...

Darüber hinaus wird der Grad entfernt $$$\ alpha> 0$ wir bekommen:

17, 75, 151 ...

Das heißt, es kommt auf:

$$

$$n (P (k), \ beta) = {2 ^ \ beta P (k) -1 \ over3};$$

Warum irgendwo $$$\ beta = 2$ und irgendwo $$$\ beta = 1$ ?

Zurück zur Sequenz A002450. Es gibt eine interessante Abhängigkeit:

$$$P (m) = (4 ^ 3m-1) / 3$ - erzeugt keine untergeordneten Sequenzen.
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$ - erzeugt untergeordnete Sequenzen, wenn $$$\ beta = 2$ .
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$ - erzeugt untergeordnete Sequenzen, wenn $$$\ beta = 1$ .

Es gibt nur 3 potenzielle untergeordnete Arrays für eine Nummer.
Wenn auf eine rekursive Formel angewendet, dann:

Funktion $$$n (\ gamma, \ alpha, \ beta)$ wo $$$\ gamma$ - Ein beliebiges Vielfaches von 3 bildet eine leere Menge ⨂.

$$

$$A (n (\ gamma), \ alpha, \ beta) = ⨂.$$

Funktion $$$n (\ lambda, \ alpha, \ beta)$ wo $$$\ lambda$ - eine beliebige generierte Nummer $$$\ gamma$ bei $$$\ beta = 2$ bildet die Menge von Zahlen K, die zu der Menge von natürlichen Zahlen N gehört.

$$

$$K (n (P (\ gamma), \ alpha, 2)) ⊆ N.$$

Funktion $$$n (P (\ lambda), \ alpha, \ beta)$ bei $$$\ beta = 1$ bildet die Menge von Zahlen L, die zu der Menge von natürlichen Zahlen N gehört.

$$

$$L (n (P (\ Lambda), \ Alpha, 1)) ⊆ N.$$

Offensichtlich kann dies irgendwie auf eine strengere und evidenzbasierte Formulierung reduziert werden.

Auf diese Weise werden Sequenzen in der Collatz-Hypothese gebildet.
Es ist noch ein Detail übrig. Es ist notwendig, vollständige Sätze aus absoluten Schritten aus den erhaltenen Sätzen wiederherzustellen.

Formel für ungerade:

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

Zusätzlich zu den ungeraden müssen Sie viele gerade wiederherstellen. Rufen Sie dazu die Formel auf:

$$

$$P (0, k) = 2 * 2 ^ k.$$

Es bleibt nur alles zusammen zu korrelieren:

$$

$$n (P (k), \ alpha, \ beta, \ epsilon) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3} * 2 ^ \ epsilon.$$

Die endgültige Version:

$$

$$n (k, \ alpha, \ beta, \ epsilon) = 2 ^ \ epsilon {2 ^ {2 \ alpha + \ beta} (4k + 1) -1 \ over3};$$

Somit kann jedes k eine Sequenz erzeugen.

Ist das Gegenteil der Fall, dass eine der natürlichen Zahlen definitiv zu einer Sequenz aus gehört? $$$n (k)$ ?

Wenn ja, dann ist es durchaus möglich, dass Collatz Recht hatte.

Für das letzte Beispiel der Implementierung der Javascript-Funktion:

 function collatsSequence( number, sequenceLength, alpha, epsilon ) { //     , //  number let set = []; //    while (number % 2 === 0) number /= 2; //    , //   number,  sequenceLength for (let k = 0; k < sequenceLength; k++) { //    alpha for (let a = 0; a < alpha; a++) { //  ,  if (number % 3 === 0) break; //   beta = 1 let numWithBeta = (number * 2 ** (2 * a + 1) - 1) / 3; //      3  beta === 1 //     3  beta === 2 if (Math.floor(numWithBeta) !== numWithBeta) //   beta = 2 numWithBeta = (number * 2 ** (2 * a + 2) - 1) / 3; //      epsilon for (let e = 0; e < epsilon; e++) set.push(numWithBeta * 2 ** e); } //      number = number * 4 + 1; } return set; } console.log( collatsSequence(5, 5, 2, 2) ); // [ 3, 6, 13, 26, 113, 226, 453, 906, 227, 454, 909, 1818 ]