Home > Project Euler, python > Problem euler #46

Problem 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?


import time

ts = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True

def is_odd_goldbach(n):
    for prime in PRIMES:
        for m in xrange(1, 50):
            if n == prime + 2*m**2:
                return True
    return False

def odds_generator():
    n = 35
    while True:
        if not is_prime(n):
            yield n
        n += 2

PRIMES = [i for i in xrange(3, 10000) if is_prime(i)]

for n in odds_generator():
    if not is_odd_goldbach(n):
        res = n

print "problem euler 41: {} \nelapsed time: {}sec".format(res, time.time() - ts)

Categorie:Project Euler, python
  1. gennaio 6, 2013 alle 4:32 am

    I absolutely love your blog.. Excellent colors &
    theme. Did you develop this web site yourself?
    Please reply back as I’m planning to create my very own website and would like to find out where you got this from or just what the theme is called. Appreciate it!

  2. marzo 8, 2013 alle 4:51 am

    Aw, this was a really good post. Taking a few minutes and actual effort to make a top notch
    article… but what can I say… I procrastinate a whole lot and don’t manage to get nearly anything done.

  3. giugno 6, 2014 alle 4:16 am

    Good post but I was wanting to know if you could write
    a litte more on this subject? I’d be very grateful if you could elaborate a little bit more.
    Many thanks!

  4. settembre 10, 2014 alle 2:40 am

    Hi, always i used to check web site posts here early in the daylight,
    because i enjoy to learn more and more.

  1. No trackbacks yet.


Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )


Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: