1

I've tried to write a code for the weak Goldbach Conjecture, which states that every odd number greater than 5 can be expressed as the sum of three prime numbers. However, the code only returns (0, 0, 0). I only need one triple that works rather than a list of triples. Any ideas where I'm going wrong? Also I know that the code isn't the most efficient as it is, especially using the eratosthenes function to generate my primes, but this is the form that I've been asked to code in.

def eratosthenes(n):
    primes = list (range(2, n+1))
    for i in primes:
        j=2
        while i*j<= primes[-1]:
            if i*j in primes:
                primes.remove(i*j)
            j=j+1
    return primes

def weak_goldbach(N):
    x, y, z = 0, 0, 0
    result = 0
    if not N % 2:
        prime = eratosthenes(N)
        while result != N:
            for i in range(len(prime)):
                x = prime[i]
                if result == N: 
                    break
                for j in range(i, len(prime)):
                    y = prime[j]
                    result = x + y
                    if result == N: 
                        break 
                    for k in range (j, len(prime)):
                        z = prime[k]
                        result = x + y + z
                        if result == N:break
    return x, y, z
jemima
  • 29
  • 1
  • 1
  • 6

1 Answers1

2

Bugs

There are a few problems with your code, but the first, and the reason it fails, is that not N % 2 always evaluates to false for odd numbers, skipping your loop and returning the initial values you set x,y and z.

There are also logical problems with it; your code breaks in the most inner loop when x+y+z == N, then the outer loops break when result is correctly set, but only after changing x or y! This means that even if you fixed the first problem, your code would always return the wrong result.

Inefficiencies

Firstly, you don't need the complicated break logic at all! You can just return x, y, z when you first find it sums to N.

Secondly, you don't need the result=x+y code in the middle loop, since it has no relevance in the weak Goldbach conjecture and is never true anyway.

Thirdly, the outer while loop is completely useless. It does nothing at all, except create an infinite loop if the inner loops didn't find a result for some reason.

Other issues

It's best to reduce nesting; so, the condition making sure it is an odd number greater than 5 should be negative, and should return an exception if it doesn't hold. That way the body of the function isn't nested in a conditional, which makes it a bit more readable.

Corrected code that works

def weak_goldbach(N):
     x, y, z = 0, 0, 0
     result = 0
     if not N % 2 or N < 7:
         raise Exception("Bad input - must be odd number greater than 5.")
     prime = eratosthenes(N)
     for i in range(len(prime)):
         x = prime[i]
         for j in range(i, len(prime)):
             y = prime[j]
             for k in range (j, len(prime)):
                 z = prime[k]
                 if x+y+z == N:
                     return x, y, z
     raise Exception("Looks like %d is the exception to the weak Goldbach conjecture!" % N)
Silas Coker
  • 480
  • 2
  • 7
  • 1
    Thank you so much! One thing I don't fully understand are the 'raise' bits, I've never used this before, could you explain it a little? And would it be possible to replace these with for/if statements in theory? – jemima Dec 17 '18 at 15:12
  • Sure, the 'raise' bits 'throw' exceptions; errors basically. They stop any further code executing unless you use a try..catch block to deal with it. It's best practise but you might prefer to return a value like None instead of the raise statements. – Silas Coker Dec 17 '18 at 15:18
  • @jemima think of them as a glorified `print()` statement. Whenever you catch something that needs the user's attention, you could print an error and/or warning message to screen. Using `raise Exception()` does exactly that but in a more proper and "pythonic" way. – Gabriel Dec 17 '18 at 15:20
  • 1
    I put the raise at the end as a joke. It shouldnt ever run! – Silas Coker Dec 17 '18 at 15:20
  • 1
    @jemima I made a mistake in my explanation; 'result' was of course the sum so you couldn't return it. – Silas Coker Dec 17 '18 at 15:28