Project Euler: Problem 92

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
85 89 145  42  20  4  16  37  58 89

Therefore 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 $k$-digit number $n=\sum_{i=0}^{k-1}d_{i}10^{i}$, where $d_{i}\in\left\{0,1,\ldots,9\right\}$, is bounded from above in the sum of its squared digits by $81k$. I claim that for $k> 3$, $81k$ has at most $k-1$ digits. Indeed,

$\displaystyle\log_{10}(81k)< 2+\log_{10}k$

So it suffices to show that $\log_{10}k\leq k-3$, when $k>3$, which we inductively do. The base case $k=4$ is obvious, so assume the result is true for all integers $. Then

$\displaystyle\log_{10}k<1+\log_{10}(k-1)\leq 1+(k-4)=k-3$

Hence, every four or more digit number arrives at a three-digit number in its chain. Since $81^{3}=324$, 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 IntsqDigitChain 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 $81k$ at $k=7$ to obtain $567$. We can easily determine how many integers in $[1,567]$ arrive at 89. So we just need to keep track of the occurrences of each $n\in [1,567]$ 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.