Project Euler : solution au problème 14, en Python

Rien de tel pour bien digérer, que de digérer des nombres. Le problème 14 joue avec ce qu'on appelle souvent la "suite de Syracuse". Cette suite est simple: partant d'un entier strictement positif, on progresse ainsi:

Il est supposé mais pas prouvé que quel que soit l'entier de départ, cette suite atteint toujours 1 (puis boucle infiniment: 1, 4, 2, 1, ...). Le nombre de pas avant d'atteindre cette limite peut être très grand. Ici on cherche le nombre entier inférieur à un million donnant lieu à la plus longue suite de Syracuse.

... suite de 525 éléments, mine de rien ...

#! /usr/bin/env python

# 2009/02/20 - euler014.py
# Solution au Probleme 14 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=14
# Jean Karim Bockstael - jkb@jkbockstael.be

def collatznext(num):
    if (num % 2 == 0):
        return num / 2
    else:
        return (3 * num) + 1

def collatzlength(start):
    length = 2 # En comptant le seed et le 1 final
    next = collatznext(start)
    while next != 1:
        length = length + 1
        next = collatznext(next)
    return length

def euler14(limit):
    maxlength = 0
    maxseed = 0
    for i in range (1, limit):
        thislength = collatzlength(i)
        if thislength > maxlength:
            maxlength = thislength
            maxseed = i
    return maxseed

print euler14(1000000)

cc-by-nc | code (python) | project euler

<<< Project Euler : solution au problème 15, en Python (2009-02-20) | Project Euler : solution au problème 11, en Python (2009-02-19) >>>