flybonzai
flybonzai

Reputation: 3941

Goldbach Conjecture algorithm returning one incorrect tuple each time

I created a function to find all combinations of prime numbers that would add up to a given number. It is working fabulously, other than the second tuple I return is always off. The way the code is structured it will always return both variations of a given tuple, so for example (5, 13) and (13, 5), but this incorrect tuple is always alone.

def goldbach_conj(number):
    prime_tup_list = []
    x, y = 0, 0
    result = 0
    if not number % 2:
        prime_list = list_of_primes(number)
        # while result != number:
        for i in range(len(prime_list)):
            x = prime_list[i]
            if result == number:
                prime_tup_list.append((x, y))
            for j in range(len(prime_list)):
                y = prime_list[j]
                result = x + y
                print("Adding {} and {}.".format(x, y))
                print("Result is {}".format(result))
                if result == number:
                    prime_tup_list.append((x, y))
    return prime_tup_list

If I enter 56 as my number I get this output:

[(3, 53), (5, 53), (13, 43), (19, 37), (37, 19), (43, 13), (53, 3)]

For 36 I get:

[(5, 31), (7, 31), (7, 29), (13, 23), (17, 19), (19, 17), (23, 13), (29, 7), (31, 5)]

Upvotes: 0

Views: 377

Answers (2)

The Brofessor
The Brofessor

Reputation: 1048

You can also edit the range on the second for loop, to avoid duplicates!

def g(number):
    prime_tup_list = []
    x, y = 0, 0
    result = 0
    if not number % 2:
        prime_list = list_of_primes(number)
        for i in range(len(prime_list)):
            x = prime_list[i]
            for j in range(i, len(prime_list)):
                y = prime_list[j]
                result = x + y
                print("Adding {} and {}.".format(x, y))
                print("Result is {}".format(result))
                if result == number:
                    prime_tup_list.append((x, y))
    return prime_tup_list

Output:

For 56 and 36, respectively

[(3, 53), (13, 43), (19, 37)]

[(5, 31), (7, 29), (13, 23), (17, 19)]

Upvotes: 1

Anand S Kumar
Anand S Kumar

Reputation: 90979

This condition directly inside the first for loop seems to be the one causing the issue -

if result == number:
    prime_tup_list.append((x, y))

When you find a result that is equal to the number inside the second for loop, you add that to the prime_tup_list , but then if that was the last prime number in the list, the result is not changed and we exit out of the second for loop (with still the same result) and in the next iteration in first for loop, you take the next x value, but before you calculate result again, you check if result is equal to number , if it is you append x (new x , not the one used to calculate result) and y to the list.

You can remove that if condition altogether, not sure why it is there.

EDIT:

Code -

def goldbach_conj(number):
    prime_tup_list = []
    x, y = 0, 0
    result = 0
    if not number % 2:
        prime_list = list_of_primes(number)
        # while result != number:
        for i in range(len(prime_list)):
            x = prime_list[i] #if below here is removed.
            for j in range(len(prime_list)):
                y = prime_list[j]
                result = x + y
                print("Adding {} and {}.".format(x, y))
                print("Result is {}".format(result))
                if result == number:
                    prime_tup_list.append((x, y))
    return prime_tup_list

Upvotes: 1

Related Questions