Skip to content

Project Euler Problem 12

October 20, 2011

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)
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: