#### Problem

The first two

consecutive numbers to have two distinct prime factors are:

14 = 2 x 7

15 = 3 x 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² x 7 x 23

645 = 3 x 5 x 43

646 = 2 x 17 x 19

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

#### 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 surface this isn’t a very difficult problem to solve, the biggest challenge I had was in making sure the solution runs in a reasonable time hence note the various places where I used Seq.cache to help improve the performance of this code.

Subscribe to my newsletter and get new contents delivered straight to your inbox :-)