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 scala.annotation.tailrec
 
object Euler92 extends App {
  override val executionStart = compat.Platform.currentTime
 
  @tailrec
  private def calcRec(i: Int): Int = {
 
    @tailrec
    def iter0(n: Int, total: Int): Int =
      if (n > 0) {
        val rest = n % 10
        iter0(n / 10, total + rest * rest)
      }
      else total
 
 
    if (i == 89 || i == 1) i else calcRec(iter0(i, 0))
  }
 
 
  private def calcConv(i: Int) = {
    var n: Int = i
    while (n != 89 && n != 1) {
      var total = 0
      while (n > 0) {
        val x = n % 10
        total += (x * x)
        n /= 10
      }
      n = total
    }
    n
  }
 
  println((1 until 100000000).par.count(calcConv(_) == 89))
  println(s"Runtime conventional loop.[total ${compat.Platform.currentTime - executionStart} ms]")
 
  val executionStart0 = compat.Platform.currentTime
  println((1 until 100000000).par.count(calcRec(_) == 89))
  println(s"Runtime recursive loop.   [total ${compat.Platform.currentTime - executionStart0} ms]")
 
}