# Fast way to count the numbers that are divisible by their own sum of digits inside a range

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]  ## 2 Answers Compile without profiling, but with optimizations turned on. bissbook:divSumDigits bisserlis$ ghc -prof -fprof-auto -rtsopts original.hs
[1 of 1] Compiling Main             ( original.hs, original.o )
bissbook:divSumDigits bisserlis$./original +RTS -s 806095 44,577,697,768 bytes allocated in the heap 81,431,504 bytes copied during GC 62,504 bytes maximum residency (2 sample(s)) 23,392 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 85945 colls, 0 par 0.48s 0.57s 0.0000s 0.0001s Gen 1 2 colls, 0 par 0.00s 0.00s 0.0002s 0.0002s INIT time 0.00s ( 0.00s elapsed) MUT time 22.36s ( 22.79s elapsed) GC time 0.48s ( 0.57s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 22.85s ( 23.35s elapsed) %GC time 2.1% (2.4% elapsed) Alloc rate 1,993,498,737 bytes per MUT second Productivity 97.9% of total user, 95.8% of total elapsed bissbook:divSumDigits bisserlis$ rm *.hi *.o
bissbook:divSumDigits bisserlis$ghc -O2 original.hs [1 of 1] Compiling Main ( original.hs, original.o ) Linking original ... bissbook:divSumDigits bisserlis$ ./original +RTS -s
806095
12,176,087,768 bytes allocated in the heap
4,273,680 bytes copied during GC
44,416 bytes maximum residency (2 sample(s))
21,120 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)

Tot time (elapsed)  Avg pause  Max pause
Gen  0     23449 colls,     0 par    0.09s    0.11s     0.0000s    0.0001s
Gen  1         2 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    2.87s  (  2.93s elapsed)
GC      time    0.09s  (  0.11s elapsed)
EXIT    time    0.00s  (  0.00s elapsed)
Total   time    2.96s  (  3.04s elapsed)

%GC     time       3.0%  (3.7% elapsed)

Alloc rate    4,237,427,802 bytes per MUT second

Productivity  97.0% of total user, 94.6% of total elapsed


(Note the Total time lines, 22.85s and 2.96s.)

I can't appreciably increase the performance any further, but I do have a couple stylistic notes.

Data.Char provides a function digitToInt :: Char -> Int, which makes writing digits much easier.

import Data.Char (digitToInt)

digits :: Int -> [Int]
digits = map digitToInt . show


No need to use list comprehensions and boolean double-checking in rangeDivisibleSumDigits, just write it as a filter on the range.

rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits start end = filter isDivisibleSumDigits [start..end]


sumDigits and lengthRangeDivisibleSumDigits are unnecessary functions, their names are pretty much as long as their implementations! They clutter up the top-level, they don't do anything surprising or interesting, I'd just use their implementations wherever you need to instead of adding another function to your mental burden.

• Stylistic notes are always appreciated. Do you have any ideas on the algorithms part? Commented Apr 1, 2015 at 2:42
• Actually this would be a perfect problem for parallelization, which should give you a linear speedup in the number of processors. I'd have to pull down my copy of Parallel and Concurrent Programming in Haskell for a refresher before taking a stab at it though. Commented Apr 1, 2015 at 3:21

It's not necessarily convert a number to a string (or list) to evaluate sum of digits, so try to rewrite your new code as:

-- Returns the sum of digits of a positive integer
sumDigits :: Int -> Int
sumDigits n = let (rest,lastDigit) = quotRem n 10 in if n == 0 then 0 else lastDigit + sumDigits rest

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n rem (sumDigits n) == 0

• Your code didn't work as it was written. I've modified it slightly to this sumDigits :: Int -> Int sumDigits n = if n == 0 then 0 else lastDigit + sumDigits rest where (lastDigit, rest) = quotRem n 10, but my system started to slow down when I ran it, so I stopped the execution. Commented Apr 1, 2015 at 10:05
• Oh! I'm sorry, my code has mistake due to my experiments with it. True line is sumDigits n = let (rest,lastDigit) = quotRem n 10 in if n == 0 then 0 else lastDigit + sumDigits rest. Your modification is also right. Commented Apr 1, 2015 at 10:09