Conjectura de Collatz
 |
A conjectura de Collatz é uma conjectura matemática que recebeu este nome em referência ao matemático alemão Lothar Collatz, que foi o primeiro a propô-la, em 1937.[1]
Além desse nome, este problema também é conhecido por Problema 3x + 1, Conjectura de Ulam (pelo matemático polonês-americano Stanisław Marcin Ulam), Problema de Kakutani (pelo matemático nipo-americano Shizuo Kakutani), Conjectura de Thwaites (pelo acadêmico britânico Bryan Thwaites), Algoritmo de Hasse (pelo matemático alemão Helmut Hasse) ou Problema de Siracusa.[1]
Esta conjectura aplica-se a qualquer número natural inteiro, e diz-nos para, se este número for par, o dividir por 2 (/2), e se for impar, para multiplicar por 3 e adicionar 1 (*3+1). Desta forma, por exemplo, se a sequência iniciar com o número 5 ter-se-á: 5; 16; 8; 4; 2; 1. A conjectura apresenta uma regra dizendo que, qualquer número natural inteiro[1], quando aplicado a esta regra, eventualmente sempre chegará a 4, que se converte em 2 e termina em 1. Essa sequência em questão também pode ser chamada de Números de Granizo ou Números Maravilhosos. A explicação destes últimos nomes está em "como o granizo nas nuvens antes de cair, os números saltam de um lugar ao outro antes de chegar ao 4, 2, 1".[1]
A explicação para estes saltos, quando ocorrem Números de Granizo, está na quantidade de fatores primos iguais a 2 quando decompomos este número, o que determina quantas vezes, de forma sucessiva, será aplicada a conjectura para números pares f(x)=x/2. Por exemplo, a enésima potência de 2 (2n) chegará a 1 em n passos, o que demonstra ser infinita a abrangência da Conjectura de Collatz. Vale ressaltar que as potências pares de 2 são acessadas por 3x+1, por exemplo, 3x5+1=16 e 3x21+1=64.
O matemático alemão Gerhard Opfer publicou em maio de 2011 um artigo com o teorema que supostamente provava esta conjectura, causando alvoroço na comunidade matemática.[2]. Em 17 de julho de 2011, entretanto, o autor publicou uma nota, na última página de seu artigo, onde reconhecia que uma de suas afirmações estava incompleta, o que não garantia a ele a prova do problema.
A Tabela a seguir descreve a porcentagem de números pares e ímpares para a quantidade de números dados. Em geral, ocorre o dobro de números pares em relação aos ímpares conforme mostrado nessa tabela.
| Quantidade x | 10 | 100 | 1000 | 10000 | 100000 |
|---|---|---|---|---|---|
| %Par | 5,00 | 21,37 | 39,88 | 56,76 | 71,88 |
| %Ímpar | 2,70 | 11,05 | 20,65 | 29,20 | 36,64 |
Enunciado do problema[editar | editar código-fonte]
Considere a seguinte operação em um número inteiro positivo arbitrário qual que:
- Se o número é par, divida-o por 2;
- Se é ímpar, multiplique-o por 3 e some 1
Em notação aritmética, a função é definida tal que:
Ou equivalente:
Onde a presença das funções fatorial, duplo fatorial e a função gama é observada.
Implementações de computador[editar | editar código-fonte]
Na linguagem Python:
def collatz(x): while x > 1: if x % 2 == 0: x /= 2 else: x = 3*x+1 Na linguagem Java:
static void collatz(int x) { System.out.println(x); if (x>1) { collatz( (x%2==0) ? x/2 : (3*x+1) ); } } Na linguagem C:
void collatz(int x) { printf("%d ", x); if (1 == x) return; else if (x % 2 == 0) collatz(x/2); else collatz(3*x+1); } Na linguagem PHP:
function collatz($x){ if($x == 1){ return $x; }else if($x % 2 == 0){ $result = $x / 2; return collatz($result); }else{ $result = ($x * 3) + 1; return collatz($result); } } Na linguagem Haskell:
collatz :: (Integral a) => a -> [a] collatz 1 = [1] collatz n | even n = n:collatz (n `div` 2) | odd n = n:collatz (n*3 + 1) Na linguagem Ruby:
def collatz(n) puts n return if n == 1 return collatz(n*3 + 1) if n.odd? return collatz(n/2) end Importância[editar | editar código-fonte]
Segundo o matemático Greg Muller, a importância desta conjectura está em que "os matemáticos suspeitam que solucionar a conjectura de Collatz abrirá novos horizontes e desenvolverá novas e importantes técnicas na teoria dos números".[1] Já Derek Jennings comenta que "outra razão é que, por ser fácil de apresentar e entender, tem potencial de atrair jovens para a matemática. Eu mesmo soube de sua existência no ensino médio e não resisti a seu encanto".[1]
