Sur la formation des séquences dans l'hypothèse Collatz (3n + 1)

Je suis attiré par des tâches telles que le problème Collatz. Ils sont faciles à formuler et à former parfaitement votre tête, en particulier la pensée algorithmique, ce qui est très utile pour le programmeur.

La tâche est formulée tout simplement:

Prenez n'importe quel nombre naturel n. S'il est pair, divisez-le par 2, et s'il est impair, multipliez-le par 3 et ajoutez 1 (nous obtenons 3n + 1). Nous effectuons les mêmes actions sur le nombre résultant, et ainsi de suite.

L'hypothèse de Collatz est que, quel que soit le nombre initial n que nous prenons, tôt ou tard nous en obtiendrons un.

Algorithmiquement, cela ressemble à ceci:

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

Par exemple, prenez n = 5. Il est impair, ce qui signifie que nous effectuerons l'action sur l'impaire, c'est-à-dire 3n + 1 => 16. 16 est pair, c'est-à-dire que nous effectuerons l'action sur le pair, c'est-à-dire n / 2 => 8 => 4 => 2 => 1.
La séquence s'est formée à n = 5: 16, 8, 4, 2, 1.

Je vous demande de me pardonner mes calculs, faites-moi savoir si je fais une erreur quelque part.

Supposons le nombre total d'informations sur l'unité et le nombre réel d'informations sur l'unité. Indiquez ces étapes.

Considérez la séquence pour n = 7:

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

Il y a 16 étapes au total et les vraies étapes qui sont réellement jetées dans un autre ensemble de nombres sont 5 d'entre elles:

7, 11, 17, 13, 5.

La vraie étape Sa (n) est le nombre d'opérations 3n + 1 sur le nombre nécessaire pour atteindre l'unité.

L'idée est clairement démontrée par l'exemple d'un tableau:

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

Dans un tel tableau, l'ordre, son propre motif, est déjà visible.
Comme vous pouvez le voir, la puissance de deux ne deviendra jamais étrange, donc cela se résume à une simple division.
Une séquence de Sa (0) est formée par une seule formule.

$$

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

Aucune vraie démarche n’est nécessaire, par simple division, tout sera réduit à l’unité.
Sachant cela, vous pouvez supprimer du tableau tous les nombres qui sont des multiples de deux.

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

Maintenant, il est plus difficile de saisir le modèle, mais il y en a un. La chose la plus intéressante maintenant est la formation de séquences. Pas juste comme ça, le chiffre suivant après 5 est 21 et après 85.
En fait, Sa (1) est la séquence A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). Il est formé par la formule:

$$

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

La même séquence peut être décrite par une formule récursive:

$$

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

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 * 5 + 1 = 21;$
$$$P (21) = 4 * 21 + 1 = 85;$
Et ainsi de suite ...

Une série de la première étape est construite, bien qu'elle puisse se poursuivre indéfiniment. Passons à la deuxième étape. La formule de transition vers l'étape 2 peut être exprimée à partir d'une formule impaire.
Sachant que nous allons partager le résultat $$ plusieurs fois, il peut s'écrire $$$2 ^ {2 \ alpha}$où $$$\ alpha$- nombre de divisions.

$$

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

La formule finale prend la forme:

$$

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

Nous introduisons également un ajustement pour $$$\ beta$comme $$$2 ^ {2 \ alpha + \ beta}$de sorte que l'option de diviser le nombre non un multiple de 3 par 3 se produit.

$$

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

Vérifions la formule, puisque l'alpha est inconnu, recherchons 5 alpha consécutifs:

$$

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

Ainsi, la séquence de la deuxième étape commence à se former. Cependant, on peut noter que 113 n'est pas dans l'ordre, il est important de se rappeler que la formule a été calculée à partir de 5 .

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

Pour résumer:

Lot de $$$Sa (n + 1)$généré par la fonction $$$n (P (k), \ alpha, \ beta)$de chaque élément de l'ensemble de $$$Sa (n)$.

Sachant cela, vous pouvez toujours raccourcir le tableau en supprimant tous les multiples d'alpha.

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

Pour être clair, voici un exemple de la façon dont les éléments d'un ensemble de $$$Sa (2)$générer des éléments de l'ensemble à partir de $$$Sa (3)$pour alpha de 0 à 4.

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

En combinant ces ensembles, nous obtenons l'ensemble de 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 ...

De plus, la suppression du degré $$$\ alpha> 0$nous obtenons:

17, 75, 151 ...

Autrement dit, cela se résume à:

$$

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

Pourquoi quelque part $$$\ beta = 2$et quelque part $$$\ beta = 1$?

Retour à la séquence A002450. Il existe une dépendance intéressante:

$$$P (m) = (4 ^ 3m - 1) / 3$- ne produit pas de séquences enfants.
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$- produit des séquences enfants lorsque $$$\ beta = 2$.
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$- produit des séquences enfants lorsque $$$\ beta = 1$.

Il n'y a que 3 tableaux d'enfants potentiels pour un certain nombre.
Si appliqué à une formule récursive, alors:

Fonction $$$n (\ gamma, \ alpha, \ beta)$où $$$\ gamma$- n'importe quel nombre multiple de 3 forme un ensemble vide ⨂.

$$

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

Fonction $$$n (\ lambda, \ alpha, \ beta)$où $$$\ lambda$- tout nombre généré $$$\ gamma$à $$$\ beta = 2$forme l'ensemble des nombres K appartenant à l'ensemble des nombres naturels N.

$$

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

Fonction $$$n (P (\ lambda), \ alpha, \ beta)$à $$$\ beta = 1$forme l'ensemble des nombres L appartenant à l'ensemble des nombres naturels N.

$$

$$L (n (P (\ lambda), \ alpha, 1)) ⊆ N.$$

De toute évidence, cela peut en quelque sorte être réduit à une formulation plus rigoureuse et fondée sur des preuves.

En fait, c'est ainsi que les séquences se forment dans l'hypothèse Collatz.
Il reste un détail. Il est nécessaire de restaurer des ensembles complets à partir d'étapes absolues à partir des ensembles que nous avons obtenus.

Formule pour Odd:

$$

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

En plus des impairs, vous devez restaurer de nombreux pairs. Pour ce faire, rappelez la formule:

$$

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

Il ne reste plus qu'à corréler tous ensemble:

$$

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

La version finale:

$$

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

Ainsi, tout k peut générer une séquence.

L'inverse est-il vrai que l'un des nombres naturels appartient définitivement à une séquence de $$$n (k)$?

Si oui, alors il est tout à fait possible que Collatz ait eu raison.

Pour le dernier exemple d'implémentation de la fonction javascript:

 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 ]