Usuário:Alberto79/Teste/Conjectura de Collatz

Conjectura de Collatz - Um Estudo

Este estudo tem por objetivo verificar a Conjectura de Collatz, utilizando como ferramenta de trabalho a planilha eletrônica Microsoft Excel.

Ao longo das décadas que se seguiram à proposição de Lothar Collatz, foram publicados trabalhos e artigos sobre o tema, mostrando simplicidade e complexidade, beleza (fractais), comportamento caótico e misterioso seguindo para 4, 2 e 1. Agora veremos que, quando dispostos adequadamente, os números apresentam harmonia e previsibilidade.

Considerações Iniciais

a - Pretende-se provar que a Conjectura de Collatz é válida para todo número natural . Há que se fazer restrição de domínio pois, caso contrário, de imediato aparece um contraexemplo: 0. O número natural 0, aplicando-se a proposição para números pares, entra em loop, sem chegar a 1, pois o resultado será sempre 0. Portanto, o domínio deste estudo será N*.

b - As proposições de Collatz têm aplicações distintas, sendo f(x) = x/2 aplicada aos números pares e f(x) = 3x+1 aplicada aos números ímpares, com os seguintes objetivos:

- f(x) = 3x+1 → tem por objetivo produzir um número par à partir de um número ímpar;

- f(x) = x/2 → tem por objetivo verificar se o número par pode, através da aplicação sucessiva da Conjectura de Collatz, chegar a 1.

Números Granizo

São chamados números granizo aqueles que fazem ‘desabar’ a ordem de grandeza da sequência numérica da aplicação das proposições de Collatz, como o granizo desaba das nuvens. Por quê? Basta analisar as proposições para vir a resposta: f(x) = 3x+1, aplicada aos ímpares, faz a sequência subir e gera sempre um número par e, portanto, não é aplicada sucessivamente; f(x) = x/2, no entanto, pode gerar números pares ou ímpares, de forma decrescente, e, quando iniciada por um número que tem como fatores primos uma sequência de 2, decrescerá pela metade tantas vezes quantas forem estes fatores, até chegar a um número ímpar, que reiniciará a busca noutros patamares, ou encerrará em 1.

Conjectura de Collatz e o infinito de sua aplicação

Todo número natural que, quando decomposto em fatores primos, apresenta apenas o número primo 2, só permitirá a aplicação de f(x) = x/2 até finalizar em 1. A série de números produzido pode ser representada assim:

S_n (2ⁿ; 2^n-1; 2^n-2; ... ; 2^n-(n-2); 2^n-(n-1); 2^n-n)

Este número precisará de n passos para chegar a 1.

Ferramentas da aquisição de dados

Os dados da aplicação da Conjectura de Collatz foram obtidos com Microsoft Excel 2010, com Sistema Operacional Windows 8.1, com hardware Intel Core I7, 8GB RAM e HD 1TB.

Inicialmente a aplicação das proposições de Collatz foram obtidas de forma manual, o que foi de grande valia na observação da repetibilidade dos números.

Em seguida, objetivando a ampliação do Universo pesquisado, o processo foi automatizado com o uso da função SE do Excel:

=SE(A2/2-INT(A2/2)=0;A2/2;A2*3+1)

Limitações do Microsoft Excel

Dentro do Universo pesquisado, a precisão dos cálculos, em função da capacidade interna de armazenamento de informações, demonstrou ser satisfatória. O Excel consegue armazenar e apresentar números com 15 dígitos. No entanto, em sua memória de cálculo, a quantidade de dígitos supera a apresentada, tendo sido possível verificar a precisão para 17 dígitos, ou seja, na casa do quatrilhão.

Sequências onipresentes

As sequências abaixo são onipresentes nos passos finais dos números investigados (Números Naturais até 4 milhões e proximidade 1 quatrilhão, variando apenas o número de passos para chegar a 1), e acrescida a S_n, já apresentada:

S₃ (10; 5; 16; 8; 4; 2; 1)

S₁₃ (40; 20; 10; 5; 16; 8; 4; 2; 1)

S₅₃ (160; 80; 40; 20; 10; 5; 16; 8; 4; 2; 1)

Valem algumas observações sobre as sequências S₃, S₁₃ e S₅₃:

