161 FORMULAÇÕES ALTERNATIVAS PARA A CONJECTURA DE
COLLATZ
Antônio Carlos da Silva Filho
INTRODUÇÃO
A Conjectura de Collatz também é conhecida como “Problema 3n+1,
“Conjectura de Ulam” e “Problema de Siracusa”. Seu enunciado é:
“Dado um número natural, N, que segue uma determinada lei para a formação
de uma sequência, esta sequência terminaria sempre em 1”.
A lei em questão estabelece que:
(a) se N for par, o próximo termo
162 na sequência será
N/2 ;
(b) se N for ímpar, o próximo termo será igual à metade de
3N + 1.
Esta conjectura não foi provada até hoje. Encontra-se na literatura duas
versões das regras de iteração [1], uma em termos da função de Collatz (C), e outra
em termos da função 3n + 1 (T).
A função de Collatz é definida por:
C(n) = n/2
3n + 1
se n é par
se n é ímpar
A função 3n + 1 é definida por:
T(n) =n/2
(3n + 1)/2
A FUNÇÃO DE COLLATZ
se n é par
se n é ímpar
163 Neste trabalho foi utilizada somente a função de Collatz, ou seja, C(n).
Com estas considerações, a conjectura de Collatz pode ser enunciada como:
Dado qualquer número natural n, se o mesmo for iterado de acordo com a
função C(n), ou seja, se for calculado C(C(n)),C(C(C(n))), e assim por diante, sempre
chegará em 1.
Chama-se de órbita do número n à sequência de números gerada através
deste processo até chegar a 1.
Seguem alguns exemplos nas figuras :
Figura 1. Órbita do número 3, que tem 8 elementos.
164 Figura 2. Órbita do número 9, que tem 20 elementos.
Uma órbita interessante é a do 27, pois possui 112 elementos, sendo o maior
deles 9232, de onde é possível ver que não é necessário números grandes para se
obter órbitas extensas. A órbita do 27 é:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121,
364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263,
790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132,
566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619,
4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232,
4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184,
92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.
165 Figura 3. Órbita do número 27, que tem 112 elementos.
Será que há alguma relação entre um dado número e o número de elementos
em sua órbita. As figuras (4-6) a seguir ilustram a dificuldade de se extrair tal
relação, caso ela exista:
166 Figura 4. Número de elementos na órbita em função do número gerador,
desde n = 1 até n = 10.
Figura 5. Número de elementos na órbita em função do número gerador,
desde n = 1 até n = 1000.
167 Figura 6. Número de elementos na órbita em função do número gerador,
desde n = 1 até n = 1000. Neste gráfico os pontos sucessivos não estão unidos, o
que revela uma estrutura subjacente.
RESULTADOS
Propomos as seguintes formulações alternativas à Conjectura de Goldbach:
Formulação Alternativa (1):
“Dado qualquer número natural n, se o mesmo for iterado de acordo com a função
C(n), ou seja, se for calculado C(C(n)),C(C(C(n))), e assim por diante, sempre
chegará à sequência N = 2k, com k inteiro não negativo”
Justificativa: Todos os números da forma N = 2k, com k inteiro não negativo,
terminarão em 1, sob as regras acima, porque são formados pela multiplicação de 2
168 por ele mesmo k vezes. Assim, a cada divisão, ou o resultado é 1 ou é uma outra
potência de 2; se for uma outra potência de 2, repete-se o procedimento.
Formulação Alternativa (2):
“Dado qualquer número natural n, escrito na base 2 se o mesmo for iterado de
acordo com a função C(n), ou seja, se for calculado C(C(n)),C(C(C(n))), e assim por
diante, sempre chegará a algum elemento da sequência:
1
10
100
1000
10000
...
”
CONCLUSÃO
As
formulações
alternativas
apresentadas
acima
não
resolvem,
automaticamente, a Conjectura de Collatz. Mas podem representar um objetivo
diferente, embora equivalente, ao de se fazer o processo de iteração de Função de
Collatz terminar em 1. O objetivo passa a ser provar que as iterações acabam em
um dos membros da sequência 2k. Formulada na base 2, passa a ser provar que as
iterações inevitavelmente produzirão, em algum instante, um número com o dígito 1
na primeira posição e somente dígitos zeros em todas as outras posições.
169 REFERÊNCIAS
AKIN, E. (2004), Why is the 3x + 1 Problem Hard?, In: Chapel Hill Ergodic Theory
Workshops (I. Assani, Ed.), Contemp. Math. 356, Amer. Math. Soc. 2004, pp. 1–20.
ALVES, J. F., Graca, M. M., M. E., Sousa Dias, M. E e Ramos, J. S. , A linear algebra
approach to the conjecture of Collatz, Lin. Alg. Appl. 394 (2005), pp. 277–289.
ANDALORO, P., On total stopping times under 3X + 1 iteration, Fibonacci Quarterly 38
(2000), pp. 73–78.
ANDALORO, P., The 3X +1 problem and directed graphs, Fibonacci Quarterly 40 (2002), pp.
43–54.
ANDREI, S., KUDLEK, M. e NICULESCU, R. S., Some results on the Collatz problem, Acta
Informatica 37 (2000), pp. 145–160.