Homework 5: Testing Goldbach's conjecture

Learning Objectives ¶

Completing this assignment will help you practice:

defining and calling functions.
using loops.
using lists.

Overview ¶

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and in all of mathematics. It states (according to Wikipedia):

Every even integer greater than 2 can be expressed as the sum of two primes.[1]

In this assignment, you will write code to test this conjecture.

Step 1: Write code to compute if a number is a prime ¶

Open Thonny. Create a new folder. In this folder, create a file called goldbach.py.

Put this code into your file, verbatim:

# Top comment block here
# which includes your name, etc.

# ---------- imports -------------

# ---------- Constants here -------------

# ---------- Function declarations ------------

# ---------- main code ------------

This is a template for you to fill in.

Step 2: Create the function is_prime() ¶

In the Function Declarations section, create a function called is_prime(n). This function returns True if n is prime, and False otherwise.

You can tell if a number is prime if it cannot be perfectly divided by any number from 2 to n / 2 + 1. (Hint: "perfectly divided by" means the remainder is 0. Wow! What a hint!) So, you'll need a loop from 2 to n/2 + 1. For each of these numbers, div, you want to see if n can be perfectly divided by div. If you find a div that perfectly divides n, return False immediately. If your code loops through all values of div and finds no value that is a perfect divider, return True.

Now, test your is_prime() function using assert statements. Add these lines below your existing main code:

assert is_prime(2)
assert is_prime(3)
assert not is_prime(4)
assert is_prime(17)
assert not is_prime(20)

If all assertions pass without error, your function works correctly!

Step 3: Generate a list of primes up to the value entered by the user ¶

In the main section, add an input() to ask the user to enter a number below which you will test all even numbers to see if Goldbach's Conjecture holds. Store the result in variable max_val.

Below that code, write this code:

primes_list = gen_primes_list(max_val)
print("Primes numbers up to", max_val, "are", primes_list)

Now, in the Function Declaration section, add a function declaration for gen_primes_list(top_val).

The code in this function does this:

create an empty list
for each integer from 2 to top_val,
- if the integer is a prime,
  - add it to the end of the list.
return the list.

(This, you might have noticed, uses the accumulator pattern.)

Run your code with the number 50, and see if it prints only prime numbers up to 50. Try it with a larger number, perhaps, 2000.

Step 4: Test Goldbach's Conjecture, finally ¶

Now, create a function to test if a given even number is the sum of two primes. In the Function Declarations section, add a function test_even_number(e, primes_list):

The algorithm for this function is:

create a variable found = False
for each number p in primes_list:
- see if e - p is in primes_list. If it is,
  - set found to True
  - break out of this for loop: you've found that e is the sum of 2 primes. (Suggestion: if DEBUG, print out the mathematical fact that you’ve found, e.g., “10 = 3 + 7”.)
if found is False,
- that means you were not able to find any prime p and its corresponding e - p that add up to e. So, the even number e is not the sum of two primes. Woah! Print that you've proven Goldbach's Conjecture false for e. Make this a nice readable output. (Next, go immediately to submit your application to win a Nobel Prize in Mathematics!).
- return False
return True

Now, in your main code section, write code to call this function in a loop:

initialize a counter to 0 (you'll see below what this is for).
for each even number, e greater than 2, up to and including max_val (can you use a range for this?)
- call test_even_number(e, primes_list)
- if it returns False, increment the counter
if the counter is 0, print a statement about how Goldbach's conjecture holds for all even numbers up to max_val.

Step 5: Submit ¶

Clean up your code so that no testing/debugging output is generated anymore (did you wrap your debugging out in if DEBUG statements?). Your code should just get a value from the user, and print out results -- the numbers that thwart Goldbach's Conjecture, or the statement saying that Goldbach's conjecture seems true for all tested numbers.

Put your standard information at the top of your file.

Submit your final version of goldbach.py to ZyBooks.

Grading Rubric ¶

70 points: program that runs correctly.
30 points: code is clean and neat and uses good comments and variable names. I.e., the code is hospitable.

Homework 5: Testing Goldbach’s conjecture