Conjectura de Collatz

A sequência de Collatz começando em 127. A sequência sobe até o máximo 4372 antes de alcançar o 4, 2, 1.

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ô-lo, em 1937.

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.

Esta conjectura aplica-se a qualquer número natural não nulo, 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 não nulo, 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".

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 (2ⁿ) chegará a 1 em n passos, o que demonstra ser infinita a abrangência da Conjectura de Collatz.

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. 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 sequência de Collatz começando em 77031. Esta é a maior sequência obtida para x menor que 100000.

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

O motivo fica claro ao observar o resultado da aplicação de 3x+1 e x/2. A conjectura para números ímpares produzirá um número par; a conjectura para números pares poderá produzir muitos outros números pares, caso em que chamamos Números de Granizo, poucos números pares, ou um único número ímpar.

Enunciado do problema

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 $C$ é definida tal que:

$C(x)={\begin{cases}3x+1&{\text{if }}x\equiv 1{\pmod {2}}\\x/2&{\text{if }}x\equiv 0{\pmod {2}}\end{cases}}$

Implementações de computador

Na linguagem C#:

using static System.Console;

public class Program
{
    public void Collatz(int x)
    {
        WriteLine(x);
        if (x == 1) return;
        Collatz(x % 2 == 0 ? x / 2 : 3 * x + 1);
    }
}

Na linguagem Python:

def collatz(x):
    print(x)
    if 1 == x:
        return
    elif x % 2 == 0:
        collatz(x / 2)
    else:
        collatz(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);
	}
}

No Microsoft Excel:

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

O argumento “A2/2-INT(A2/2)=0” verifica se o número contido na célula “A2” é par através da diferença entre a divisão por 2 e o inteiro desta mesma divisão pois, quando ímpar, o resto da divisão será diferente de 0. Quando verdadeiro, ou seja, “A2” é par, aplica-se a Conjectura para números pares f(x) = x/2 — “A2/2”; quando falso, aplica-se a Conjectura para números ímpares f(x) = 3x+1 — “A2*3+1”. Este processo não tem dispositivo de parada em 1. Daí que, na planilha do Microsoft Excel, após a sequência 16,8,4,2,1, há a repetição em loop do segmento 4, 2, 1, enquanto existir a função SE inserida nas células.

Importância

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

Ver Também

• Número de Mersenne
• Produtos Notáveis