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.

In the "main code" section, write code to do this:

Ask the user for a number which is stored in a variable num. Make sure this num is an integer.
Write this code: print(num, "is prime?: ", is_prime(num))

Those are the only lines in the main section.

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, run your code and see if is_prime() produces the correct result, for some known prime numbers, and some numbers known not to be prime.

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

Update your input() call in the main section 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 now.

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, write code in your main code section to test if each even number from 4 up to max_val is the sum of two primes.

The algorithm is basically this:

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:
- 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.
- if found is False,
  - you were not able to find any prime p and its corresponding e - p that add up to e. So, e is not the sum of two primes. 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!).
  - increment a counter of how many even numbers you've found that show the conjecture is wrong.
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 Moodle.

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