Voici un résumé de l'énoncé du problème 14 "Longest Collatz sequence" du Project Euler (traduction complète en français ici) :

Which starting number, under one million, produces the longest Longest Collatz chain?

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de départ inférieur à 1 million qui produit la plus longue suite de Collatz.

L'exemple donné dans l'énoncé du problème nous montre que si nous prenons 13 comme nombre de départ, nous arriverons à 1 au bout de 9 itérations de la suite (\(n \rightarrow n/2\) si \(n\) est pair et \(\n \rightarrow 3n+1\) si \(n\) est impair). Mais grâce à l'exemple, nous savons aussi que si nous prenons 40 comme nombre de départ, nous arriverons à 1 au bout de 8 itérations, si nous prenons 20, au bout de 7 itérations, si nous prenons 10 au bout de 6, si nous prenons 5, au bout de 5, si nous prenons 16, au bout de 4, si nous prenons 8, au bout de 3, si nous prenons 4, au bout de 2, et si nous prenons 2, au bout de 1.

Grâce à cet exemple, nous savons dorénavant, que si nous prenons un nombre \(n\) de départ et que, à un moment dans la suite, nous tombons sur 20, par exemple, nous pourrons nous arrêter et ajouter 7 à la longueur de la chaine de Collatz qui était en cours de calcul. Nous pourrons aussi ajouter à la liste, obtenue précédemment, du nombre d'itérations restantes en fonction du nombre de départ, \(n\) ainsi que tous les autres termes de la suite, pour lesquels on connait maintenant le nombre d'itération qu'il faut, en partant d'eux pour arriver à un.

Appliquons notre raisonnement au nombres de départ 2, 3 et 4, tout en partant de 0, c'est à dire, en sachant juste que si nous arrivons à 1, nous n'avons plus d'itérations à faire, la chaîne est finie. Pour nous faciliter la tâche, notons cette information dans un "dictionnaire" comme ceci : {1: 0}. Ainsi :

• pour 2, nous obtenons : \(2 \rightarrow  1\) et comme nous savons que si nous arrivons à 1, la chaîne est fini, nous pouvons en déduire que la longueur de la chaîne de Collatz est 2 quand le nombre de départ est 2
• pour 3, nous obtenons : \(3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2\) et comme nous savons, grâce au précédent point, que si nous arrivons à 2, il nous faut encore 1 itérations de la suite pour arriver à 1, nous pouvons en déduire que la longueur de la chaîne de Collatz est de 8. De plus, nous pouvons aussi en déduire que si le nombre de départ est 10, nous obtenons 7 termes pour arriver à 1, ... jusqu'à 4, ce qui nous donne au final, le dictionnaire suivant non trié : {1: 0, 2: 1, 3: 7, 10: 6, 5: 5, 15: 4, 8: 3, 4: 2}
• pour 4, nous n'avons même pas besoin de commencer la suite car nous avons déjà trouvé, dans le point précédent, le nombre d'itérations à faire pour arriver à 1

Il nous faut alors continuer à appliquer cette méthode pour les nombres de départ 5, 6, 7, ... jusqu'à 1 million.

Le programme

Appliquons maintenant le raisonnement obtenu plus haut dans notre programme. Pour se faire, nous devons faire appel à la récursivité. Si vous savez ce que c'est et savez l'utiliser, le programme ne devrait pas vous poser de problèmes de compréhension, sinon voici un tutoriel explicatif à ce sujet. Le programme Python à utiliser pour résoudre le problème est le suivant :

sequence_length = {1: 0}
def collatz_sequence_length(nb):
    global sequence_length
    #Si on trouve le nombre dans notre tableau, on retourne
    #sa valeur, cad la longueur de la chaîne à partir de ce terme-là
    if nb in sequence_length:
        return sequence_length[nb]
    #Si le nombre n'a pas été trouvé dans le tableau, on calcule le
    #terme suivant de la suite et appelle la fonction pour qu'elle
    #nous donne la longueur de la chaine à partir de ce terme
    if nb%2 == 0:
        length = collatz_sequence_length(nb//2)
    else:
        length = collatz_sequence_length(3*nb + 1)
    length += 1
    sequence_length[nb] = length
    return length
resultat = 0
longest = 0
for i in range(1, 1000000):
    length = collatz_sequence_length(i)
    if length > longest:
        resultat = i
        longest = length
print(resultat)

Le résultat

La réponse à ce problème est 837799.