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?
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.
I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.
Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.
- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong