// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (10 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 46 Solution

Project Euler 46 Solution

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×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: 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
download arrowUse 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.
|5777|

Comments

Project Euler 46 Solution last updated

Discussion

4 Responses to “Project Euler 46 Solution”

  1. 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 AM
  2. 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!

    Posted by nikola | October 21, 2015, 8:49 PM
  3. 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…

    Posted by Christopher Joyce | April 22, 2013, 10:00 AM

Post a comment