// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 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


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.
download arrowUse this link to get the Project Euler Solution Python 2.7 source.

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