Haskell function taking a long time to process

Question

Hi

I am doing question 12 of project euler where I must find the first triangle number with 501 divisors. So I whipped up this with Haskell:

divS n = [ x | x <- [1..(n)], n `rem` x == 0 ]
tri n = (n* (n+1)) `div` 2
divL n = length (divS (tri n))
answer = [ x | x <- [100..] ,  501 == (divL x)]

The first function finds the divisors of a number.

The second function calculates the nth triangle number

The 3rd function finds the length of the list that are the divisors of the triangle number

The 4th function should return the value of the triangle number which has 501 divisors.

But so far this run for a while without returning a result. Is the answer very large or do I need some serious optimisation to make this work in a realistic amount of time?

Answer 1

Some optimization tips:

• check for divisors between 1 and sqrt(n). I promise you won't find any above that limit (except for the number itself).
• don't build a list of divisors and count the list, but count them directly.

Answer 2

You need to use properties of divisor function: http://en.wikipedia.org/wiki/Divisor%5Ffunction

Notice that n and n + 1 are always coprime, so that you can get d(n * (n + 1) / 2) by multiplying previously computed values.

Answer 3

It is probably faster to prime-factorise the number and then use the factorisation to find the divisors, than using trial division with all numbers <= sqrt(n).

The Sieve of Eratosthenes is a classical way of finding primes, which may be modified slightly to find the number of divisors of each natural number. Instead of just marking each non-prime as "not prime", you could make a list of all the primes dividing each number. You can then use those primes to compute the complete set of divisors, or just the number of them, since that is all you need.

Another variation would be to mark not just multiples of primes, but multiples of all natural numbers. Then you could simply use a counter to keep track of the number of divisors for each number.

You also might want to check out The Genuine Sieve of Eratosthenes, which explains why trial division is way slower than the real sieve.

Last off, you should look carefully at the different kinds of arrays in Haskell. I think it is probably easier to use the ST monad to implement the sieve, but it might be possible to achieve the correct complexity using accumArray, if you can make sure that your update function is strict. I have never managed to get this to work though, so you are on your own here.

Answer 4

If you were using C instead of Haskell, your function would still take much time.

To make it faster you will need to improve the algorithm, using suggestions from the above answers. I suggest to change the title and question description accordingly. Following that I'll delete this comment.

If you wish, I can spoil the problem by sharing my solution.

For now I'll give you my top-level code:

main =
  print .
  head . filter ((> 500) . length . divisors) .
  map (figureNum 3) $ [1..]

The algorithmic improvement lies in the divisors function. You can further improve it using rawicki's suggestion, but already this takes less than 100ms.