Sobre la formación de secuencias en la hipótesis de Collatz (3n + 1)

Me atraen tareas como el problema de Collatz. Son fáciles de formular y entrenar perfectamente su cabeza, especialmente el pensamiento algorítmico, que es muy útil para el programador.

La tarea se formula de manera bastante simple:

Toma cualquier número natural n. Si es par, divídalo por 2, y si es impar, multiplique por 3 y sume 1 (obtenemos 3n + 1). Realizamos las mismas acciones en el número resultante, y así sucesivamente.

La hipótesis de Collatz es que no importa qué número inicial tomemos, tarde o temprano obtendremos uno.

Algorítmicamente, se ve así:

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

Por ejemplo, tome n = 5. Es impar, lo que significa que realizaremos la acción en el impar, es decir, 3n + 1 => 16. 16 es par, es decir, realizaremos la acción en el par, es decir, n / 2 => 8 => 4 => 2 => 1.
La secuencia formada en n = 5: 16, 8, 4, 2, 1.

Te pido que me perdones por mis matemáticas, avísame si me equivoco en alguna parte.

Señalemos el número total de información sobre la unidad y el número real de información sobre la unidad. Denota estos pasos.

Considere la secuencia para n = 7:

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

Hay 16 pasos en total, y los verdaderos pasos que realmente se incluyen en otro conjunto de números son 5 de ellos:

7, 11, 17, 13, 5.

El verdadero paso Sa (n) es el número de operaciones 3n + 1 en el número necesario para alcanzar la unidad.

La idea se demuestra claramente con el ejemplo de una tabla:

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 5	3	17	11	7 7	9 9	25	33	43	57	39	105
4 4	10	6 6	34	22	14	18 años	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 60	77	102	134	178	230	306	418

En dicha tabla, el orden, su propio patrón, ya es visible.
Como puede ver, el poder de dos nunca será extraño, por lo que se reduce a una división simple.
Una secuencia de Sa (0) está formada por solo 1 fórmula.

$$

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

No es necesario dar pasos verdaderos; por simple división, todo se reducirá a la unidad.
Sabiendo esto, puede eliminar de la tabla todos los números que sean múltiplos de dos.

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 5	3	17	11	7 7	9 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

Ahora es más difícil atrapar el patrón, pero hay uno. Lo más interesante ahora es la formación de secuencias. No solo así, el siguiente dígito después de 5 es 21 y después de 85.
En realidad, Sa (1) es la secuencia A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). Está formado por la fórmula:

$$

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

La misma secuencia se puede describir mediante una fórmula recursiva:

$$

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

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 * 5 + 1 = 21;$
$$$P (21) = 4 * 21 + 1 = 85;$
Y así sucesivamente ...

Se construye una serie del primer paso, aunque puede continuar indefinidamente. Pasemos al paso dos. La fórmula de transición al paso 2 se puede expresar a partir de una fórmula impar.
Sabiendo que vamos a compartir el resultado. $$$3n + 1$ varias veces, se puede escribir como $$$2 ^ {2 \ alpha}$ donde $$$\ alpha$ - número de divisiones.

$$

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

La fórmula final toma la forma:

$$

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

También presentamos un ajuste para $$$\ beta$ como $$$2 ^ {2 \ alpha + \ beta}$ para que ocurra la opción de dividir el número, no un múltiplo de 3 por 3.

$$

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

Verifiquemos la fórmula, ya que el alfa es desconocido, verifiquemos 5 alfa consecutivos:

$$

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

Por lo tanto, la secuencia del segundo paso comienza a formarse. Sin embargo, se puede observar que 113 no está en secuencia, es importante recordar que la fórmula se calculó a partir de 5 .

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

Para resumir:

Lote de $$$Sa (n + 1)$ generado por función $$$n (P (k), \ alpha, \ beta)$ de cada elemento del conjunto de $$$Sa (n)$ .

Luego, sabiendo esto, aún puede acortar la tabla eliminando todos los múltiplos de alfa.

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

Para que quede claro, aquí hay un ejemplo de cómo los elementos de un conjunto de $$$Sa (2)$ generar elementos del conjunto desde $$$Sa (3)$ para alfa de 0 a 4.

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

Combinando estos conjuntos, obtenemos el conjunto 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 ...

Además, eliminando el grado $$$\ alpha> 0$ obtenemos:

17, 75, 151 ...

Es decir, todo se reduce a:

$$

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

Por que en algun lado $$$\ beta = 2$ y en alguna parte $$$\ beta = 1$ ?

Volver a la secuencia A002450. Hay una dependencia interesante:

$$$P (m) = (4 ^ 3m- 1) / 3$ - No produce secuencias secundarias.
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$ - produce secuencias secundarias cuando $$$\ beta = 2$ .
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$ - produce secuencias secundarias cuando $$$\ beta = 1$ .

Solo hay 3 posibles matrices secundarias para un número.
Si se aplica a una fórmula recursiva, entonces:

Función $$$n (\ gamma, \ alpha, \ beta)$ donde $$$\ gamma$ - cualquier número múltiplo de 3 forma un conjunto vacío ⨂.

$$

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

Función $$$n (\ lambda, \ alpha, \ beta)$ donde $$$\ lambda$ - cualquier número generado $$$\ gamma$ a las $$$\ beta = 2$ forma el conjunto de números K que pertenecen al conjunto de números naturales N.

$$

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

Función $$$n (P (\ lambda), \ alpha, \ beta)$ a las $$$\ beta = 1$ forma el conjunto de números L que pertenecen al conjunto de números naturales N.

$$

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

Obviamente, esto de alguna manera puede reducirse a una formulación más rigurosa y basada en evidencia.

En realidad, así es como se forman las secuencias en la hipótesis de Collatz.
Queda un detalle. Es necesario restaurar conjuntos completos a partir de pasos absolutos de los conjuntos que hemos obtenido.

Fórmula para Odd:

$$

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

Además de los impares, debe restaurar muchos pares. Para hacer esto, recuerde la fórmula:

$$

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

Solo queda correlacionar todos juntos:

$$

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

La versión final:

$$

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

Por lo tanto, cualquier k puede generar una secuencia.

¿Es cierto lo contrario que cualquiera de los números naturales definitivamente pertenece a cualquier secuencia de $$$n (k)$ ?

Si es así, entonces es completamente posible que Collatz tuviera razón.

Para el ejemplo final de implementación de la función 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 ]