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


 
MODULE DigitsSquaring;
IMPORT
  Out;
 
VAR
  i,hits89: LONGINT;
 
  PROCEDURE Squaring(n: LONGINT): LONGINT;
  VAR
    d, sum: LONGINT;
  BEGIN
    LOOP
      sum := 0;
      WHILE n > 0 DO
        d := n MOD 10;
        INC(sum,d * d);
        n := n DIV 10
      END;
      IF (sum = 1) OR (sum = 89) THEN EXIT END;
      n := sum;
    END;
 
    RETURN sum
  END Squaring;
 
BEGIN
  hits89 := 0;
  FOR i := 1 TO 100000000 DO
    IF Squaring(i) = 89 THEN INC(hits89) END
  END;
  Out.LongInt(hits89,0);Out.Ln
END DigitsSquaring.
 
 