1 – As sequências são singulares. Quando acontece como em S₈₀ e S₁₃ , que têm os mesmos elementos, a singularidade reside na forma com que se inicia a sequência, uma por f(x) = x/2; outra por f(x) = 3x+1. Esta será a diferença entre diversas sequências e, alguns números, têm a particularidade de não serem ‘atingidos’ por f(x) = 3x+1, como na sequência S_n onde, alternadamente, um elemento é ‘atingido’ e outro não. Isto acontece porque f(x) = 3x+1 não produz números pares múltiplos de 6.

Números ímpares	f(x) = 3x+1
1	4
3	10
5	16
7	22
9	28

Tabela 1: Entrada natural ímpar gerando uma Progressão Aritmética de razão 6.

2 – S₅₃ contém S₁₃ e S₃.

Abaixo uma tabela com os 15 primeiros Número de Mersenne, onde estas sequências estão presentes:

Mersenne	sequência final - 20 últimos termos
1																		4	2	1
3														10	5	16	8	4	2	1
7					22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
15				46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
31	61	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
63	61	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
127	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
255	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
511	56	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
1023	56	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
2047	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
4095	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
8191	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
16383	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
32767	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1

Tabela 2: Números de Mersenne – Vinte últimos termos.

Dispondo os números

Na aplicação da Conjectura de Collatz, vemos as sequências seguirem o seguinte padrão:

a - Parte-se de um número par ou produz-se um número par pela aplicação de f(x) = 3x+1;

b - Expurga-se os fatores primos iguais a 2 pela aplicação de f(x) = x/2 até chegar a 1 ou a outro número ímpar.

Sendo assim, as sequências de todos os números são compostas da mesma forma. Na tabela 2, analisando os vinte últimos termos da sequência do Mersenne 31, temos o número ímpar 61 que gera o número par 184; expurgando os fatores primos iguais a 2 de 184, chegamos a 23; do número 23 chega-se ao 70, com um único fator primo igual a 2, levando ao 106, que também tem um único 2 como fator primo, levando à S₅₃. Já com o Mersenne 32.767, partimos do número par 58 e finalizamos com S₁₃. Seguindo este princípio, podemos montar a seguinte tabela:

Colunas →	A	B	C	D	E	F	G	H	I	J
Linhas ↓	Ímpar	f(x) = 3x+1	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2
1	1	4	2	1
2	3	10	5
3	5	16	8	4	2	1
4	7	22	11
5	9	28	14	7
6	11	34	17
7	13	40	20	10	5
8	15	46	23
9	17	52	26	13
10	19	58	29
11	21	64	32	16	8	4	2	1
12	23	70	35
13	25	76	38	19
14	27	82	41
15	29	88	44	22	11
16	31	94	47
17	33	100	50	25
18	35	106	53
19	37	112	56	28	14	7
20	39	118	59
21	41	124	62	31
22	43	130	65
23	45	136	68	34	17
24	47	142	71
25	49	148	74	37
26	51	154	77
27	53	160	80	40	20	10	5
28	55	166	83
29	57	172	86	43
30	59	178	89
31	61	184	92	46	23
32	63	190	95
33	65	196	98	49
34	67	202	101
35	69	208	104	52	26	13
36	71	214	107
37	73	220	110	55
38	75	226	113
39	77	232	116	58	29
40	79	238	119
41	81	244	122	61
43	83	250	125
44	85	256	128	64	32	16	8	4	2	1
45	87	262	131
46	89	268	134	67
47	91	274	137
48	93	280	140	70	35
49	95	286	143
50	97	292	146	73
51	99	298	149
52	101	304	152	76	38	19
53	103	310	155
54	105	316	158	79
55	107	322	161
56	109	328	164	82	41
57	111	334	167
58	113	340	170	85
59	115	346	173
60	117	352	176	88	44	22	11
61	119	358	179
62	121	364	182	91
63	123	370	185
64	125	376	188	94	47
65	127	382	191
66	129	388	194	97
67	131	394	197
68	133	400	200	100	50	25
69	135	406	203
70	137	412	206	103
71	139	418	209
72	141	424	212	106	53
73	143	430	215
74	145	436	218	109
75	147	442	221
76	149	448	224	112	56	28	14	7
77	151	454	227
78	153	460	230	115
79	155	466	233
80	157	472	236	118	59
81	159	478	239
82	161	484	242	121
83	163	490	245
84	165	496	248	124	62	31
85	167	502	251
86	169	508	254	127
87	171	514	257
88	173	520	260	130	65
89	175	526	263
90	177	532	266	133
91	179	538	269
92	181	544	272	136	68	34	17
93	183	550	275
94	185	556	278	139
95	187	562	281
96	189	568	284	142	71
97	191	574	287
98	193	580	290	145
99	195	586	293
100	197	592	296	148	74	37

