### The Problem

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

• 14 = 2 × 7
• 15 = 3 × 5

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

• 644 = 2² × 7 × 23
• 645 = 3 × 5 × 43
• 646 = 2 × 17 × 19.

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

### The Solution

Once again, we need primes. Lots of them. So we'll start by stealing the `getSomePrimes` function from yesterday.

``````let intsqrt i = int(sqrt(float i))

let isPrime i =
if i <= 1 then false
elif i = 2 then true
elif (i &&& 1) = 0 then false
else
let sr = intsqrt i
seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime i =
match i with
| i when isPrime i -> i
| i -> nextPrime (i + 1)

let getSomePrimes num =
let primeGenerator (candidate,count) =
if count > num then
None
elif candidate = 2 then
Some(2,(3,count+1))
else
let next = nextPrime candidate
Some(next,(next+2,count+1))

Seq.unfold primeGenerator (2,1)

let factors = getSomePrimes 1000 |> List.ofSeq
``````

So how many primes do we need? As with yesterday's problem, I don't know. I'm going to pick 100 because "it sounds good" and adjust later if I need to.

Why 100? We're looking for 4 prime factors. If we generate 1000 primes and take the last 4, we get:

• 7883
• 7901
• 7907
• 7919

If you multiply those 4 numbers together you get 3,899,919,746,694,739. That's way out of 32-bit integer territory. Are we willing to bet that the answer is less than that? Yes, we are.

Now we'll write a function to get the prime factors of a number.

``````let f n =
let rec getFactors (acc : Set<int>) (factors : int list) =
match factors with
| [] -> acc
| x::xs ->
if n % (x*x) = 0 then
elif n % x = 0 then
else
getFactors acc xs

getFactors Set.empty<int> factors
``````

The function `f` takes a number `n` and returns its prime factors.

The recursive internal `getFactors` function simply starts with a list of factors and tests them all to see if they are factors of `n`. The problem definition clearly shows that squares of primes are allowed to be counted as a "distinct factor" so we account for that case.

Now we need a function to look at a number and see if it has the specified number of distinct prime factors. In fact, we need to know if several consecutive numbers have that property, so we'll take a list of numbers as input instead of just a single number. We need to verify that:

• Each number has 4 distinct factors
• The set of 4 numbers has 16 distinct factors

The problem definition doesn't come right out and say that "distinct prime factors" means "distinct across the 4 consecutive numbers", but you don't get the right answer without accounting for that.

``````[<Literal>]
let factorCount = 4

[<Literal>]
let requiredDistinct = 16

let haveDistinctPrimeFactors numbers =
let numbersFactors =
numbers
|> Seq.map f
|> List.ofSeq

let distinctCount =
numbersFactors
|> List.reduce (fun acc elem -> acc + elem)
|> Set.count

(numbersFactors |> List.forall (fun x -> (Set.count x) = factorCount)) &&
(distinctCount = requiredDistinct)
``````

The `haveDistinctPrimeFactors` function starts by computing a couple of values.

`numbersFactors` becomes a list of factors for each of the input `numbers`.

`distinctCount` is the count of the distinct factors across all 4 input `numbers`. The factors are of type `Set` so when we add them together, we wind up with the union of all 4 sets. Thus, the `count` of that union is the number of distinct factors.

If the count of distinct factors for each input is 4 and the count of distinct factors is `requiredDistinct` then the function returns `true`; otherwise, it returns `false`.

Now we can solve the problem:

``````#time
Seq.unfold (fun state -> Some(state, state+1)) 647
|> Seq.filter (fun x -> haveDistinctPrimeFactors [x..x+3])
We start by using `Seq.unfold` to generate an infinite sequence of numbers starting at 647. The problem definition says that 644..646 is the first set of consecutive numbers of have 3 prime factors, so we'll start looking right after that.