# Project Euler 92: sum of squares of digits until a loop is encountered

This is my solution to Project Euler #92:

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?

I was wondering how the code looks from a Pythonic perspective: is there anything that could be better? Cleaner? Is there anything that can be improved upon from a performance perspective?

from itertools import (
islice,
combinations_with_replacement,
groupby
)
import operator

def get_digits(num):
for c in str(num):
yield int(c)

def sum_sq_digits(d):
return sum(i*i for i in d)

def memoize(f):
cache = {}
def wrapped(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return wrapped

@memoize
def sum_sq_chain(num):
if num in (1, 89):
return num

return sum_sq_chain(sum_sq_digits(get_digits(num)))

def fact(i):
return reduce(operator.mul,
xrange(1, i+1),
1)

count = 0
for digits in islice(
combinations_with_replacement(range(10), 7),
1,
None):

if sum_sq_chain(sum_sq_digits(digits)) == 89:
cur = fact(7)
for _, v in groupby(digits):
cur //= fact(len(list(v)))
count += cur

print count

• For an alternate way of solving this, you could take a look at this answer. Commented Dec 25, 2015 at 22:09

Prefer integer arithmetic

def get_digits(num):
while n:
yield n % 10
n //= 10


Integer arithmetic is way faster than string convertion and manipulation, so this alternate version improves the efficiency of the code.

Give names appreciating the generality of your functions

sum_sq_digits works on any integer list. It works on any integer sequence, not just digits, but your name hints that it only works on a list of digits. I would rename it: sum_squared

Make a final function

I like that you wrote many small functions, it really helps readibility, I suggest going the last step and writing a function to solve the problem:

def chain_ending(limit, target)
for digits in islice(
combinations_with_replacement(range(10), limit),
1,
None):

if sum_sq_chain(sum_sq_digits(digits)) == target:
cur = fact(limit)
for _, v in groupby(digits):
cur //= fact(len(list(v)))
yield curr


This way testing it is simpler and you may reuse it with different parameters. To get the final answer, just sum the generator this function yields.

Re-use

You will want to reuse as much as possible of your logic, to avoid duplicating work and possible errors.

The factorial function makes use of an in-place-defined product, I think that a separate product function will make code a little more English-like and will save you effort from re-writing it as getting the product of a sequence is a common task.

By the same point of view, using if __name__ == "__main__" allows you to import the script without running it, enabling re-use.