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


sumDigitsSquared[n_Integer] := Total[IntegerDigits[n]^2]
stopValues = Join[{1}, NestList[sumDigitsSquared, 89, 7]];
iterate[n_Integer] := 
 NestWhile[sumDigitsSquared, n, Intersection[stopValues, {#}] == {} &]
 
numberOfDigits = 8;
maxSum = numberOfDigits 9^2;
loopVariables = 
  ToExpression@Table["i" <> ToString[n], {n, numberOfDigits}];
iteratesToOne = Cases[Range@maxSum, _?(iterate[#] == 1 &)];
allIterators = 
  Flatten[{Reverse@#, 9}] & /@ Partition[loopVariables, 2, 1];
maxCombinations = numberOfDigits!;
 
ssd = 
  SparseArray[Table[n^2 -> numberOfDigits, {n, 9}], {maxSum}];
 
Do[
  variables = loopVariables[[;; digitCount]];
  iterators = allIterators[[;; digitCount - 1]];
 
  Do[ssd += 
    SparseArray[
     Total[variables^2] -> 
      maxCombinations/
       Times @@ (Tally[PadRight[variables, numberOfDigits]][[All, 
            2]]!), {maxSum}], {i, 9}, Evaluate[Sequence @@ iterators]],
 
  {digitCount, 2, numberOfDigits}];
 
onesCount = 
 Total[Cases[
    ArrayRules[ssd] /. 
     HoldPattern[{a_} -> b_] :> {a, 
       b}, {_?(MemberQ[iteratesToOne, #] &), _}][[All, 2]]];
 
(10^numberOfDigits - 1) - onesCount