Conjectura de Collatz

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde setembro de 2015). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
A sequência de Collatz começando em 127.

A conjectura de Collatz é devida ao matemático alemão Lothar Collatz e também é conhecida como problema 3x + 1. A conjectura apresenta uma regra dizendo que, qualquer número natural, quando aplicado a esta conjectura, no fim dará sempre 1. A conjectura aplica-se a qualquer número natural, 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. Interrompendo o procedimento no número 1 a pergunta que se faz é: qualquer que seja o número natural inicial a sequência findará em 1?

O matemático alemão Gerhard Opfer publicou em maio de 2011 um artigo que alegava provar a conjectura, causando alvoroço na comunidade matemática.[1] . 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

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 for par, dividi-lo em dois.
  • Se o número for ímpar, triplicar-lo e adicionar uma.

Em notação aritmética, a função é definida tal que:

Implementações de computador[editar | editar código-fonte]

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 (x == 1){
		return;
	} else if (x % 2 == 0){		
		collatz(x/2);
	} else{
		collatz(3*x+1);
	}
}

Referências

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.