Geek Answers Handbook

Efficient Haskell Divisor Detection

Trying to solve Problem 12 at Project Euler in Haskell.

A sequence of triangular numbers is generated by adding a natural number.

Thus, the 7th number of the triangle will be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten members will be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

We list the factors of the first seven numbers of the triangle:

 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors.

What is the meaning of the first number of triangles having more than five hundred dividers?

My solution works fine for small numbers of dividers (for example, given 5, it returns 28), but when 500 is entered, it seems to hang indefinitely.

 -- Lazily generates infinite list of triangle numbers. triangleNumbers :: [Integer] triangleNumbers = map (\x -> sum [1..x]) [1..] -- Given a number, returns the a tuple of how many divisors it has and the number. numDivisors :: Integer -> (Int, Integer) numDivisors num = (length [x | x <- [1..num], num `mod` x == 0], num) p12 :: Integer p12 = snd $ head $ filter (\x -> fst x > 500) $ map numDivisors triangleNumbers

Do you have any idea what I can do wrong? Thanks!

+4
source share
2 answers

Another problem is that your generation of triangular numbers, which, being correct, is very inefficient. For example, to calculate the 11th number, you add [1..11], and then to calculate the 12th number, which you add [1..12], which does not use the results of the previous calculation.

As I mentioned in my comment, you can directly calculate the nth triangular number using n*(n+1)/2 . However, even if you did not know this formula, you can take advantage of the similarities between consecutive triangular numbers using recursion like this:

 triangulars = go 1 2 where go sn = s : go (s+n) (n+1)

This recursion is also captured by the scanl function:

 triangulars = scanl (+) 1 [2..]
+7
source

The problem is that the search function for the number of divisors is very slow, as it checks all numbers. There are much more efficient features. See For example the answers to this question in StackOverflow: Two simple codes for generating number divisors. Why is recursive faster? .

But if you google a little, you can find many other algorithms.

+3
source

More articles:


All Articles