## Project Euler 46: Find the smallest odd composite that cannot be written as the sum of a prime and twice a square

#### Problem Description

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: If pi never repeats, then it’s infinite and represents every numerical sequence possible. This would include a digital representation of a newspaper article that mentions the discovery of a repeating pi. Therefore, pi does, at some point, repeat.

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.

Generate primes as needed (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.

#### Project Euler 46 Solution

Runs < 0.001 seconds in Python 2.7.```
n = 5
f = 1
primes = set()
while True:
if all(n % p for p in primes):
primes.add(n)
else:
if not any((n-2*i*i) in primes for i in range(1, n)):
break
n += 3-f
f = -f
print "Project Euler 46 Solution =", n
```

Use this link to get the Project Euler 46 Solution Python 2.7 source.#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### 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.