Trying to work out Problem 12 on Project Euler in Haskell.
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...Let us list the factors of the first seven triangle numbers:
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 value of the first triangle number to have over five hundred divisors?
My solution works fine for small numbers of divisors (e.g. given 5, it returns 28), but when 500 is input, 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 might be doing wrong? Thank you!
Another problem is that your generation of the triangular numbers which, while correct, is very inefficient. For instance, to compute the 11th number you are summing [1..11], and then to compute the 12th number you are summing [1..12] which doesn't use the results of the previous computation.
As I mentioned in my comment, you can compute the n-th triangular number directly using n*(n+1)/2. However, even if you didn't know this formula you can take advantage of the similarity between consecutive triangular numbers by using a recursion like this:
triangulars = go 1 2
where go s n = s : go (s+n) (n+1)
This kind of recursion is also captured by the scanl function:
triangulars = scanl (+) 1 [2..]