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


fcn check(number){  // a list of digits: 13 is L(0,0,0,0,0,0,1,3)
   candidate:=number.reduce(fcn(sum,n){ sum*10 + n },0);  // digits to int
 
   while(candidate != 89 and candidate != 1)  // repeatedly sum squares of digits
      { candidate = candidate.split().reduce(fcn(sum,c){ sum + c*c },0); }
 
   if(candidate == 89){ // count permutations of these digits, they all sum to 89
      digitsCount:=List(0,0,0,0,0,0,0,0,0,0);
      foreach d in (number){ digitsCount[d] += 1; }
      return(digitsCount.reduce(fcn(r,c){ r/factorial(c) },cacheBang)); // cacheBang==number.len()!
   }
   0 // this number doesn't sum to 89 (ie sums to 1)
}
fcn factorial(n) { (1).reduce(n,fcn(N,n){ N*n },1) }
 
limit:=0d100_000_000;  cacheSize:=limit.toFloat().log10().ceil().toInt();
number:=(0).pump(cacheSize,List().write,0); // list of zeros
result:=0; i:=cacheSize - 1;
var cacheBang=factorial(cacheSize);  //== number.len()!
 
while(True){  // create numbers s.t. no set of digits is repeated
   if(i == 0 and number[i] == 9) break;
   if(i == cacheSize - 1 and number[i] < 9){ number[i] += 1; result += check(number); }
   else if(number[i] == 9) i -= 1;
   else{
      number[i] += 1;
      foreach j in ([i + 1 .. cacheSize - 1]){ number[j] = number[i]; }
      i = cacheSize - 1;
      result += check(number);
   }
}
println(result);