🏷️ 🙈 🙍🏾 Sobre a formação de sequências na hipótese de Collatz (3n + 1) 😕 🔴 🤵🏼

Sinto-me atraído por tarefas como o problema de Collatz. Eles são fáceis de formular e treinar perfeitamente, especialmente o pensamento algorítmico, o que é muito útil para o programador.

A tarefa é formulada de maneira bastante simples:

Tome qualquer número natural n. Se for par, divida-o por 2 e, se for ímpar, multiplique por 3 e adicione 1 (obtemos 3n + 1). Realizamos as mesmas ações no número resultante, e assim por diante.

A hipótese de Collatz é de que, independentemente do número inicial n que tomarmos, mais cedo ou mais tarde obteremos um.

Algoritmicamente, fica assim:

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

Por exemplo, considere n = 5. É ímpar, o que significa que realizamos a ação no ímpar, ou seja, 3n + 1 => 16. 16 é par, significa que realizamos a ação no par, ou seja, n / 2 => 8 => 4 => 2 => 1.
A sequência formada em n = 5: 16, 8, 4, 2, 1.

Peço que você me perdoe pela minha matemática, deixe-me saber se eu cometer algum erro em algum lugar.

Vamos destacar o número total de informações na unidade e o número real de informações na unidade. Indique estas etapas.

Considere a sequência para n = 7:

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

Existem 16 etapas no total, e as verdadeiras etapas que são realmente lançadas em outro conjunto de números são 5:

7, 11, 17, 13, 5.

O verdadeiro passo Sa (n) é o número de operações 3n + 1 no número necessário para alcançar a unidade.

A ideia é claramente demonstrada pelo exemplo de uma tabela:

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

Nessa tabela, a ordem, seu próprio padrão, já está visível.
Como você pode ver, o poder de dois nunca se tornará estranho, então tudo se resume a uma divisão simples.
Uma sequência de Sa (0) é formada por apenas 1 fórmula.

P (0, k) = 2 * 2^{k} .

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

Não é preciso dar passos verdadeiros: pela simples divisão tudo será reduzido à unidade.
Sabendo disso, você pode soltar da tabela todos os números que são múltiplos de dois.

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

Agora é mais difícil entender o padrão, mas existe um. O mais interessante agora é a formação de sequências. Não apenas assim, o próximo dígito após 5 é 21 e depois é 85.
Na verdade, Sa (1) é a sequência A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). É formado pela fórmula:

P (k) = 4^{k} - 1 a c i m a d e 3 .

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

A mesma sequência pode ser descrita por uma fórmula recursiva:

P (k) = 4 k_{0} + 1, c o m k_{0} = 1.

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

P (1) = 4 * 1 + 1 = 5;

$P (1) = 4 * 1 + 1 = 5;$

P (5) = 4 * 5 + 1 = 21;

$P (5) = 4 * 5 + 1 = 21;$

P (21) = 4 * 21 + 1 = 85;

$P (21) = 4 * 21 + 1 = 85;$
E assim por diante ...

Uma série do primeiro passo é construída, embora possa continuar indefinidamente. Vamos para o passo dois. A fórmula de transição para a etapa 2 pode ser expressa a partir de uma fórmula ímpar.
Sabendo que vamos compartilhar o resultado

3 n + 1

$3n + 1$ várias vezes, pode ser escrito como

2^{2 a l p h a}

$2 ^ {2 \ alpha}$ onde

a l p h a

$\ alpha$ - número de divisões.

P (k) = 3 n + 1 o v e r 2^{2 a l p h a}; 2^{2 a l p h a} P (k) = 3 n + 1; 3 n = 2^{2 a l p h a} P (k) - 1;

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

A fórmula final assume a forma:

n (P (k), a l p h a) = 2^{2 a l p h a} P (k) - 1 o v e r 3;

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

Também introduzimos um ajuste para

b e t a

$\ beta$ como

2^{2 a l p h a + b e t a}

$2 ^ {2 \ alpha + \ beta}$ para que a opção de dividir o número não um múltiplo de 3 por 3 aconteça.

n (P (k), a l p h a, b e t a) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3;

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

Vamos verificar a fórmula, já que o alfa é desconhecido, verifique 5 alfa consecutivos:

n (5, a l p h a, b e t a) = 2^{2 a l p h a + b e t a} * 5 - 1 o v e r 3;

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

n (5, 0, 1) = (2^{0 + 1} * 5 - 1) / 3 = 3.

$n (5,0,1) = (2 ^ {0 + 1} * 5-1) /3=3.$

n (5, 1, 1) = (2^{2 + 1} * 5 - 1) / 3 = 13.

$n (5,1,1) = (2 ^ {2 + 1} * 5-1) /3=13.$

