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


with javascript_semantics
constant MAXINT = power(2,iff(machine_bits()=32?53:64))
 
procedure main(integer limit)
    sequence sums = repeat(0,limit*81+1)
    sums[1] = 1
    for n=1 to limit do
        for i=n*81 to 1 by -1 do
            for j=1 to 9 do
                integer s = j*j, i1= i+1, i1ms = i1-s
                if s>i then exit end if
                sums[i1] += sums[i1ms]
            end for
        end for
        atom count89 = 0
        for i=1 to n*81 do
            integer r, digit, w = i, i1 = i+1
            while w!=1 do
                r = 0
                while w!=0 do
                    digit = mod(w,10)
                    r += digit*digit
                    w = floor(w/10)
                end while
                if r=89 then
                    count89 += sums[i1]
                    if count89>MAXINT then
                        printf(1,"counter overflow for 10^%d\n",n)
                        return
                    end if
                    exit
                end if
                w = r
            end while
        end for
        printf(1,"There are %d numbers from 1 to 10^%d ending with 89\n",{count89,n})
    end for
end procedure
 
atom t0 = time()
main(20)
?time()-t0
