Tous les défis
Moyen 0 résolus 0 % de réussite

Plus longue suite de Syracuse (Collatz)

Trouver le nombre de départ, jusqu'à une limite, dont la suite de Syracuse est la plus longue.

Ce que vous allez apprendre

  • Générer une suite de Syracuse
  • Mettre les résultats en cache pour éviter les calculs répétés
  • Départager les égalités par la plus petite valeur

Problème

Partant d'un entier positif n, la règle de Collatz (suite de Syracuse) donne comme terme suivant n / 2 si n est pair et 3n + 1 si n est impair, et la suite s'arrête lorsqu'elle atteint 1. Pour 6, on obtient 6, 3, 10, 5, 16, 8, 4, 2, 1, soit neuf termes. Parmi tous les nombres de départ de 1 à limit, trouvez celui qui produit le plus de termes.

Implémentez longest_collatz_chain(limit).

Les suites ont des fins communes : mémoriser la longueur trouvée pour chaque nombre évite beaucoup de calculs. En chemin, les termes peuvent dépasser la limite ; utilisez des entiers sur 64 bits.

Entrée

limit : le plus grand nombre de départ à essayer.

Sortie

Renvoyez le nombre de départ dont la suite a le plus de termes (en comptant le départ et le 1 final). En cas d'égalité, renvoyez le plus petit.

Contraintes

1 ≤ limit ≤ 100 000

Exemples

Exemple 1
Entrée :
limit = 6

Sortie attendue :
expected = 6
Entrée :
long long limit = 6;

Sortie attendue :
long long expected = 6;
Entrée :
long limit = 6;

Sortie attendue :
long expected = 6;

Explication

Pour les départs de 1 à 6, les suites ont 1, 2, 8, 3, 6 et 9 termes, donc la réponse est 6.

Exemple 2
Entrée :
limit = 10

Sortie attendue :
expected = 9
Entrée :
long long limit = 10;

Sortie attendue :
long long expected = 9;
Entrée :
long limit = 10;

Sortie attendue :
long expected = 9;

Explication

9 donne 20 termes (9, 28, 14, 7, ...), plus que tout autre départ jusqu'à 10, donc la réponse est 9.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Commencez par compter les termes d'une seule suite, départ et 1 compris.

Indice 2

Quand une suite atteint un nombre dont vous connaissez déjà la longueur, additionnez au lieu de continuer.

Indice 3

Ne remplacez le meilleur départ que si la longueur est strictement plus grande.

Complexité attendue

temps O(limit × average new steps), c'est-à-dire limit fois le nombre moyen de nouvelles étapes, espace supplémentaire O(limit)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.