Inspired by this question on Stack Overflow, I wrote a function that returns the length of a list made of numbers that are divisible by their own sum of digits inside a range:
-- Returns the digits of a positive integer as a list, in reverse order.
-- This is slightly more efficient than in forward order.
digitsRev :: Int -> [Int]
digitsRev i = case i of
0 -> []
_ -> lastDigit : digitsRev rest
where (rest, lastDigit) = quotRem i 10
-- Returns the digits of a positive integer as a list.
digits :: Int -> [Int]
digits = reverse . digitsRev
-- Returns the sum of digits of a positive integer
sumDigits :: Int -> Int
sumDigits = sum . digits
-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise.
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n `mod` sumDigits n == 0
-- Returns a range of positive integers in which every element is divisible by
-- the sum of it's digits. Includes the end of the range.
rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits range_start range_end =
[n | n <- [range_start..range_end], isDivisibleSumDigits n == True]
-- Returns the length of the list returned by rangeDivisibleSumDigits
lengthRangeDivisibleSumDigits :: Int -> Int -> Int
lengthRangeDivisibleSumDigits range_start range_end =
length $ rangeDivisibleSumDigits range_start range_end
Then I used this function inside a main function, like this:
main = putStrLn $ show $ lengthRangeDivisibleSumDigits 1 10000000
According to the file generated by profiling the program (compiling like this: ghc -prof -fprof-auto -rtsopts Main.hs
and executing like this: ./Main +RTS -p
) it took 14.36 seconds to execute main
. That's slow.
Do you have ideas on a faster way to perform the task carried out by this function?
Edit
Thanks to @bisserlis 's answer below, now the code reads:
-- Returns the digits of a positive integer as a list.
digits :: Int -> [Int]
digits = map digitToInt . show
-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n `mod` (sum (digits n)) == 0
-- Returns a range of positive integers in which every element is divisible by
-- the sum of it's digits. Includes the end of the range.
rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits start end = filter isDivisibleSumDigits [start..end]