# Goldbach conjecture


```python
import pybryt
```

# helper function

In this reference implementation we mark many values that we expect a good solution *not* to have. Therefore, we use this helper function simplifies the notation.


```python
def notify_when_value_exists(value, message_when_exists, message_when_missing = None):
    v = pybryt.Value(value)
    n = ~v
    n.success_message = message_when_missing
    n.failure_message = message_when_exists
    return(n)
```

The function above can be written in a concise way but it might be less obvious to understand why it works:

```python
def notify_when_value_exists(value, message_when_exists, message_when_missing = None):
    return (~pybryt.Value(value, 
        failure_message = message_when_missing,
        success_message = message_when_exists)
```

The strong Goldbach conjecture states that every even integer $\geq$ 4 is a sum of two prime numbers. Proving this conjecture is an open problem in mathematics for almost 300 years. In this exercise you are asked to write a function `check_goldbach_conjecture(n, primes)` which receives an integer `n` and a set of primes and returns `True` if `n` is a sum of two primes from the set or `False` otherwise. Try to make your solution efficient in terms of computational complexity and memory usage.


```python
def check_goldbach_conjecture(n, primes):
    """
    Checks if n can be written as a sum of two elements from the set primes.
    
    Args:
        n (``int``): an integer expected to be even greater than 4
        primes (``set`` of ``int``): a set of prime numbers
    
    Returns:
        ``bool``: True of n is a sum of two primes
    """    
    relevant_primes_set={p for p in primes if p<n}
    notify_when_value_exists(
        relevant_primes_set, 
        "ADVICE: it is good that you are looking only at primes smaller than n but to save memory you can do that without creating a new set"
    )

    notify_when_value_exists(sorted(primes), "ADVICE: sorting the list of primes only increases the complexity of the solution")

    for prime in primes:
        if n - prime in relevant_primes_set:
            return True
    return False
```


```python
from sympy.ntheory.generate import primerange
primes = set(primerange(50,1000))
n = 116
check_goldbach_conjecture(n, primes)

notify_when_value_exists(71 + 73, "ADVICE: instead of going over all primes and checking if they sum to n you can check if n-p is in the list of primes")

notify_when_value_exists(n - 997, "ADVICE: if the prime is bigger then n it cannot be a member of a pair that sum to n")

notify_when_value_exists(35, "ADVICE: the program checks if 35 is prime (35 is just an example), try to see if this can be avoided")

```




    pybryt.NotAnnotation



 

7264bfad944e1909c196522e10ecea3207ae8012
ipynb
Jupyter Notebook
demo/goldbach/goldbach.ipynb
chrispyles/pybryt
23f8bfce3179638ec5b4efe3555d3bb4e7321dc0
MIT
2021-02-17T20:45:17.000Z
2022-03-16T19:39:00.000Z
demo/goldbach/goldbach.ipynb
chrispyles/pybryt
23f8bfce3179638ec5b4efe3555d3bb4e7321dc0
MIT
2021-03-05T01:11:45.000Z
2022-03-23T04:08:58.000Z
demo/goldbach/goldbach.ipynb
chrispyles/pybryt
23f8bfce3179638ec5b4efe3555d3bb4e7321dc0
MIT
2021-02-14T04:27:34.000Z
2022-03-03T07:29:49.000Z
Qwen/Qwen-72B
1. YES
2. YES