Project Euler 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?

To tackle this problem I used the following procedure.

• set array[1] to 1

• set array[89] to 89

• loop through all starting numbers from 2 to 10,000,000

• for each starting number, calculate sum of squares until a previously calculated number is found

• mark off all numbers in the chain you have just created as either 89 or 1

• count the number of starting numbers that now have 89 as their array value

However even after using this relative clever strategy, my code still takes half a minute to compute. Is there something wrong I have done in my logic, or are there any other obvious improvements? I also think this strategy uses a large chunk of memory.

```
def square_digits(num):
# Squares the digits of a number, eg 44=4^2+4^2=32
total = 0
while num:
total += (num % 10) ** 2
num //= 10
return total

def single_chain(num, square_dict):
# Evaluates a single chain untill 1 or 89
temp_nums = []
while True:
if num in [1, 89]:
break
try:
# If we hit a previously calculated value, break
num = square_dict[num]
break
except:
temp_nums.append(num)
num = square_digits(num)
for i in temp_nums:
# Backtrack through the chain saving each number
square_dict[i] = num
return num == 1, square_dict

def pre_calculation(limit):
# Precalculates the first values
square_dict = dict()
for i in range(1,limit+1):

I already posted the incremental improvement answer. Here's the home run answer.

Consider the number 4,666,777. This number happens to chain into 89. That takes some amount of work to figure out. But eventually we get there. What does this tell us? Since we're only interested in the sum of the squares of the digits, the actual ordering of the digits is irrelevant. That is... once we know that 4,666,777 is valid, we also know that 6,466,777 is valid, and 7,664,776 is valid, and ... All 140 unique permutations of the digits 4666777 are things we want to count. The key is: once we're done with 4666777, we do not even need to consider the other 139!

There are only 11,440 unique digit combinations from 1 to 10,000,000. Any solution checking all of them is thus doing ~900x more work than necessary. We can use itertools.combinations_with_replacement to get the unique digit combinations, and then use itertools.groupby to help determine how many such combinations there are.

Still with the memoized my_square_chain:

def euler89():
    count_89 = 0 
    fact7 = fact(7)
    digits = range(10)

    for num in itertools.combinations_with_replacement(digits, 7): 
        cur = sum(d**2 for d in num)
        if cur > 0 and my_square_chain(cur) == 89: 
            count = fact7
            for _, g in itertools.groupby(num):
                count /= fact(len(list(g)))
            count_89 += count
    return count_89

This runs in 0.120s on my box. A performance improvement of 265x from my incremental changes, and 381x from the original solution.

StackExchange Code Review Q#109255, answer score: 15