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


class Abbreviations {
  function : Main(args : String[]) ~ Nil {
    Count89s(1000000)->PrintLine();
    Count89s(100000000)->PrintLine();
  }
 
  function : Count89s(limit : Int) ~ Int {
    if(limit < 1) {
      return 0;
    };
 
    result := 0;
    ends := Int->New[Int->Min(limit, 9 * 9 * 9 + 2)];
    for(i := 1; i < ends->Size(); i++;) {
      ends[i] := i;
      while(ends[i] <> 1 & ends[i] <> 89) {
        ends[i] := SquareDigitSum(ends[i]);
      };
 
      if(ends[i] = 89) {
        result++;
      };
    };
 
    for(i := ends->Size(); i < limit; i++;) {
      if(ends[SquareDigitSum(i)] = 89) {
        result++;
      };
    };
 
    return result;
  }
 
  function : SquareDigitSum(n : Int) ~ Int {
    sum := 0;
    while(n > 0) {
      digit := n % 10;
      sum += digit * digit;
      n /= 10;
    };
 
    return sum;
  }
}