### 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
getFactors (Set.add (x*x) acc) xs
elif n % x = 0 then
getFactors (Set.add x acc) xs
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])
|> Seq.head
#time
``````

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.

Next, we filter out any values that don't have the required distinct prime factors and return the head of the resulting sequence. That is the answer.

Other Posts in This Series