A Conjectura de Collatz
Você consegue dizer se esse loop terminará em algum momento?
while n > 1:
print(n)
if n % 2 == 0:
n = n / 2
else:
n = n*3 + 1
Para qualquer valor de n diferente de 1, esse programa imprime n, depois checa se n é par (n % 2 == 0
). Caso seja, o novo valor de n passa a ser a metade do valor atual. Caso seja ímpar, o novo valor passa a ser o triplo de n mais 1. O loop somente encerrará quando n for igual a 1.
Por exemplo, se o valor inicial de n for 3
, esta será a sequência de valores atriuidos a n:
3, 10, 5, 16, 8, 4, 2, 1
Observe que às vezes o valor sobe e às vezes desce, o que torna difícil prever para onde ele está tendendo ao longo das iterações do loop.
De fato, até hoje ninguém conseguiu provar que esse loop termina para qualquer número inteiro positivo.
Esse problema foi proposto em 1937 pelo matemático alemão Lothar Collatz e recebeu o nome de Conjectura de Collatz.
Em 2011, o matemático Gerhard Opfer publicou um artigo com o teorema que, segundo ele, provava a Conjectura de Collatz. Mas dois meses depois ele reconheceu que uma das afirmações do seu teorema estava incompleta, e com isso o problema permaneceu sem solução até hoje.
Além de discussões interessantes entre matemáticos, a conjectura também rende belas imagens, como o fractal na imagem deste post.