Conjectura de Collatz ou problema 3x + 1

O problema 3x + 1 está por resolver. Consiste no seguinte:

Considera-se um número inteiro positivo superior a 1. Se for par divide-se por dois, se for ímpar multiplica-se por três e soma-se-lhe um. Ao novo número assim obtido faz-se o mesmo, e assim sucessivamente, até que se chegue a 1.

Conjectura-se que qualquer que seja o número inicial, a sequência gerada acaba sempre no número um. 

Exemplo: 5, 16, 8, 4, 2, 1

Cálculo:

    5×3+1= 16,     16÷2= 8,     8÷2= 4,     4÷2= 2,     2÷2= 1

Outro exemplo (o do gráfico em cima): 27, 82, 41, 124, …, 3077, 9232, 4616, …, 46, 23, 70, …, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Cálculo:
    27×3+1= 82,     82÷2= 41
    41×3+1= 124,     124÷2= 62,     62÷2= 31
    31×3+1= 94,     94÷2= 47
    47×3+1= 142,     142÷2= 71
    71×3+1= 214,     214÷2= 107
    107×3+1= 322,     322÷2= 161
    161×3+1= 484,    484÷2= 242,    242÷2= 121,

    121×3+1= 364,    364÷2= 182,    182÷2= 91
    91×3+1= 274,    274÷2= 137
    137×3+1= 412,    412÷2= 206,    206÷2= 103
    103×3+1= 310,    310÷2= 155
    155×3+1= 466,    466÷2= 233
    233×3+1= 700,    700÷2= 350,    350÷2= 175
    175×3+1= 526,    526÷2= 263,

    263×3+1= 790,    790÷2= 395
    395×3+1= 1186,    1186÷2= 593,

    593×3+1= 1780,    1780÷2= 890,    890÷2= 445
    445×3+1= 1336,    1336÷2= 668,    668÷2= 334,    334÷2= 167
    167×3+1= 502,    502÷2= 251
    251×3+1= 754,    754÷2= 377
    377×3+1= 1132,    1132÷2= 566,    566÷2= 283
    283×3+1= 850,    850÷2= 425,

    425×3+1= 1276,    1276÷2= 638,    638÷2= 319
    319×3+1= 958,    958÷2= 479
    479×3+1= 1438,    1438÷2= 719
    719×3+1= 2158,    2158÷2= 1079
    1079×3+1= 3238,    3238÷2= 1619
    1619×3+1= 4858,    4858÷2= 2429
    2429×3+1= 7288,    7288÷2= 3644,    3644÷2= 1822,    1822÷2= 911
    911×3+1= 2734,    2734÷2= 1367
    1367×3+1= 4102,    4102÷2= 2051, 

    2051×3+1= 6154,    6154÷2= 3077, 

    3077×3+1= 9232,     9232÷2= 4616,    4616÷2= 2308,     2308÷2= 1154,    1154÷2= 577
    577×3+1= 1732,    1732÷2= 866,    866÷2= 433
    433×3+1= 1300,    1300÷2= 650,    650÷2= 325
    325×3+1= 976,    976÷2= 488,    488÷2= 244,    244÷2= 122,     122÷2= 61,

    61×3+1= 184,    184÷2= 92,    92÷2= 46,    46÷2= 23
    23×3+1= 70,    70÷2= 35
    35×3+1= 106,    106÷2= 53
    53×3+1= 160,    160÷2= 80,    80÷2= 40,    40÷2= 20,    20÷2= 10,    10÷2= 5
    5×3+1= 16,    16÷2= 8,    8÷2= 4,    4÷2= 2,    2÷2= 1

Note que a seguir a um número x ímpar o número 3x+1 é sempre par!

Quando se testa sistematicamente em computador esta sequência, basta escrever o número na forma

km+r

e parar quando se obtiver um número inferior ao inicial, desde que antes se tenham testados todos os números para k menor ou igual ao que está a ser testado, o que poupa tempo de cálculo.

Exemplos:

 

m=4

4k\rightarrow \left( 4k\right) /2=\allowbreak 2k<4k

\qquad  —

4k+1\rightarrow 3\left( 4k+1\right) +1=\allowbreak 12k+4\rightarrow \left( 12k+4\right) /2=\allowbreak 6k+2

\rightarrow \left( 6k+2\right) /2=\allowbreak 3k+1<4k+1

\qquad  —

4k+2\rightarrow \left( 4k+2\right) /2=\allowbreak 2k+1<4k+2

\qquad  —

4k+3\rightarrow 3\left( 4k+3\right) +1=\allowbreak 12k+10\rightarrow \left( 12k+10\right) /2=\allowbreak 6k+5

\rightarrow 3\left( 6k+5\right) +1=\allowbreak 18k+16\rightarrow \left( 18k+16\right) /2=\allowbreak 9k+8

\bigskip

\begin{array}{cc} 4k & 2k \\ 4k+1 & 3k+1 \\ 4k+2 & 2k+1 \\ 4k+3 & \end{array}

\bigskip

Só se testam \dfrac{1}{4} dos casos, os da forma 4k+3

