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


import BigInt
 
func is89(_ n: Int) -> Bool {
  var n = n
 
  while true {
    var s = 0
 
    repeat {
      s += (n%10) * (n%10)
      n /= 10
    } while n > 0
 
    if s == 89 {
      return true
    } else if s == 1 {
      return false
    }
 
    n = s
  }
}
 
func iterSquare(upToPower pow: Int) {
  var sums = [BigInt](repeating: 0, count: pow * 81 + 1)
  sums[0] = 1
 
  for n in 1...pow {
    var i = n * 81
 
    while i > 0 {
      for j in 1..<10 {
        let s = j * j
        guard s <= i else { break }
        sums[i] += sums[i-s]
      }
 
      i -= 1
    }
 
    var count89 = BigInt(0)
 
    for x in 1..<n*81 + 1 {
      guard is89(x) else { continue }
 
      count89 += sums[x]
    }
 
    print("1->10^\(n): \(count89)")
  }
}
 
iterSquare(upToPower: 8)