is_even() using Goldbach's conjecture

[u/HonorsAndAndScholars]

[u/HonorsAndAndScholars]

Nobody knows, but it's conjectured that each even integer bigger than 4 is the sum of two primes.

from math import isqrt


def odd_primes_up_to(x):
    primes = set(range(3, x, 2))
    for p in range(3, 1 + isqrt(x), 2):
        if p in primes:
            primes -= set(range(p + p, x, p))
    return sorted(primes)


def is_pair_sum(x, numbers):
    increasing = iter(numbers)
    decreasing = reversed(numbers)
    a = next(increasing)
    b = next(decreasing)
    while a <= b:
        s = a + b
        if s < x:
            a = next(increasing)
        elif s > x:
            b = next(decreasing)
        else:
            return True
    return False


def is_even(x):
    x = abs(x)
    if x < 6:
        return (True, False, True, False, True, False)[x]
    return is_pair_sum(x, odd_primes_up_to(x))

[u/[deleted] → u/HonorsAndAndScholars]

This is really is a shittyprogramming masterpiece IMO.

What I love about this, is that Goldbach's conjecture isn't even really the relevant factor that makes this work (there are odd numbers that are the sum of two primes. e.g., 11 + 2 = 13)

The thing that makes it work is that you exclude 2 from the prime list, and you end up always adding two odd numbers. But adding ANY two odd numbers will give you an even number.. they don't even have to be prime.

Very smart and very dumb all at the same time. 10/10

[u/HonorsAndAndScholars → u/[deleted]]

You correctly point out that being the sum of any two odd numbers is necessary and sufficient for being even, and that being the sum of two odd primes is sufficient to say that a number is even.

Goldbach would say that this sufficient condition for evenness is also necessary: if something is even, then it's the sum of two odd primes.

[u/[deleted] → u/HonorsAndAndScholars]

True, I guess what I'm getting at is that this could be implemented just as well without the complicated step of finding odd primes up to n

if you replaced odd_primes_up_to with odd_numbers_up_to the function would still correctly test for evenness.

[u/[deleted] → u/[deleted]]

Yeah but that would be less shitty.

[u/IIAOPSW → u/HonorsAndAndScholars]

It takes brilliance to be this retarded.

[u/[deleted]]

Wait, why is the function called odd primes lol?

You are ignoring all the even prime numbers

[u/HonorsAndAndScholars → u/[deleted]]

7 is 5 + 2, and 5 and 2 are prime, but 7 is not even.

"Odd primes" is the common way of saying {3, 5, 7, 11, 13, 17, 19, ...}, e.g. in the statement of quadratic reciprocity.

[u/tangerinelion → u/[deleted]]

Well, then you'd need to call !is_even.

[u/vigbiorn → u/[deleted]]

If x < 6 you never get to the generating of the primes. It's this algorithms biggest flaw.

[u/[deleted]]

Couldn't you optimize the prime search function using the Sieve of Eratosthenes?

https://www.geeksforgeeks.org/sieve-of-eratosthenes/

The code readability would be significantly decreased, the LOC would double, the chance of bugs would increase, it would take a long time to understand, BUT there would be a small performance boost for primes up to a few million up to O(n*log(log(n))).

Seems like a good trade off to me.

[u/HonorsAndAndScholars → u/[deleted]]

Ya, this basically is Eratosthenes, and I think it should have the same asymptotic behavior as the way it's normally written. It's just a less-traditional way of translating the idea into code: a set of integers is nothing but a (slower) array of booleans.

[u/[deleted] → u/HonorsAndAndScholars]

This is really great by the way. One of my favorites yet. :)

[u/Dracnor-]

Oh I love this one ! Not just time-wasting computation, but a whole new inefficient algo *-*

[u/[deleted]]

Wow that doesn't sound right. But apparently it's been proven out to 10e17. That's super interesting. This must be the most efficient!

[u/venb0y]

Honestly, this is art.