Loading...
Project Euler 46: Find the smallest odd composite that cannot be written as the sum of a prime and twice a square
Project Euler 46 Problem Description
Project Euler 46: 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
Analysis
I love how Chris was tossing a bunch of stuff out there and then letting someone else prove him wrong, if, in fact, it really was wrong. His famous conjecture (every even integer greater than 2 can be expressed as the sum of two primes) has stood the test of time even today, but some doubt it may hold forever. Gotta love the guy.
I give it a try: pi is an irrational number, then it’s fractional part is infinite and represents every numerical sequence possible. This would include a series of 14s repeated an infinite number of times or s many time that enumerating them as fast as the smallest discreet division of time would outlast time itself. The same goes for 09876. And any infinite other number of endings. So, you see, it does repeat and you can claim any series you like. You’re welcome.
Sorry for the fill here, just needed a bit more content for this post since there’s not much to be said for explaining the solution.
Sieve primes as we go along (because we have no idea how many it’s going to take) using our knowledge from Problem 7 and check the proposal until a odd composite is found.
Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler Solution Python 2.7 source.
hey Mike, also referring to this section:
“f = 1
n += 3-f
f = -f
”
Q7 explains why when we search for a prime we can skip every second odd number. However, here we are searching for a composite number.
How do you know
Posted by cloops | October 30, 2015, 10:33 AMhi MIKE
you wrote
primes = set()
not
primes = set([3])
why?
If skip test 3?
if not any((n – 2 * i * i) in primes for i in range(1, n)):
Does it mean that
every odd composite number can be written as
N == 3 + 2 * i * i
i = sqrt((N – 3) / 2)
all i:
i == int(i)
but example 25:
25 = 3 + 22 = 3 + 2 * 11 => sqrt(11) not int
I don’t understand why 3 not in the primes set.
thanks!
Posted by nikola | October 21, 2015, 8:49 PMI am fascinated by the following sequence:
f = 1
n += 3-f
f = -f
What is the mathematical basis for being able to skip exactly every other odd number? Thanks…
Posted by Christopher Joyce | April 22, 2013, 10:00 AMCheck the bottom of problem 7 for a complete explanation of this sequence.
Posted by Mike | June 9, 2014, 11:56 PM