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


(ns async-example.core
  (:require [clojure.math.numeric-tower :as math])
  (:use [criterium.core])
  (:gen-class))
(defn sum-sqr [digits]
  " Square sum of list of digits "
  (let [digits-sqr (fn [n]
                     (apply + (map #(* % %) digits)))]
    (digits-sqr digits)))
 
(defn get-digits [n]
  " Converts a digit to a list of digits (e.g. 545 -> ((5) (4) (5)) (used for squaring digits) "
  (map #(Integer/valueOf (str %)) (String/valueOf n)))
 
(defn -isNot89 [x]
  " Returns nil on 89 "
  (cond
    (= x 0) 0
    (= x 89) nil
    (= x 1) 0
    (< x 10) (recur (* x x))
    :else (recur (sum-sqr (get-digits x)))))
 
;; Cached version of isNot89 (i.e. remembers prevents inputs, and returns result by looking it up when input repeated)
(def isNot89 (memoize -isNot89))
 
(defn direct-method [ndigits]
  " Simple approach of looping through all the numbers from 0 to 10^ndigits - 1 "
  (->>
    (math/expt 10 ndigits)
    (range 0)									; 0 to 10^ndigits
    (filter #(isNot89 (sum-sqr (get-digits %))))	; filters out 89
    (count)										; count non-89
    (- (math/expt 10 ndigits))))				; count 89 (10^ndigits - (count 89))
 
 
(time (println (direct-method 8)))
 