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


OpenConsole()
Procedure is89(x)
  Repeat
    s=0
    While x : s+ x%10*x%10 : x/10 : Wend
    If s=89 : ProcedureReturn 1 : EndIf
    If s=1  : ProcedureReturn 0 : EndIf
    x=s
  ForEver
EndProcedure
 
Procedure main()
  Dim sums(32*81+1) : sums(0)=1 : sums(1)=0
 
  For n=1 To n+1
    For i=n*81 To 1 Step -1
      For j=1 To 9
        s=j*j : If s>i : Break : EndIf
        sums(i)+sums(i-s)
      Next
    Next
    count89=0
    For i=1 To n*81+1
      If Not is89(i) : Continue : EndIf
      If sums(i)>9223372036854775807-count89
        PrintN("counter overflow for 10^"+Str(n))
        ProcedureReturn 0
      EndIf
      count89+sums(i)
    Next
    PrintN("1->10^"+LSet(Str(n),2,Chr(32))+": "+Str(count89))
  Next  
EndProcedure
 
start=ElapsedMilliseconds()
main()
Print("elapsed milliseconds= "+Str(ElapsedMilliseconds()-start))
Input()