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


' FB 1.05.0 Win64
 
' similar to C Language (first approach)
' timing for i3 @ 2.13 GHz
 
Function endsWith89(n As Integer) As Boolean
  Dim As Integer digit, sum = 0
  Do
    While n > 0
      digit = n Mod 10
      sum += digit * digit
      n \= 10
    Wend
    If sum = 89 Then Return True
    If sum = 1 Then Return False
    n = sum
    sum  = 0
  Loop  
End Function
 
Dim As Double start = timer 
Dim sums(0 To 8 * 81) As UInteger 
sums(0) = 1
sums(1) = 0
Dim s As Integer
For n As Integer = 1 To 8 
  For i As Integer = n * 81 To 1 Step -1
    For j As Integer = 1 To 9
      s = j * j        
      If s > i Then Exit For
      sums(i) += sums(i - s)
    Next j
  Next i
 
  If n = 8 Then
    Dim As UInteger count89 = 0 
    For i As Integer = 1 To n * 81
      If Not endsWith89(i) Then Continue For
      count89 += sums(i)
    Next i 
    Print "There are";count89; " numbers from 1 to 100 million ending with 89"
  End If
Next
Print "Elapsed milliseconds ="; Int((timer - start) * 1000 + 0.5) 
Print
Print "Press any key to quit"
Sleep