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.
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 -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
String (a list of its digits as type
Char) then convert the elements of the list back to type
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.
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.