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


with Ada.Text_IO;
 
procedure Digits_Squaring is
 
   function Is_89 (Number : in Positive) return Boolean
   is
      Squares : constant array (0 .. 9)  of Natural :=
        (0, 1, 4, 9, 16, 25, 36, 49, 64, 81);
 
      Sum : Natural := Number;
      Acc : Natural;
   begin
      loop
         Acc := Sum;
         Sum := 0;
         while Acc > 0 loop
            Sum := Sum + Squares (Acc mod 10);
            Acc := Acc / 10;
         end loop;
 
         if Sum = 89 then  return True;  end if;
         if Sum =  1 then  return False; end if;
      end loop;
   end Is_89;
 
   use Ada.Text_IO;
   Count : Natural := 0;
begin
   for A in 1 .. 99_999_999 loop
      if Is_89 (A) then
         Count := Count + 1;
      end if;
 
      if A = 999_999 then
         Put_Line ("In range 1 ..    999_999: " & Count'Image);
      end if;
 
   end loop;
   Put_Line ("In range 1 .. 99_999_999: " & Count'Image);
end Digits_Squaring;