06/04/2009
Project Euler : solution au problème 23, en Python
Un dernier pour aujourd'hui, vu que je ne serai sûrement pas vraiment généreux en code cette semaine, ni la semaine prochaine. Disons que je prends un peu d'avance.
Le problème 23 est une question de nombres abondants. Connaissant la somme des diviseurs propres d'un nombre, on dit que ce nombre est déficient si cette somme est inférieure à lui-même (c'est le cas du nombre 10), parfait si cette somme lui est égale (28 l'est), abondant si elle est supérieure à lui-même (12 est abondant).
Il est un fait établi que tous les nombres supérieurs à 28123 peuvent être écrits comme la somme de deux nombre abondants. Les entiers qui ne sont pas exprimables comme somme de deux abondants forment donc un ensemble fini. On en demande la somme.
#! /usr/bin/env python
# 2009/04/06 - euler023.py
# Solution au Probleme 23 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=23
# Jean Karim Bockstael - jkb@jkbockstael.be
def getproperdivisors(num):
res = []
for i in range(1, num / 2 + 1):
if (num % i == 0):
res.append(i)
return res
def sumofproperdivisors(num):
return sum(getproperdivisors(num))
def isabundant(num):
return (sumofproperdivisors(num) > num)
def getabundantnumbers(lim):
res = []
for i in range(1, lim + 1):
if isabundant(i):
res.append(i)
return res
def issumofabundants(num, abundants):
res = False
for i in abundants:
if ((num - i) in abundants):
res = True
break
return res
def euler23(lim):
abundants = getabundantnumbers(lim)
res = []
for i in range(1, lim + 1):
if not (issumofabundants(i, abundants)):
res.append(i)
return sum(res)
print euler23(28123)