Project Euler 92: Square digit chains
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.