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):
        num = i
        while num not in [1,89]:
            num = square_digits(num)
        if num == 1:
            square_dict[i] = 1
        else:
            square_dict[i] = 89
    return square_dict


def square_chains(limit, square_dict):
    # Finds the number of chains ending in 1 and 89
    count_1 = 0
    count_89 = 0
    for i in range(1, limit):
        boolean, square_dict = single_chain(i, square_dict)
        if boolean:
            count_1 += 1
        else:
            count_89 += 1
    print "Chains ending in 1: ", count_1
    print "Chains ending in 89: ", count_89


if __name__ == '__main__':
    square_dict = pre_calculation(9*9*7)
    square_chains(10**7,square_dict)
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 &gt; 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.