Sequência de Collatz

A sequência de collatz e algumas implementações.

October 15, 2015
haskell collatz ruby matemática

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)