{- 
  
  Euler #12 in Haskell

  Problem 12
  """
  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 the 7th triangle number, 28, is the first triangle number 
  to have over five divisors.

  Which is the first triangle number to have over five-hundred divisors?")
  """

  This program was created by Hakan Kjellerstrand (hakank@gmail.com)
  Also see my Haskell page: http://hakank.org/haskell/
  
  
-}

import Data.List
import HakankUtils (numDivisors)

-- allFactors' _ 1 _ = []
-- allFactors' n m d | m > 1 = -- if d > 1+(n `div` 2) then
--                           if d > n then
--                             [m]
--                           else if m `mod` d == 0 then
--                             d : allFactors' n (m `div` d) d
--                           else
--                             allFactors' n m (d+1)
-- allFactors n = allFactors' n n 2


-- Count the number of occurrences of elements in list (x:xs)
-- collect xs =  map (\i sum (==i) xs ) nub xs

-- divisors1 n = 1 : [i | i <- [2..1+(n `div` 2)], n `mod` i == 0 ] ++ [n]

-- Brute force. Quite elegant but way too slow, especially since divisors is so slow...
-- And this does not do the full thing, i.e. calculate the next value.
-- See euler12b for a complete and a much faster variant.
-- euler12a = takeWhile (\n -> length (divisors1 n) <= 500) $ scanl1 (+) [1..]

euler12b = last t2 - (foldr1 (-) t2) + 1
           where
             t = takeWhile (\n -> numDivisors n <= 500) $ scanl1 (+) [1..]
             len = length t
             t2 = drop (len-2) t


-- Shorter, about the same time as euler12b
euler12c = head $ dropWhile (\n -> numDivisors n <= 500) $ scanl1 (+) [1..]
                  
main = do
         -- print euler12a -- Too slow
  
         -- print euler12b -- (0.44 secs, 338,453,792 bytes)

         print euler12c -- (0.44 secs, 337,760,376 bytes)