Project Euler Problem 34 Factorions

[root@www ~]# python thirtyfour.py
145
40585
Started at: Thu Oct 23 13:20:38 2008 Ended at: Thu Oct 23 13:21:23 2008
[root@www ~]# cat thirtyfour.py
# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()

# 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

# Find the sum of all numbers which are equal to the sum of the factorial of their digits.

# Note: as 1! = 1 and 2! = 2 are not sums they are not included.

# An 8 digit number cannot be less than 10,000,000

# Nine factorial is 362880

# So the largest sum-of-factorials which an 8 digit number can have

# is 8 * 362880 = 2903040

# Similarly for 9 or more digits.

# Therefore a curious number can have at most seven digits.

# The largest curious number can be at most 7 * 362880 = 2540160


def factorial(n):
"""
Factorial function

>>> factorial(5)
120

>>> factorial(1)
1

>>> factorial(0)
1

"""
if n < 0:
return -999999
elif n < 2:
return 1
else:
return n * factorial(n - 1)

class precalc:
def __init__(self):
"""
Stores precalculated factorials

>>> x = precalc()
>>> x.ten[0]
1

"""
self.ten = [1] + [factorial(n) for n in range(1,10)]

pc = precalc()
fact = pc.ten

def getFact(n):
"""
Reads precalculated single-digit factorials

>>> getFact(5)
120

>>> getFact(4)
24

>>> getFact(0)
1

>>> getFact(8)
40320


"""

return fact[int(n)]


def sumOfFactorialsHelper(n):
"""
Find the sum of the factorials in each digit of n

>>> sumOfFactorialsHelper(145)
[1, 24, 120]

mathworld.wolfram.com says that there are only four
factorions: 1,2, 145 and 40585

>>> sumOfFactorialsHelper(40585)
[24, 1, 120, 40320, 120]



"""
s = str(n)
digits = [s[i] for i in range(len(s))]
factDigits = map(getFact, digits)
return factDigits

for n in range(10, 2540161):
if sum(sumOfFactorialsHelper(n)) == n:
print n



print "Started at: ", starttime, " Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()