Check if an integer equals the sum of its digits to the fifth power

Question

I can do this in one line in Python:

sum([i for i in range(9,9999999) if i == sum([int(x)**5 for x  in str(i)])])

Not very fast, but works nicely. I thought it might be quicker to do it in Haskell, a language I'm quite new to:

-- helper func
toDigits    :: Int -> [Int]
toDigits 0 = []
toDigits x = toDigits (x `div` 10) ++ [x `mod` 10]

isSumofFifth n = n == sum (map (^5) (toDigits n))
sum (filter isSumofFifth [9..9999999])

But it seems as slow, or even slower (I haven't done exact profiling).

I realise I could optimise it with a more refined upper bound, but aside from that, is there a better way to write this in Haskell?

Answer 1

I agree with Glorfindel that the best result is achieved by thinking of the problem in a different way. Still, improvements can be made to the code that speed it up by about a factor of 3:

toDigits :: Int -> [Int]
toDigits 0 = []
toDigits x = let (d, m) = x `divMod` 10
             in d `seq` m : toDigits d

isSumofFifth n = n == sum (map (^5) (toDigits n))

main :: IO ()
main = do
  let result = sum (filter isSumofFifth [9..9999999])
  putStrLn $ "Result is: " ++ show result

First the divMod function is used to compute the quotient and modulus in a single step rather than separately, which saves time, as they are expensive operations.

More importantly, the toDigits function can be changed to generate the digits in reverse order, which is fine for this problem, and thereby avoid a series of concatenations. In this code, each digit is generated as needed, while in the original, the first digit can't be read until all of the others are generated and then concatenated together from a series of single-element lists. This causes a lot of copying.

Another small speed-up is achieved by the seq operator, which insures that d is fully calculated when m is returned, avoiding extra processing.

Answer 2

I'm not familiar with either Haskell or Python, but I'd like to challenge the way you're tackling this problem.

First of all, seven 9s will give you a sum of 7 * 9⁵ = 413343. That's six digits, so searching up to one million (instead of ten million) would already be enough.

But we can do better. Instead of analyzing all million numbers, you can reduce that number by realizing that 123456 will give the same sum as 654321. The order of the digits doesn't matter. The sums you actually need to compute are the combinations with repetition; there are 'only' 5005 of them. Python has a standard function to list them in the itertools package, e.g. combinations_with_replacement('0123456789', 6).

When you have computed the sum of the combination, you need to sort its digits and check if they match the combination. If so, the sum is a true positive and can be added to the list.

Answer 3

Actually, you did a much better job with your first version than you seem to think.

Your Python version takes about 23 seconds (Python 3) on my desktop. If I take your original program:

toDigits    :: Int -> [Int]
toDigits 0 = []
toDigits x = toDigits (x `div` 10) ++ [x `mod` 10]

isSumofFifth n = n == sum (map (^5) (toDigits n))
main = print $ sum (filter isSumofFifth [9..9999999])

and, remembering that Haskell is a compiled language, take care to compile it with optimizations ghc -O2 FindFives.hs (using GHC 8.6.4), I find the executable runs in about 2.7 seconds, so about ten times faster than the Python version.

So, Important Note: Never benchmark Haskell code with the GHCi interpreter or using runghc! The performance results will be completely meaningless.

Also, since this is Code Review, let me point out that you can write your Haskell version in much the same form as the Python version:

answer :: Int
answer =   sum [i |   i <-     [9..9999999],   i == sum [d^5 | d <- toDigits i]]
-- Python: sum([i for i in range(9,9999999) if i == sum([int(x)**5 for x  in str(i)]

Using your original toDigits, this still runs in about 2.7 seconds, but it's probably easier to read.

@Truman has covered the main ways to speed up your toDigits. The version in that answer gives a runtime of about 1 second.

You can do a little better. The version:

toDigits :: Int -> [Int]
toDigits = unfoldr go
  where go 0 = Nothing
        go x = Just $ swap $ x `quotRem` 10

gets it down to about 700ms because unfoldr allows the creation of the actual digits list to be optimized away.