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


      REM Version 1: Brute force
      REM ---------------------------------------------------------
      T%=TIME
      N%=0
      FOR I%=1 TO 100000000
        J%=I%
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          J%=K%
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=1
      NEXT
      PRINT "Version 1: ";N% " in ";(TIME-T%)/100 " seconds."
 
      REM Version 2: Brute force + building lookup table
      REM ---------------------------------------------------------
      T%=TIME
      DIM B% 9*9*8,H%(9)
      N%=0
      FOR I%=1 TO 100000000
        J%=I%
        H%=0
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          H%(H%)=K%:H%+=1
          J%=K%
          IF B%?J%=1 EXIT REPEAT
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=1:WHILE H%>0:H%-=1:B%?H%(H%)=1:ENDWHILE
      NEXT
      PRINT "Version 2: ";N% " in ";(TIME-T%)/100 " seconds."
 
      REM Version 3: Calc possible combinations (translation of C)
      REM ---------------------------------------------------------
      T%=TIME
      DIM B%(9*9*8):B%(0)=1
      FOR N%=1 TO 8
        FOR I%=9*9*N% TO 1 STEP -1
          FOR J%=1 TO 9
            S%=J%*J%
            IF S%>I% EXIT FOR
            B%(I%)+=B%(I%-S%)
          NEXT
        NEXT
      NEXT
 
      N%=0
      FOR I%=1 TO 9*9*8
        J%=I%
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          J%=K%
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=B%(I%)
      NEXT
      PRINT "Version 3: ";N% " in ";(TIME-T%)/100 " seconds."
 
      END