It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
let hasDivisor(n) = let upperBound = int64(sqrt(double(n))) [2L..upperBound] |> Seq.exists (fun x -> n % x = 0L) // need to consider negative values let isPrime(n) = if n <= 1L then false else not(hasDivisor(n)) // generate the sequence of odd composite numbers let oddCompositeNumbers = Seq.unfold (fun state -> Some(state, state+2L)) 9L |> Seq.filter (fun n -> not(isPrime n)) // generate the sequence of prime numbers let primeNumbers = Seq.unfold (fun state -> Some(state, state+2L)) 1L |> Seq.filter isPrime // function to check if a number can be written as the sum of a prime and twice a square let isSum(number) = primeNumbers |> Seq.takeWhile (fun n -> n < number) |> Seq.exists (fun n -> sqrt(double((number-n)/2L)) % 1.0 = 0.0) let answer = oddCompositeNumbers |> Seq.filter (fun n -> not(isSum(n))) |> Seq.head
All pretty straight forward here, the only slightly confusing part of this solution is how to determine if a number can be written as the sum of a prime and twice a square:
Odd Composite Number = Prime + 2 x n2 => n = sqrt((Odd Composite Number – Prime) / 2)
As you know Math.Sqrt works with a double and returns a double, hence to find out if n above is a whole number I had to check whether it divides by 1 evenly
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