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


gen: function [n][
    result: n
    while [not? in? result [1 89]][
        s: new 0
        loop digits result 'd ->
            's + d*d
        result: s
    ]
    return result
]
 
chainsEndingWith89: function [ndigits][
    [prevCount,currCount]: #[]
    loop 0..9 'i -> prevCount\[i*i]: 1
 
    res: new 0
 
    loop 2..ndigits 'x [
        currCount: #[]
        loop prevCount [val,cnt][
            v: to :integer val
            loop 0..9 'newDigit [
                mm: v + newDigit*newDigit
                if not? key? currCount mm -> currCount\[mm]: 0
                currCount\[mm]: currCount\[mm] + cnt
            ]
        ]
        prevCount: currCount
    ]
    loop currCount [val,cnt][
        v: to :integer val
        if and? [v <> 0] [89=gen v] ->
            'res + cnt
    ]
    return res
]
 
print [
    "Number chains for integers <100000000 that end with an 89 value:" 
    chainsEndingWith89 8
]