Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 14 : solution Python

Article

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 :

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.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.