Problem #92 concerns the results when numbers are repeatedly replaced by the square of their digits. The question reads:
Project Euler Problem 92: Square digit chains
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?
My solution for this problem is very bad as it takes longer than a minute to run. Here is my solution:
Solution #1: Brute Force Approach
Starting from 10,000,000 and working down, we manually check whether each number ends at 1 or 89 and then store all intermediate numbers based on whether they end in 1 or 89. With this approach, it is possible to dynamically determine whether each smaller number will end in a loop. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #92
'''
import time
def squareDigits(x):
a = str(x)
total = 0
for b in a:
total+=int(b)**2
return total
def projectEulerProblemNinetyTwo(n):
found = [-1]*(n)
found[1] = 1
found[89] = 89
total = 0
for c in range(n-1,1,-1):
endsOne = True
if(found[c]==-1):
temp = c
change = []
while(temp!=89 and temp!=1 and (temp>n or found[temp]==-1)):
if(temp<=c):
change.append(temp)
temp = squareDigits(temp)
if(temp == 89 or found[temp] == 89):
endsOne = False
total+=1
if endsOne:
for x in change:
found[c] = 1
else:
for x in change:
found[c] = 89
else:
if(found[c] == 89):
total+=1
return total
start = time.time()
print projectEulerProblemNinetyTwo(10000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
8581146
--- 105.508774042 seconds ---
for input of n = 10000000.
'''
And with that, we’re done. That took over 100 seconds to run, so I will definitely want to look back at this question at some point. However, it appears that dynamically finding the answer can work even when it requires the creation of an array with 10,000,000 elements.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 