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 →1→1
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 <k. 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.

Advertisements
This entry was posted in Haskell, Problem Solving, Progamming and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s