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


 
(defun square (number)
  (expt number 2))
 
(defun list-digits (number)
  "Return the `number' as a list of its digits."
  (loop
    :for (rest digit) := (multiple-value-list (truncate number 10))
                      :then (multiple-value-list (truncate rest 10))
    :collect digit
    :until (zerop rest)))
 
(defun next (number)
  (loop
    :for digit :in (list-digits number)
    :sum (square digit)))
 
(defun chain-end (number)
  "Return the ending number after summing the squaring of the digits of
`number'.  Either 1 or 89."
  (loop
    :for next := (next number) :then (next next)
    :until (or (eql next 1)
               (eql next 89))
    :finally (return next)))
 
(time
 (loop
   :with count := 0
   :for candidate :from 1 :upto 100000000
   :do (when (eql 89 (chain-end candidate))
         (incf count))
   :finally (return count)))
 