n (5, 2, 1) = (2^{5} * 5 - 1) / 3 = 53.

$n (5,2,1) = (2 ^ 5 * 5-1) /3=53.$

n (5, 3, 1) = (2^{7} * 5 - 1) / 3 = 213.

$n (5,3,1) = (2 ^ 7 * 5-1) /3=213.$

n (5, 4, 1) = (2^{9} * 5 - 1) / 3 = 853.

$n (5,4,1) = (2 ^ 9 * 5-1) /3=853.$

Assim, a sequência do segundo passo começa a se formar. No entanto, pode-se notar que 113 não está em sequência, é importante lembrar que a fórmula foi calculada a partir de 5 .

n = 113 de fato:

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

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

Para resumir:

Lote de $Sa (n + 1)$ gerado por função $n (P (k), \ alpha, \ beta)$ de cada elemento do conjunto de $Sa (n)$ .

Então, sabendo disso, você ainda pode reduzir a tabela removendo todos os múltiplos de alfa.

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

Para deixar claro, aqui está um exemplo de como os elementos de um conjunto de

S a (2)

$Sa (2)$ gerar elementos do conjunto de

S a (3)

$Sa (3)$ para alfa de 0 a 4.

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

Combinando esses conjuntos, obtemos o conjunto de Sa (3):

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

Além disso, remover o grau

a l p h a > 0

$\ alpha> 0$ nós obtemos:

17, 75, 151 ...

Ou seja, tudo se resume a:

n (P (k), b e t a) = 2^{} b e t a P (k) - 1 o v e r 3;

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

Por que em algum lugar

$\ beta = 2$ e em algum lugar

$\ beta = 1$ ?

Voltar à sequência A002450. Existe uma dependência interessante:

P (m) = (4^{3} m - 1) / 3

$P (m) = (4 ^ 3m-1) / 3$ - não produz seqüências filho.

P (m) = (4^{3 m + 1} - 1) / 3

$P (m) = (4 ^ {3m + 1} - 1) / 3$ - produz seqüências filho quando

b e t a = 2

$\ beta = 2$ .

P (m) = (4^{3 m + 2} - 1) / 3

$P (m) = (4 ^ {3m + 2} - 1) / 3$ - produz seqüências filho quando

b e t a = 1

$\ beta = 1$ .

Existem apenas três matrizes filho em potencial para um número.
Se aplicado a uma fórmula recursiva, então:

Função $n (\ gama, \ alpha, \ beta)$ onde $\ gama$ - qualquer número múltiplo de 3 forma um conjunto vazio ⨂.
$A (n (g a m a), a l p h a, b e t a) = ⨂ .$
$A (n (\ gama), \ alpha, \ beta) = ⨂.$

Função $n (\ lambda, \ alpha, \ beta)$ onde $\ lambda$ - qualquer número gerado $\ gama$ às $\ beta = 2$ forma o conjunto de números K pertencentes ao conjunto de números naturais N.
$K (n (P (g a m a), a l p h a, 2)) \subseteq N .$
$K (n (P (\ gama), \ alpha, 2)) ⊆ N.$

Função $n (P (\ lambda), \ alpha, \ beta)$ às $\ beta = 1$ forma o conjunto de números L pertencentes ao conjunto de números naturais N.
$L (n (P (l a m b d a), a l p h a, 1)) \subseteq N .$
$L (n (P (\ lambda), \ alpha, 1)) ⊆ N.$

Obviamente, isso pode ser reduzido de alguma forma a uma formulação mais rigorosa e baseada em evidências.

Na verdade, é assim que as seqüências são formadas na hipótese de Collatz.
Ainda há um detalhe. É necessário restaurar conjuntos completos de etapas absolutas dos conjuntos que obtivemos.

Fórmula para Ímpar:

n (P (k), a l p h a, b e t a) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3;

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

Além dos estranhos, você precisa restaurar muitos pares. Para fazer isso, lembre-se da fórmula:

P (0, k) = 2 * 2^{k} .

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

Resta apenas correlacionar todos juntos:

n (P (k), a l p h a, b e t a, e p s i l o n) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3 * 2^{} e p s i l o n .

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

A versão final:

n (k, a l p h a, b e t a, e p s i l o n) = 2^{} e p s i l o n 2^{2 a l p h a + b e t a} (4 k + 1) - 1 o v e r 3;

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

Assim, qualquer k pode gerar uma sequência.

É o inverso verdade que qualquer um dos números naturais definitivamente pertence a qualquer sequência de $n (k)$ ?

Nesse caso, é perfeitamente possível que Collatz estivesse certo.

Para o exemplo final da implementação da função 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 ]

Sobre a formação de sequências na hipótese de Collatz (3n + 1)

More articles: