Yacoby's Wanderings | Problem 12

Project Euler - Problem 12

What is the value of the first triangle number to have over five hundred divisors?

My brute force solution took a couple of seconds (compiled with -O3), but trying to come up with a neater solution, I came across the fact that the sum of the exponents, each incremented by one gives the number of factors. E.g. The prime factors of 108 are 2², 3³. Therefore the number of factors of 108 = (2+1)(3+1) = 12

Unfortunately, after implementing this, I only gained about 200ms (10%) on the previous version. I am fairy sure there are some better optimizations that I could have done.

Original Solution:

sumTo :: Int -> Int
sumTo n = (n*(n+1))`div`2

numFactors :: Int -> Int
numFactors num =  ( doNumFactors num $ sqrtInt num ) * 2
		where
			sqrtInt :: Int -> Int
			sqrtInt n = floor ( sqrt ( fromIntegral n ) ) 

			doNumFactors :: Int -> Int -> Int
			doNumFactors num 0 		= 0
			doNumFactors num current = (iIsFactor num current)  + (doNumFactors num $ current - 1)
			
			iIsFactor :: Int -> Int -> Int
			iIsFactor n f = fromEnum ((n `mod` f) == 0)


--Like Data.list.find, but it doesn't use maybe. This doesn't matter as we are using lists [1..∞]
takeFirstWhere :: (a -> Bool) -> [a] -> a
takeFirstWhere f (x:xs) | f(x)			= x
			| otherwise		= takeFirstWhere f xs

solve :: Int -> Int
solve limit = takeFirstWhere (\x ->  ( numFactors $ x ) > limit ) [ sumTo x | x <- [1..] ]

Updated numFactors function:

numFactors :: Int -> Int
numFactors n = doCalc $ getListCounts $ getPrimeFactors n
		where
			doCalc l = foldl1 (*) $ map (+1) l


--Returns an array of counts of every value in the given list
--So getListCounts [2,2,2,1] == [3,1]
getListCounts :: [Int] -> [Int]
getListCounts [] = []
getListCounts l = countWhere (== ( head l ) ) l : ( getListCounts $ filter(/= (head l) ) l )

countWhere :: ( a -> Bool) -> [a] -> Int
countWhere f l = foldl (\x y -> x + (fromEnum $ f y) ) 0 l

getPrimeFactors :: Int -> [Int]
getPrimeFactors 1 = []
getPrimeFactors n =  prime : ( getPrimeFactors $ n `div` prime )
	where
		prime :: Int
		prime = takeFirstWhere (\x -> n `mod` x == 0 ) [2..]