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


import tables
 
iterator digits(n: int): int =
  ## Yield the digits starting from the unit.
  var n = n
  while true:
    yield n mod 10
    n = n div 10
    if n == 0:
      break
 
 
func gen(n: int): int =
  ## Compute the chain.
  result = n
  while result notin [1, 89]:
    var s = 0
    for d in digits(result):
      inc s, d * d
    result = s
 
 
func chainsEndingWith89(ndigits: Natural): Natural =
  ## Compute the number of chains ending with 89.
 
  # Initialize the count table with values for one digit numbers.
  var prevCount, currcount: CountTable[int]
  for i in 0..9: prevcount[i * i] = 1
 
  # Add next digits.
  for _ in 2..ndigits:
    # Create the next generation count array.
    currcount.clear()
    for val, count in prevcount:
      for newdigit in 0..9:
        # As 0 is included, "currcount" includes "prevcount".
        currcount.inc(newdigit * newdigit + val, count)
    prevcount = currcount
 
  for val, count in currcount:
    if val != 0 and gen(val) == 89:
      inc result, count
 
echo "For  8 digits: ", chainsEndingWith89(8)
echo "For 50 digits: ", chainsEndingWith89(15)