6
\$\begingroup\$

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)
\$\endgroup\$
15
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

This won't affect performance, but your return choice for single_chain is odd. Since everything in python is a reference, you don't need to return square_dict. It's unnecessary, you could just return num. Then on the call side:

if single_chain(i, square_dict) == 1:
    count_1 += 1
else:
    count_89 += 1

reads a bit better. Your pre_calculation doesn't actually do anything useful either, you can drop it completely.

Exceptions exceptions exceptions

Exception are expensive. Most of your time is spent here:

try:
    # If we hit a previously calculated value, break
    num = square_dict[num]
    break
except: 
    temp_nums.append(num)
    num = square_digits(num)

But if we reorganize this to a non-throwing version:

store = square_dict.get(num, None)
if store is not None:
    num = store
    break
else:
    temp_nums.append(num)
    num = square_digits(num)

Runtime drops from 45.7s on my box to 34.7s.

Memoization

This problem also lends itself well to memoization, which actually makes the logic a ton simpler since you can just write:

@memoize
def my_square_chain(i):
    if i == 1 or i == 89: 
        return i

    return my_square_chain(square_digits(i))

It's shorter and easier to reason about, with the added benefit that it's also a little bit faster (31.8s).

\$\endgroup\$
  • \$\begingroup\$ Quite disagree with your exception part. EAFP is the python preferred approach and can be quite faster than using ifs if the amount of KeyError (in this case) is very low. The thing, here, is that it gets a KeyError for every input, thus being inefficient. Calling single_chain(square_digits(i), square_dict) in square_chains will produce only 495 KeyErrors without changing the outcome. \$\endgroup\$ – 409_Conflict Oct 30 '15 at 14:20
  • \$\begingroup\$ @MathiasEttinger You disagree with the fact that avoiding exceptions made it 50% faster? It doesn't matter what the "preferred" approach is - it was slower. \$\endgroup\$ – Barry Oct 30 '15 at 14:25
  • 2
    \$\begingroup\$ Thing is I was testing with Python 3 and not getting improvements between try ... except and if ... else. get was even a slitly slower. Just tested with python2 and got similar results. 45s for try, 34s for get and 31s for if num in square_dict.But, as I said, having less than 1% of dict access resulting in an exception using boolean, square_dict = single_chain(square_digits(i), square_dict) gives a slight advantage to try (26s) over if (27s). Whatever, you nailed it with your second answer. \$\endgroup\$ – 409_Conflict Oct 31 '15 at 20:42
2
\$\begingroup\$

square_digits

You actually sum the square digits, making the code longer and less reusable, instead just yield them:

def square_digits(num):
    while num:
        yield (num % 10) ** 2
        num //= 10

Example usage:

>>> square_digits(146)
<generator object square_digits at 0x7f6a0b5930a0>
>>> list(_) # `_` is the previous value
[1, 16, 36]

In fact you may make your function even more versatile:

def digits(n):
    while n:
        yield n % 10
        n //= 10

Now you may use it in solving any problem that involves finding digits.

Also note that using my functions requires a slight change in the calling code:

  • square_digits(num) -> sum(square_digits(num))
  • square_digits(num) -> sum(i**2 for i in digits(num))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.