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


var endsWith89 = Fn.new { |n|
    var digit = 0
    var sum = 0
    while (true) {
        while (n > 0) {
            digit = n % 10
            sum = sum + digit*digit
            n = (n/10).floor
        }
        if (sum == 89) return true
        if (sum == 1) return false
        n = sum
        sum = 0
    }
}
 
var start = System.clock
var sums = List.filled(8*81 + 1, 0)
sums[0] = 1
sums[1] = 0
var s = 0
for (n in 1..8) {
    for (i in n*81..1) {
        for (j in 1..9) {
            s = j * j
            if (s > i) break
            sums[i] = sums[i] + sums[i-s]
        }
    }
    if (n == 8) {
        var count89 = 0
        for (i in 1..n*81) {
            if (endsWith89.call(i)) count89 = count89 + sums[i]
        }
        System.print("There are %(count89) numbers from 1 to 100 million ending with 89.")
    }
}
System.print("Took %(((System.clock - start)*1000).round) milliseconds.")