Problem Description

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?

Analysis

To begin, all chains that end in 1 are called happy numbers. Any chain that contains an 89 will be destined to an endless loop of calculations.
Here’s more information from Wikipedia: http://en.wikipedia.org/wiki/Happy_number

If you think about it, 9,999,999 is the largest number we will have to check and the first (and largest) element is 9^2 * 7 (which is 567). This allows us to build a cache of flags for the first 567 numbers and mark them as happy (flag=0) or unhappy (flag=1). Now we can check all the numbers for 1 to 10,000,000 and after calculating just the first element in the chain, determine whether it is happy or not.

Solution

Runs < 3 minutes in Python.

cache = [0]*568
 
for cxi in range(2,568):
  n = cxi
  while n!=1:
    n = sum(int(t)**2 for t in str(n))
    if n==89 or n==4:
      cache[cxi]=1
      break
 
c = 0
for i in range(1,10000000):
  n = sum(int(t)**2 for t in str(i))
  if cache[n]==1: c+=1
 
print "Answer to PE92 = ",c

Comments