Project Euler — Problem 47 Solution

Problem

The first two con­sec­u­tive num­bers to have two dis­tinct prime fac­tors are:

14 = 2 x 7

15 = 3 x 5

The first three con­sec­u­tive num­bers to have three dis­tinct prime fac­tors are:

644 = 2² x 7 x 23

645 = 3 x 5 x 43

646 = 2 x 17 x 19

Find the first four con­sec­u­tive inte­gers to have four dis­tinct primes fac­tors. What is the first of these num­bers?

Solution

let hasDivisor(n) =
    let upperBound = bigint(sqrt(double(n)))
    [2I..upperBound] |> Seq.exists (fun x -> n % x = 0I)

let isPrime(n) = if n = 1I then false else not(hasDivisor(n))

let naturalNumbers = Seq.unfold (fun state -> Some(state, state+1I)) 1I

// define the sequence of prime numbers
let primeSeq = naturalNumbers |> Seq.filter isPrime |> Seq.cache

// recursive function to find the prime denominators for a number n
let rec getPrimeFactors denominators n =
    if n = 1I then denominators
    else
        let denominator = primeSeq |> Seq.filter (fun x -> n % x = 0I) |> Seq.head
        getPrimeFactors (denominators @ [denominator]) (n/denominator)

// curry the getPrimeDenominators function to start with an empty list
let primeFactors = getPrimeFactors []

// function to get the number of distinct prime factors a number has
let distinctPrimeFactorsCount n = primeFactors n |> Seq.distinct |> Seq.length

// define the sequence of numbers with exactly 4 distinct prime factors
let seq = naturalNumbers |> Seq.filter (fun n -> distinctPrimeFactorsCount n = 4) |> Seq.cache

let answer =
    seq
    |> Seq.windowed 4
    |> Seq.filter (fun l -> Seq.max (l) - Seq.min (l) = 3I)
    |> Seq.head
    |> Seq.head

Whilst on the sur­face this isn’t a very dif­fi­cult prob­lem to solve, the biggest chal­lenge I had was in mak­ing sure the solu­tion runs in a rea­son­able time hence note the var­i­ous places where I used Seq.cache to help improve the per­for­mance of this code.