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
Enjoy what you’re reading? Subscribe to my newsletter and get more content on AWS and serverless technologies delivered straight to your inbox.
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.
In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. Including basic concepts, HTTP and event triggers, activities, design patterns and best practices.
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