20/02/2009
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:
- si l'entier est pair, on le divise par deux
- si l'entier est impair, on le multiplie par trois et on ajoute 1 au résultat
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)