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.

14 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?

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 )

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 )

Google+ photo

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

Connecting to %s