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


 
test: procedure options (main, reorder); /* 6 August 2015 */
 
   declare (m, n) fixed decimal (10);
   declare (i, j, p, s, tally initial (0) ) fixed binary (31);
   declare d fixed binary (7);
   declare (start_time, finish_time, elapsed_time) float (15);
 
   start_time = secs();
 
   do m = 1 to 1000000;
      n = m;
      do until ((n = 1) | (n = 89));
         p = n; s = 0;
         do while (p > 0);
            d = mod(p, 10);
            p = p/10;
            s = s + d*d;
         end;
         n = s;
      end;
      if n = 89 then tally = tally + 1;
   end;
 
   finish_time = secs();
   put skip edit (Tally, ' numbers iterated to 89') (f(10), A);
   elapsed_time = finish_time - start_time;
   put skip edit ('Elapsed time=', elapsed_time, ' secs') (A, F(10,3));
 
end test;
 