euler012.hs

import Data.List (group)
--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?
--

main :: IO ()
main = print . take 1 $ triangleNumsWithMoreThan500Divisors

triangleNumsWithMoreThan500Divisors :: [Integer]
triangleNumsWithMoreThan500Divisors = triangleNumsWithMoreThanNDivisors nDivisors 500 

triangleNumsWithMoreThanNDivisors :: (Integer -> Int) -> Int -> [Integer]
triangleNumsWithMoreThanNDivisors f n = [x | x <- triangleNums, f x > n]


-- Drop the idea of a list comprehension entirely, previous version always had pairs in 
-- the concatable inner list. So just double the list length. This has slightly nicer 
-- memory usage and performance on the first run than the prime factorization approach.
-- But it stays the same on subsequent runs, whereas prime factorization drops dramatically
-- for both mem and speed. Which is clever.
numDivisors :: Integer -> Int
numDivisors n = 
		2 + 2 * length divs' 
	where 
		divs'					= filter ((==0) . mod n) [2..limit n]
		limit					= truncate . sqrt . fromIntegral

triangleNums :: [Integer]
triangleNums = map (sum . enumFromTo 1 ) [1..]


--- Evolution

-- My first try was this, but it is quite slow
--nDivs :: Integer -> Int
--nDivs n = 
--		2 + length divs' 
--	where 
--		divs' = concat [ [x, div n x] | x <- [2..limit n], mod n x == 0 ]
--		limit		= truncate . sqrt . fromIntegral


-- Borrowed this approach from the haskell euler wiki to prove to myself it could be fast
nDivisors :: Integer -> Int
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))

primes :: [Integer]
primes = 2 : primes'
  where 
    primes' = sieve [3,5..] 9 primes'
    sieve (x:xs) q ps@ ~(p:t)
       | x < q   = x : sieve xs q ps
       | otherwise = sieve [y | y <- xs, y `mod` p > 0] (head t^2) t

primeFactors :: Integer -> [Integer]
primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p * p > n      = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

--- Other approaches that didn't work because they were even slower
--ndivs' :: Integer -> Int 
--ndivs' n = 
--	length (tuple_to_list(unzip [(j, (div n j)) | j <- [i | i <- [1..lim n],(mod n i) == 0]] ))
--	where 
--		tuple_to_list xs = (fst xs) ++ (snd xs)
--		lim		= truncate . sqrt . fromIntegral
--
--divisors k = divisors' 2 k
--	where
--		divisors' n k 
--			| n * n > k			 = [k]
--			| n * n == k		 = [n, k]
--			| k `mod` n == 0 = (n:(k `div` n):result)
--			| otherwise			 = result
--					where 
--						result = divisors' (n+1) k
--
--divisors2 :: Integer -> [Integer]
--divisors2 k = k : (concatMap (\x -> [x, k `div` x]) $ filter (\x -> k `mod` x == 0) $ takeWhile (\x -> x*x <= k) [2..])