Saltar para o conteúdo

Usuário:Alberto79/Teste/Conjectura de Collatz

Origem: Wikipédia, a enciclopédia livre.

Conjectura de Collatz - Um Estudo

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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

  1. Número natural
  2. Números pares e ímpares

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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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:

Sn (2n; 2n-1; 2n-2; ... ; 2n-(n-2); 2n-(n-1); 2n-n)

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

Ferramentas da aquisição de dados

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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 Sn, já apresentada:

S3 (10; 5; 16; 8; 4; 2; 1)

S13 (40; 20; 10; 5; 16; 8; 4; 2; 1)

S53 (160; 80; 40; 20; 10; 5; 16; 8; 4; 2; 1)

Valem algumas observações sobre as sequências S3, S13 e S53:

1 – As sequências são singulares. Quando acontece como em S80 e S13 , 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 Sn 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 – S53 contém S13 e S3.

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

[editar | editar código-fonte]

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 à S53. Já com o Mersenne 32.767, partimos do número par 58 e finalizamos com S13. 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á 20 passos entre os elementos; na coluna D, 21 passos; na coluna E, 22 passos. E assim segue, de modo que a enésima coluna à direita da Coluna C terá um espaçamento entre elementos de 2n passos e a diferença entre eles será 3. Existe, também, um ciclo de 26 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
20 6 3
21 12 6 3
3 18 9
22 24 12 6 3
5 30 15
6 36 18 9
7 42 21
23 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
24 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
25 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á 20 passos entre os elementos; na coluna C, 21 passos; na coluna D, 22 passos. E assim segue, de modo que a enésima coluna à direita da Coluna B terá um espaçamento entre elementos de 2n 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 2n o número 3.

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

Organizando Conjuntos

[editar | editar código-fonte]

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

[editar | editar código-fonte]

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.

Obtida de "https://pt.wikipedia.org/w/index.php?title=Usuário:Alberto79/Teste/Conjectura_de_Collatz&oldid=50581221"