\begin{array}{cc}4k+3 &(\text{usa-se}\qquad 9k+8)\end{array}

\bigskip

m=8

\begin{array}{cc}8k&4k\\8k+1&6k+1\\8k+2&4k+1\\8k+3&\\8k+4 & 4k+2\\8k+5&6k+4\\ 8k+6&4k+3\\8k+7&\end{array}

\bigskip

Só se testam  \dfrac{2}{8}=\dfrac{1}{4} dos casos, os da forma 8k+3 e 8k+7

\begin{array}{cc}8k+3&(\text{usa-se}\qquad 9k+4)\\8k+7&(\text{usa-se}\qquad 27k+26)\end{array}

\bigskip

m=16

\begin{array}{cc}16k&8k\\16k+1&12k+1\\16k+2&8k+1\\16k+3&9k+2\\16k+4&8k+2\\16k+5&12k+4\\16k+6&8k+3\\16k+7&\\16k+8&8k+4\\16k+9&12k+7\\16k+10&8k+5\\16k+11&\\ 16k+12&8k+6\\ 16k+13&12k+10\\ 16k+14&8k+7\\16k+15&\end{array}

\bigskip

Só se testam \dfrac{3}{16}<\dfrac{1}{4} dos casos, os da forma 16k+7, 16k+11 e 16k+15.

\begin{array}{cc}16k+7&(\text{usa-se}\qquad 27k+13)\\16k+11&(\text{usa-se}\qquad 27k+20)\\16k+15&(\text{usa-se}\qquad 81k+80).\end{array}

Links úteis:

[4-6-2008: incluído gráfico]

 

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Matemática, Teoria dos Números com as etiquetas . ligação permanente.

