Sequência de Collatz

Collatz

A Conjectura de Collatz é um problema matemático muito simples, mas que ainda não tem uma prova matemática. Portanto, é um problema em aberto.

Funciona assim:

Escolha um número inteiro x positivo qualquer.  
Para todo x > 0, faça:  
    se x for par, divida o número por 2 (x = x/2)
    se x for ímpar,  triplique o número e adicione 1 (x = 3x + 1)

A Conjectura de Collatz afirma que se você continuar rodando esse algoritmo, será gerada uma sequência de números que sempre terminará com x = 1.

Por exemplo:

Seja x = 10. Teremos a seguinte sequência de collatz para x:
[10, 5, 16, 8, 4, 2, 1].

Seja x = 77. Teremos a seguinte sequência de collatz para x:
[77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1].

Ou seja, pouco importa o valor inicial de x, sempre teremos no final da sequência o número 1.

Uma implementação em Ruby:

def collatz n  
  seq = [n]
  until n == 1
    n = (n.even?) ? (n / 2) : (3 * n + 1)
    seq << n
  end
  seq
end  

Outra implementação em Haskell:

chain :: (Integral a) => a -> [a]  
chain 0 = error "Inválido!"  
chain 1 = [1]  
chain x  
  | even x = x:chain (x `div` 2)
  | odd x = x:chain (x*3 + 1)