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 -&gt; [Int]
digitsRev i = case i of
    0 -&gt; []
    _ -&gt; lastDigit : digitsRev rest
where (rest, lastDigit) = quotRem i 10

-- Returns the digits of a positive integer as a list.
digits :: Int -&gt; [Int]
digits = reverse . digitsRev

-- Returns the sum of digits of a positive integer
sumDigits :: Int -&gt; Int
sumDigits = sum . digits

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise.
isDivisibleSumDigits :: Int -&gt; 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 -&gt; Int -&gt; [Int]
rangeDivisibleSumDigits range_start range_end =
    [n | n &lt;- [range_start..range_end], isDivisibleSumDigits n == True]

-- Returns the length of the list returned by rangeDivisibleSumDigits
lengthRangeDivisibleSumDigits :: Int -&gt; Int -&gt; 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 -&gt; [Int]
digits = map digitToInt . show

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise
isDivisibleSumDigits :: Int -&gt; 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 -&gt; Int -&gt; [Int]
rangeDivisibleSumDigits start end = filter isDivisibleSumDigits [start..end]
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 )
Linking original ...
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 -&gt; Int, which makes writing digits much easier.

import Data.Char (digitToInt)

digits :: Int -&gt; [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 -&gt; Int -&gt; [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.