Problem 92 on Project Euler concerns square digit chains: take a number, square each of its digits, sum the squares, repeat. As far as I can tell, square digit chains are useless aside from satisfying intellectual curiosity, as are many things in mathematics. The text of the problem is reproduced below.

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 32 13 10

11

8589145 42 20 4 16 37 5889Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

A -digit number , where , is bounded from above in the sum of its squared digits by . I claim that for , has at most digits. Indeed,

So it suffices to show that , when , which we inductively do. The base case is obvious, so assume the result is true for all integers . Then

Hence, every four or more digit number arrives at a three-digit number in its chain. Since , we need to verify that all integers from 1 to 324 have square digit chains arriving at either 1 or 89. You can do this in the language of your choice; I implemented my solution in Haskell.

```
import Data.Char
sqDigit :: Int -> Int
sqDigit x = sum $ map (^2) $ map digitToInt $ show x
sqDigitChain :: Int -> Int
sqDigitChain x = if (x == 1 || x == 89) then x
else sqDigitChain $ sqDigit x
all (\x -> (x==1) || (x==89)) (map sqDigitChain [1..324])
```

`sqDigit`

takes an integer as its argument and returns the sum of its squared digits. There are several ways to implement this; I chose to convert `Int `

to `String`

(a list of its digits as type `Char`

) then convert the elements of the list back to type `Int`

. `sqDigitChain `

takes an integer as its argument and checks if its 1 or 89. If it is, it returns x. Otherwise, it calls `sqDigit`

on x. Note that if there did exist an integer that did not arrive at either 1 or 89, then the recursion would have infinite depth.

The `all `

statement is a Boolean test of whether all the elements in the list returned by calling the function `sqDigitChain `

on each element of the list `[1..324]`

are 1 or 89. As I am typing this post, I realize that the `all `

statement is superfluous as the recursion would not have terminated if the test were false. For a more extensive discussion of the solution and its generalization, see Professor J. Wilson’s page.

Now to solving Problem 92. The key observation to my solution is that every positive integer below ten million (I took this to mean excluding ten million, but it doesn’t matter) reduces to a number between 1 and 567 after one iteration of the square digit chain. This is immediate from evaluating at to obtain . We can easily determine how many integers in arrive at 89. So we just need to keep track of the occurrences of each in the list `map sqDigit [1..(10^7 - 1)]`

.

```
import Data.Char
sqDigit :: Int -> Int
sqDigit x = sum $ map (^2) $ map digitToInt $ show x
sqDigitChain :: Int -> Int
sqDigitChain x = if (x == 1 || x == 89) then x
else sqDigitChain $ sqDigit x
main = print(n - length xs)
where
xs = filter (\x -> elem x l) (map sqDigit [1..n])
n = (10^7 - 1)
l = [t | t <- [1..567], sqDigitChain t == 1]
```

```
```

For a faster solution which uses the observation that the sum of squared digits is invariant under permutation to reduce the number of computations, see MathBlog.