## 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×1^{2}

15 = 7 + 2×2^{2}

21 = 3 + 2×3^{2}

25 = 7 + 2×3^{2}

27 = 19 + 2×2^{2}

33 = 31 + 2×1^{2}

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.

#### Comments

*Project Euler 46 Solution last updated*

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

hi 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!

I 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…

Check the bottom of problem 7 for a complete explanation of this sequence.