If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89:

15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89
7 -> 49 -> 97 -> 130 -> 10 -> 1
An example in Python:

>>> step = lambda x: sum(int(d) ** 2 for d in str(x))
>>> iterate = lambda x: x if x in [1, 89] else iterate(step(x))
>>> [iterate(x) for x in xrange(1, 20)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]


Task

 Count how many number chains for integers 1 <= n < 100_000_000 end with a value 89.
Or, for much less credit - (showing that your algorithm and/or language is slow):

 Count how many number chains for integers 1 <= n < 1_000_000 end with a value 89.
This problem derives from the Project Euler problem 92.

For a quick algorithm for this task see the talk page



Related tasks

 Combinations with repetitions
 Digital root
 Digital root/Multiplicative digital root


F next_step(=x)
   V result = 0
   L x > 0
      result += (x % 10) ^ 2
      x I/= 10
   R result
 
F check(number)
   V candidate = 0
   L(n) number
      candidate = candidate * 10 + n
 
   L candidate != 89 & candidate != 1
      candidate = next_step(candidate)
 
   I candidate == 89
      V digits_count = [0] * 10
      L(d) number
         digits_count[d]++
 
      V result = factorial(number.len)
      L(c) digits_count
         result I/= factorial(c)
      R result
 
   R 0
 
V limit = 100000000
V cache_size = Int(ceil(log10(limit)))
assert(10 ^ cache_size == limit)
 
V number = [0] * cache_size
V result = 0
V i = cache_size - 1
 
L
   I i == 0 & number[i] == 9
      L.break
   I i == cache_size - 1 & number[i] < 9
      number[i]++
      result += check(number)
   E I number[i] == 9
      i--
   E
      number[i]++
      L(j) i + 1 .< cache_size
         number[j] = number[i]
      i = cache_size - 1
      result += check(number)
 
print(result)