Problem #74 concerns the sum of the factorials of the digits in a number. The question reads:
Project Euler Problem 74: Digit factorial chains
The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
My solution for this problem is quite bad as it involves lots of brute force. Here is my solution:
Solution #1: Brute Force Approach
We simply store the loop length of every number less than 1,000,000 and count the number of starting points which loop with exactly 60 terms. We can do this somewhat dynamically, because once a loop is terminated, all numbers within the loop must have the same loop length. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #74
'''
import time
def digitFactorial(n):
factorials = [1,1,2,6,24,120,720,5040,40320,362880]
total = 0
for x in str(n):
total+=factorials[int(x)]
return total
def projectEulerProblemSeventyFour(n,v):
loops = [-1]*(n)
loops[0] = 0
loops[1] = 1
for x in range(2,n):
if(loops[x]==-1):
temp = x
found = []
alreadyDone = False
loopLength = -1
while(temp not in found):
if(temp<n and loops[temp]!=-1):
loopLength = loops[temp]
alreadyDone = True
loops[x] = len(found)+loopLength
break
found.append(temp)
temp = digitFactorial(temp)
if not alreadyDone:
myIndex = found.index(temp)
loopLength = len(found)-myIndex
for a in range(myIndex,len(found)):
loops[found[a]] = loopLength
loops[x] = len(found)
total = 0
for a in loops:
if a == v:
total+=1
return total
start = time.time()
print projectEulerProblemSeventyFour(1000000, 60)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
402
--- 3.78305602074 seconds ---
for input of n = 1000000, v = 60.
'''
That took over 3.7 seconds to run. There must be a more efficient implementation of this solution. I may come back to this problem eventually to look for a faster solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 