# Project Euler Problem 12

Project Euler Problem 12 seems can be solved by a brute force: produce a sequence of triangle numbers until the member having number of divisors greater, than 500.

Googling for “number of all divisors of an integer” brings us to the topic of Divisor function: *if a number is present as a multiple of its prime factors with correspondent exponents, then the number of all its divisors would be equal to the multiple of all prime factor exponents, each increased by 1.*

We can revisit the process of factorization that we performed for Project Euler Problem 3 solution. But now we would need to present the factorization as a list of tuples, each carrying a prime divisor and correspondent exponent. For example, **12 -> [(2,2);(3,1)]**. From here we can easily can find number of divisors that is equals to **(2+1)*(1+1) = 6**. **12** has divisors **1,2,3,4,6,12**; six of them, indeed.

The whole solution is:

// Build a sequence of triangle numbers within the integer field let triangles = Seq.unfold (fun (x, acc) -> Some (acc + x, (x + 1, acc + x))) (1,0) // Find prime factors of a number within the integer field as // a sequence of tuples (primeFactor, exponent) let primeFactors number = let rec factorize number factor answer = if number <= factor then factor :: answer elif number % factor = 0 then factorize (number/factor) factor (factor :: answer) else factorize number (factor+1) answer factorize number 2 [] |> Seq.countBy id // Find number of all divisors of an integer // After prime factorization the sought value equals to // multiple of prime exponents, each incremented by 1, // reference: http://en.wikipedia.org/wiki/Divisor_function let numberOfDivisors number = primeFactors number |> Seq.fold (fun acc (factor, exp) -> acc * (exp + 1)) 1 // Finally, solve the Problem 12 let problem012 () = triangles |> (Seq.tryFind (fun t -> (numberOfDivisors t) > 500) >> Option.get)