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