Problema 14 - Maior seqüência de Collatz

Dado n inteiro positivo, uma seqüência de Collatz para n é uma seqüência gerada da seguinte maneira:

• n <- n / 2, se n for par;
• n <- 3*n + 1, se n for ímpar.

Existe uma conjectura que supõe que todas as seqüências de Collatz terminam em 1.

O que o Problema 14 quer saber é: qual n abaixo de 1 milhão produz a seqüência de Collatz mais longa? Eu resolvi isso de duas maneiras.

Método 1

Este é o método mais direto. Para cada número entre 2 e 1.000.000, ir gerando o próximo elemento da seqüência de Collatz e ativar um contador. Vence quem tiver o maior contador ao final.

Usei o pacote "parallel" pela primeira vez aqui, para poder aplicar aqui a função de contagem em mais de um elemento/seqüência ao mesmo tempo através de computação paralela. Interessante notar, também, que basta testar n para n ímpar (por quê?), deixando o cálculo aproximadamente duas vezes mais rápido.

Método 2

Não usei computação paralela. Mas eu tomei vantagem de um corolário da conjectura citada na (minha) descrição do problema: se m pertence à seqüência gerada por n, então ambas seqüências serão iguais a partir de m. Em outras palavras, se estou gerando a seqüência de n, cheguei em m e já conheço o tamanho da seqüência de m, posso parar aí e verificar o próximo n.

O Método 1 levou, no meu caso, 5,85 minutos para ser executado, enquanto o Método 2 levou 35,19 segundinhos.