Tabela 3: Entrada ímpar → f(x) = 3x+1 → f(x) = x/2 até número ímpar.

Nesta tabela 3 vemos que toda coluna é composta por uma Progressão aritmética, tendo a coluna A, razão 2; coluna B, razão 6; da coluna C em diante, razão 3.

Outra característica, que aparece da coluna C em diante, é a previsibilidade do aparecimento de elementos pois, entre eles, há um espaçamento constante. Na coluna C há 2⁰ passos entre os elementos; na coluna D, 2¹ passos; na coluna E, 2² passos. E assim segue, de modo que a enésima coluna à direita da Coluna C terá um espaçamento entre elementos de 2ⁿ passos e a diferença entre eles será 3. Existe, também, um ciclo de 2⁶ linhas.

Vejamos como se comportam os múltiplos de 6, em tabela semelhante:

Colunas →	A	B	C	D	E	F	G
Linhas ↓	Múltiplo de 6	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2	f(x) = x/2
2⁰	6	3
2¹	12	6	3
3	18	9
2²	24	12	6	3
5	30	15
6	36	18	9
7	42	21
2³	48	24	12	6	3
9	54	27
10	60	30	15
11	66	33
12	72	36	18	9
13	78	39
14	84	42	21
15	90	45
2⁴	96	48	24	12	6	3
17	102	51
18	108	54	27
19	114	57
20	120	60	30	15
21	126	63
22	132	66	33
23	138	69
24	144	72	36	18	9
25	150	75
26	156	78	39
27	162	81
28	168	84	42	21
29	174	87
30	180	90	45
31	186	93
2⁵	192	96	48	24	12	6	3

Tabela 4: Entrada múltiplo de 6 → f(x) = x/2 até número ímpar.

Esta tabela 4 também é composta por Progressões aritméticas, tendo a coluna A, razão 6; da coluna B em diante, razão 3.

Também existe a previsibilidade do aparecimento de elementos pois, entre eles, há um espaçamento constante. Na coluna B há 2⁰ passos entre os elementos; na coluna C, 2¹ passos; na coluna D, 2² passos. E assim segue, de modo que a enésima coluna à direita da Coluna B terá um espaçamento entre elementos de 2ⁿ passos e a diferença entre eles será 3.

Na numeração das linhas desta tabela 4, utilizou-se potências de base 2 para ressaltar a previsibilidade do aparecimento do número 3 da coluna B em diante. É possível afirmar que a enésima coluna à direita de B terá na linha 2ⁿ o número 3.

Assim vê-se que o comportamento aparentemente caótico, dá lugar a harmonia, simetria e previsibilidade.

Organizando Conjuntos

Consideremos as colunas das tabelas 3 e 4 como base para a formação dos seguintes conjuntos:

K = elementos da coluna A da tabela 3, ou seja, números Naturais ímpares;

W = elementos da coluna B da tabela 3, ou seja, números Naturais pares e ímpares, dispostos em P.A. de razão 6 e elemento inicial 4;

X = elementos da coluna C da tabela 3, ou seja, números Naturais pares e ímpares, dispostos em P.A. de razão 3 e elemento inicial 2;

Y = elementos da coluna A da tabela 4, ou seja, números Naturais múltiplos de 6.

Todos estes conjuntos são infinitos, estão contidos no Universo dos Números Naturais e a união deles tem como resultado N*.

Conclusão

Tendo como Universo os Números Naturais, a Conjuntura de Collatz não se confirma pois não contempla o zero.

No entanto, se fizermos restrição de domínio, excluindo o zero do Universo trabalhado, passando de N para N*, a Conjectura se confirma.