15 respostas a Conjectura de Collatz ou problema 3x + 1

  1. thainá diz:

    achei o que eu procurava!!!!!

  2. Nathan diz:

    Presado Americo Tavares,

    primeiramente, cumprimentos pelo blog. Conteúdo interessante e é sempre aplaudida a iniciativa da propagação do conhecimento.

    Em segundo, sabes se o problema em questão continua a ser conjectura?

    Grande abraço,
    Nathan.

  3. Olicheski diz:

    Boa Tarde,
    Bom, pesquisei sobre isso, pq tambem encontrei isso no Boinc, há um projeto la tambem sobre isso.
    http://boinc.thesonntags.com/collatz/

    Agora, fica minha pergunta.
    Para que afinal vai servir isso??? qual a funçao???
    Talvez seja uma pergunta boba, mas gostaria de saber, pois se for algo interesante, quero colocar meu PC a funcionar para esse fim.

    Abraço a todos, obrigado pela resposta.
    Nem preciso dizer que o site esta otimo não é??? so sobre tratar de um tema como esse, ja é algo muito bom.

    • Esta questão por resolver da Teoria dos Números é muito fácil de enunciar mas de resolução certamente muito difícil, atendendo aos anos que já tem e às tentativas infrutíferas a que tem resistido.

      Obrigado pelo link.

      Quanto à pergunta que faz, «Para que afinal vai servir isso???», a minha opinião pouco conhecedora é a de que não se sabe. Mas, como um matemático disse uma vez que não há campo nenhum da Matemática, por mais abstracto que seja, que não venha a ter aplicações, algumas deverão existir, não se sabe é quando e quais.

      Porém penso que a nível teórico deve ter consequências, especialmente se vier a requerer o desenvolvimento de novos métodos, talvez menos se utilizar os existentes de uma forma inovadora.

      Obrigado pela avaliação que faz deste blogue.

      Cumprimentos

    • Olicheski diz:

      Opa…
      é sempre bom receber um comentario do comentario =D
      Bom, como sempre a matematica é algo confuso que com o tempo se torna claro, hoje “brinquei” um pouco com este teorema, e é algo bem interesante, tanto que ja fiz um programa para o computador em DOS mas serve para “brincar”… e diga-se que os calculos sao bem demorados.

      Bom, agora é testar um pouco mais, ja que nao tenho supermaquinas para fazer experiencias cientificas e pesquisar outros teoremas… alguma dica???

      Se quiserem, posso postar os comandos do programa para quem quiser brincar e elaborar ele um pouco mais.

      Abraço a todos.

  4. Olicheski

    Se desejar pode então escrever o seu programa aqui nos comentários ou enviar para o meu e-mail (veja página “Sobre”).

  5. Olicheski diz:

    Bom pessoal, fiz um pequeno programa em Basic, para testar a conjectura, quem quiser utilizar ele para “brincar” um pouco. Esteja a vontade.
    Segue o código.

    10 CLS
    15 FOR F=1 TO 4
    16 A=F
    20 IF A MOD 2=0 THEN GOTO 70
    30 A=(3*A)+1
    40 PRINT A : IF A<=0 THEN GOTO 120
    50 IF A=1 THEN GOTO 110
    60 GOTO 20
    70 A=A/2
    80 PRINT A : IF A<=0 THEN GOTO 120
    90 IF A=1 THEN GOTO 110
    100 GOTO 20
    110 NEXT F
    120 END

    Acima foi os comandos, o basic é bem parecido com a linguagem humana, entao é facil entender.

    Na linha 15 esta os numeros a ser divididos e multiplicados no caso de 1 a 4 (o computador processa o numero 1 tambem, a gente ja sabe quevai dar 1, mas ele faz mesmo assim)

    Na linha 20 o programa analisa se o numero é par ou impar. ele divide o numero por 2, se o resto for diferente de zero entao é impar. "acredito que pode ser analizado asim."

    Nas linhas 40 e 80 o programa "Pinta" na tela o resultado dos calculos e ainda analisa se o resultado é zero ou menor que ele, se for zero ou menor, o programa para. Acredito que assim se tem uma
    segurança para erros e caso haja a confirmação dos calculos serem diferentes de 1.

    Infelismente ainda nao coloquei nada de grafico em tela, o programa so da os resultados corridos, se tiver uma ideia de como fazer os graficos, diagramas… eixos de X e Y, podemos fazer ele como uma
    especie de programa e disponibilizar aqui, no blog para os curiosos de plantão.

    A parte grafica ja dei uma analizada, mas seguindo os graficos do site, eu e um amigo, nao entendemos como se chegou naqueles pontos la. Tem como esplicar como se chega naqueles pontos X e Y, de onde saiu os valores.

    Abraço a todos.

  6. Jonathas Ferreira diz:

    Caro Américo Tavares, poderia explicar um pouco mais sobre como otimizar o algoritmo para o cálculo dos termos da sequência em computado. com um exemplo de códigor?
    Obrigado

  7. Repetindo, se o número for da forma km+r será necessário ter testado antes todos os números da mesma forma com k menor ou igual ao que está a ser testado, o que obriga a uma utilização intensiva de memória, daí uma limitação. Por exemplo, se soubermos que a sequência gerada por 58=12\times 4+10 termina em 1, então 16\times 4+13=77, também acabará por terminar em 1.
    Consultanto as páginas dos autores acima indicadas, vê-se que, até esta altura, Eric Roosendaal verificou a conjectura até 2^{60} e Tomás Oliveira e Silva até 20\times 2^{58}.

  8. alexandre bruno santiago da silva diz:

    estou trabalhando duro para solucionar esse problema, espero conseguir minha pesquisa está bem avançada mas como todos sabem é bem complicado, se eu chegar a uma resposta coloco aqui.

    • olicheski diz:

      Camarada…

      Não sei se minha lógica tá certo, mas todo o número sempre retorna a algum número par logo, sempre retornará a 1.

      e mais, se dividirmos por módulo, não sei se assim se chama isso que vou tentar explicar, mas um problema que se tem é o “estouro” da numeração quando se faz isso no computador, logo temos de dividir os números em pedaços.

      ex… bem tosco mas acho que entenderão o que quero dizer:

      100.000
      Faz-se o calculo com 100 e após o restante dos zeros, dividindo a quantidade de números, logo, todo o número sempre em um dado momento, resultará em 1 pois não faz diferença a quantidade se uma centena já foi calculado o resto sempre se repetirá. Claro, que provar isso é complicado, pois não sou matemático, apenas alguém que “brinca” com os números

      Pelo menos foi a lógica que encontrei, mas não sei como colocar isso em “palavras bonitas” ou se tudo está errado e eu falei uma porcaria =D

      Abraço.

  9. Len diz:

    Saudaçoes a todos

    Neste brilhante blog matematico, eu gostei deste post e para aqueles que se interessam a evoluçao de uma questao especifica desta disciplina [vide os casos da “conjectura fraca de goldbach” solucionada por um peruano em 2012 e da “conjectura fraca dos nrºs primos gemeos” resolvida por um chines em 2013], informo-lhes que em 2011 um alemao chamado Gerhard Opfer propos uma soluçao do problema de Collatz, mas ate agora nao se sabe se a comunidade internacional de matematica aprovou o resultado dele na questao.

    Bem, tenho de ir; adeus e ate a proxima …

  10. Olá,
    eu não entendi quando se usar o km+r, gostaria de deixar mais rápido meu calculo, consigo fazer a formulá básica, mas, não consigo usar a formula do km+r. Alguém pode me ajudar?

  11. Paulo Estevão Pauli diz:

    Paulo Estevão Pauli
    Estudo a Conjectura de Collatz desde 2007, nos primeiros três anos apenas tomando conhecimento dos caminhos já percorridos por famosos matemáticos, a partir do quarto ano iniciei a busca pela referência biunívoca entre frequências encontradas nos cálculos e o Conjunto dos Números Naturais Positivos (N*), quando se consegue essa referência transforma-se a Conjectura em Teorema. Fazem dois anos que encontrei não só a referência biunívoca como também importantes sequências numéricas que podem ser usadas em criptografia entre outros fins.
    Estou pensando em trocar os números primos da criptografia e inserir as frequências encontradas, quem souber de pessoas que trabalham com projeto de criptografia por favor me indiquem.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão /  Alterar )

Google photo

Está a comentar usando a sua conta Google Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão /  Alterar )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.