Problème 14 "Colonne de nombre de collats la plus longue"
Définissez une séquence de nombres qui est générée à plusieurs reprises par la formule suivante pour un entier positif.
n → n/2 (n est pair)\\ n → 3n + 1 (n est étrange)À partir de 13, cette séquence de nombres ressemble à ceci:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1Il y a 10 termes de 13 à 1. On pense que cette séquence se termine à 1 quel que soit le nombre avec lequel vous commencez, mais cela n'a pas encore été prouvé (problème de Colats).
Maintenant, lequel des nombres inférieurs à 1 million devrait être lancé pour générer la plus longue séquence de nombres?
Remarque: peut-être plus d'un million au milieu d'une rangée
Python
n = 1000000
seq = range(1, n)
collatz_dict = {1: [1]}
def compute_collatz(i):
if(i not in collatz_dict):
if(i % 2 == 0):
collatz = [i] + compute_collatz(i / 2)
else:
collatz = [i] + compute_collatz(3 * i + 1)
collatz_dict[i] = collatz
return collatz_dict[i]
collatz_lenghs = {}
for i in seq:
collatz = compute_collatz(i)
collatz_lenghs[i] = len(collatz)
max_length = max(collatz_lenghs.values())
max_index = collatz_lenghs.values().index(max_length)
max_length_collatz_key = collatz_lenghs.keys()[max_index]
max_length_collatz = collatz_dict[max_length_collatz_key]
result = max_length_collatz_key
print result
print result == 837799
print max_length
print max_length_collatz[:6]
résultat
837799
True
525
[837799, 2513398, 1256699, 3770098, 1885049, 5655148]
Il est un peu tard, mais je ne vois pas de bon moyen.
Recommended Posts