# Goldbach conjecture

## Contents

# 6.5. Goldbach conjecture#

In this section, we will write a longer program that checks for a given number if the Goldbach conjecture is verified or rejected.

## 6.5.1. Problem Statement#

A conjecture is a proposition/opinion/observation that is not proven yet. For example, the Goldbach conjecture states:

Every

even integer greater than \(2\)can be written as the sum of two prime numbers.

A **prime number** is a number divisible only by two *distinct* numbers: 1 and itself. For example, \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\). Keep in mind that \(1\) is not a prime number because it is divisible by \(1\) only, not two *distinct* numbers.

Let’s write a program that asks for the user to input a number that is *even* and *greater than \(2\)*, and then checks if this number verifies or rejects the Goldbach conjecture.

## 6.5.2. Divide Problem into sub-problems#

Let’s list the tasks to be done by this program:

Take input number from the user

Verify if the number is even and greater than \(2\)

Test the Goldbach conjecture

Print if the number verifies or rejects the conjecture

Next, we tackle each task and decide if we can put it in a separate function or if it requires multiple functions. This helps us in easily managing a larger piece of software.

### 6.5.2.1. Take input from the user#

As we take input from the user, we need to validate that it is even and greater than \(2\) before proceeding with testing the Goldbach conjecture.

**Loop type.** As we discussed in Do-while loop vs. while loop, taking input from the user and validating it requires repetition until a valid input is made. Doing so requires that we first take the input from the user then validating it. This is what a do-while loop is best fit for. This is because a do-while loop will run its statements before checking the condition. Similarly, we want to take input from the user before checking it is even and greater than \(2\).

**Function prototype.** The following code is a function that takes the address of an `int`

variable, *i.e.* `int*`

, then the value at that address is changed to the input of the user. This is why we received a pointer `int*`

to the function and return `void`

.

**Code in-progress**

```
1void getUserInput(int *number) {
2 // Get user input from the keyboard
3 // and validates it is even and greater than 2
4
5 do {
6 printf("Enter a number to test the Goldbach conjecture: ");
7 scanf("%d", number);
8 } while (*number <= 2 || *number % 2 != 0);
9}
```

Important!

In line 6, we are using `scanf`

without an `&`

because `number`

is already an address to the `int`

we want to change.

In line \(8\), we are referring to the `int`

variable that `number`

has it’s address. This is why we dereference `number`

to get to the `int`

it is pointing to.

**Test with main function**

```
1#include <stdio.h>
2
3void getUserInput(int *);
4
5int main(void) {
6 int num;
7 getUserInput(&num);
8 return 0;
9}
10
11void getUserInput(int *number) {
12 // Get user input from the keyboard
13 // and validates it is even and greater than 2
14
15 do {
16 printf("Enter a number to test the Goldbach conjecture: ");
17 scanf("%d", number);
18 } while (*number <= 2 || *number % 2 != 0);
19}
```

**Output1**

Enter a number to test the Goldbach conjecture:-1Enter a number to test the Goldbach conjecture:3Enter a number to test the Goldbach conjecture:4

Currently, the prompt message is not telling the user why is their first and second input invalid. To have a clarifying prompt message after the user enters an invalid input, we can have a `bool`

variable that indicates if it is the first time the user enters an input. We can use this `bool`

variable to better explain to the user what is the expected input. The modified function is shown below. We added lines \(17\), \(19\) – \(22\).

**Improved getUserInput function**

```
1#include <stdbool.h>
2#include <stdio.h>
3
4void getUserInput(int*);
5
6int main(void) {
7 int num;
8 getUserInput(&num);
9 return 0;
10}
11
12void getUserInput(int *number) {
13 // Get user input from the keyboard
14 // and validates it is even and greater than 2
15 bool firstEntry = true;
16 do {
17 if (firstEntry) {
18 printf("Enter a number to test the Goldbach conjecture: ");
19 firstEntry = false;
20 } else {
21 printf("Your input was invalid, please enter another even number > 2: ");
22 }
23 scanf("%d", number);
24 } while (*number <= 2 || *number % 2 != 0);
25}
```

**Output**

Enter a number to test the Goldback conjecture:-1Your input was invalid, please enter another even number > 2:3Your input was invalid, please enter another even number > 2:4

### 6.5.2.2. Test the Goldbach conjecture#

**Step 1: Toy example.** For example, if the user enters \(12\). Logically, we can think that 12 can be written as \(12 = 5 + 7\).

**Step 2: Think of a solution and decompose into steps!** The user entered \(12\) which is a sum of two `int`

prime numbers, `x`

and `y`

, *i.e.* \(12 = x + y\). To find `x`

and `y`

, we can

Get the first prime number in

`x`

, which is \(2\).Then get

`y`

, which is \(y = 12 - x\).Check if

`y`

is prime.If

`y`

, is not prime, we increment`x`

to the next prime number.Then we repeat steps \(2\) – \(4\)

We stop repeating till we find

`y`

is prime or if the**conjecture is rejected**. When is the conjecture rejected?

For example, in Fig. 6.14, we show the steps/iterations to verify the Goldbach conjecture for \(12\). The conjecture gets rejected when we continue looking for `x`

and `y`

, but realize they will never be both prime numbers. This happens when `x`

prime numbers start to surpass the values of `y`

. This is also around when `x`

becomes greater than the half of \(12\), which is the number we are testing.

**Summary!** We stop iterating and looking for `x`

and `y`

prime numbers either: (i) when the conjecture is verified (`x`

and `y`

are prime) or (ii) when `x`

becomes greater than `y`

and we have never verified the conjecture before!

**Step 3: Write a pseudo-code.** We can write the *pseudo-code* of the above steps. *Pseudo-code* is an informal language used to write code. It is intended to simplify a piece of code by writing it in plain English language mixed with a program language too. For example, we can translate the above steps to the following pseudo-code.

**Pseudo-code**

// first prime number x = 2 while(not verified and not rejected){ // look for x and y // N is user input y = N - x if(y is Prime){ conjecture is verified }else if (x > y){ conjecture is rejected }else{ x is advanced to the next prime number } }

**Step 5: Write the code.** There are two tasks in the previous pseudo-code that require a few lines of code to accomplish. These are: (i) if y is prime, and (ii) to get the next prime number after `x`

. These two will be completed by different functions. We can define their function prototypes before proceeding with writing the code for testing Goldbach conjecture.

*Check if a number is prime.*This can be a function that returns`true`

is a number is prime and`false`

if the number is not prime. The only input this function requires is the`int`

value it will check. This makes the function prototype:`bool isPrime(int);`

*Get the next prime number.*There are many ways to advance to the next prime number. All what you need is to pass the address of`x`

to that function, and the function will change the value of`x`

and return`void`

. This makes the function prototype:`void nextPrimeNumber(int*);`

In the following code, we convert the pseudo-code to a function written in C programming language.

```
1bool testGoldbach(int N) {
2 // Tests the Goldbach conjecture and
3 // returns true if verified or false if rejected
4 int x = 2, y;
5 bool rejected = false;
6 bool verified = false;
7 while (!rejected && !verified) {
8 y = N - x;
9 if (isPrime(y)) {
10 verified = true;
11 } else if (y < x) {
12 rejected = true;
13 } else {
14 nextPrimeNumber(&x);
15 }
16 }
17 return verified;
18}
```

In line \(7\), we check if rejected and verified are both `false`

. This is by adding a `!`

before `rejected`

and `!`

before `verified`

and ANDing them: `!rejected && !verified`

.

In line \(9\), we immediately use `isPrime`

as we know it returns either `true`

if `y`

is a prime number or `false`

otherwise: `isPrime(y)`

.

In line \(14\), we use `nextPrimeNumber`

by passing the address of x to it, and inside the function we will shortly implement the advancement of `x`

to the next prime number: `nextPrimeNumber(&x)`

.

### 6.5.2.3. Get the Next Prime Number#

To implement `void nextPrimeNumber(int*);`

, we need to first think of how to find the next prime number.

**Step 1: Toy example.** For example, the next prime number after \(3\) is \(5\).

**Step 2: Think of a solution and decompose into steps.** The next number after \(3\) is \(4\), but it is not prime number. We can continue advancing to \(5\) and then checking if it is prime! Given that, the steps to get the next prime number are

Add \(1\) to that value

Check if it is prime

Repeat \(1\) – \(2\) till value becomes a prime number

**Step 3: Write the code.** The following code implements the steps discussed. Caution! We are receiving the address of a `int`

, which is `int*`

.

```
1void nextPrimeNumber(int *px) {
2 // We will look for the numbers after *pFrist one by one
3 // until we find the next prime number
4 int value = *px + 1;
5 while (!isPrime(value)) {
6 value += 1;
7 }
8 *px = value;
9}
```

In line \(5\), we check if `value`

is prime or not using `isPrime`

function, which we know it will return `true`

if value is prime and `false`

otherwise. `!isPrime(value)`

is `true`

as long as `value`

is not prime. Once `value`

is prime, `!isPrime(value)`

becomes `false`

, and we exit the loop.

In line \(8\), we are not returning any values because `nextPrimeNumber`

does not return any number. Instead, we change the value at address `px`

to the prime number we found next.

**Step 4: Test your code in isolation.** You should be testing your code when called only by the `main`

function to see if it works.

### 6.5.2.4. Find If a Number Is Prime or Not#

To implement `bool isPrime(int);`

, we need to first think of how to know if a number is prime.

**Step 1: Toy example.** For example, \(12\) is not a prime number.

**Step 2: Think of a solution and decompose into steps.** We know that a prime number `num`

is divisible only by \(1\) and `num`

. This means that between \(2\) and the `num - 1`

there is no divisibles of `num`

. We can do the following steps to see if `num`

is prime:

Denominator

`denom`

is set to \(2\)Find if

`num`

/ \(2\) gives no**remainder**,*i.e.*`num % denom == 0`

If

`num % denom == 0`

, then`num`

is not prime, because it is divisible by`denom`

.Otherwise, add \(1\) to

`denom`

Repeat \(2\) – \(4\), until either you found out

`num`

is not prime, or when`num % denom == 0`

has been checked on all`denom`

values from \(2\) to`num - 1`

and was never`true`

. This is when`num`

is`true`

.

**Step 4: Write pseudo-code.**

**Pseudo-code**

// We can start with good intentions that a number is prime if (number is less than 2){ number is not prime }else{ denom = 2 while(denom < num -1 and number is still prime) if (num % denom == 0){ number is not prime }else{ denom = denom + 1 } } }

**Step 3: Write the code.** To implement the `bool isPrime(int);`

, we will convert the pseudo-code into code.

**Code**

```
1bool isPrime(int num) {
2 // check if num is prime, by checking the remainder of num / all numbers from
3 // 2 to num - 1
4 bool prime = true;
5 if (num < 2) {
6 prime = false;
7 } else {
8 for (int denom = 2; denom <= num - 1 && prime; denom++) {
9 if (num % denom == 0) {
10 prime = false;
11 }
12 }
13 }
14 return prime;
15}
```

**Step 4: Test your function in isolation.** Think of numbers to test your function. Numbers less than, greater than or equal to 2.

Does the function work with numbers

*less than 2*? Yes. Line \(6\) will set`prime`

to`false`

.Does the function work with

*2*? In line \(8\),`denom`

starts from \(2\), and then`denom`

is checked with`num - 1`

. The condition`denom <= num - 1`

is false if`num`

is set to \(2\). Hence, the function will return the preset value of`prime`

, which is`true`

.Does the function work with numbers

*above 2*? In lines \(8\) – 10, the function will set`prime`

to`false`

if`num`

is divisible by another number between \(2\) and`num - 1`

. It will exist the loop because this condition`denom <= num - 1 && prime`

becomes`false`

. The function will not change`prime`

value if the loop tries over all`denom`

values from \(2\) to`num - 1`

and does not find`num`

to be divisible. Hence,`prime`

will**continue**to be`true`

.

### 6.5.2.5. Print If the Conjecture Is Verified#

We need a function that prints if the Goldbach conjecture is verified or rejected! This function can simply call `testGoldbach`

. If `testGoldbach`

returns `true`

, the function prints the number verifies the conjecture, and prints the number rejects the conjecture otherwise.

These simple steps can be written as follows:

**Code**

```
void printConjResult(int number){
//Call a function to verify the conjecture and prints the result
bool verified = testGoldbach(number);
if(verified){
printf("Goldbach conjecture is verified.\n");
}
else{
printf("Goldbach conjecture not verified.\n");
}
}
```

## 6.5.3. Integrate all pieces/functions#

In the previous sections, we have divided the steps into two **main** ones: getting input through `getUserInput`

and printing if the conjecture is verified through `printConjResult`

.

This eases the task of writing the `main`

function. The `main`

function should only call `getUserInput`

and `printConjResult`

. This is shown in the following code.

**Code**

```
int main(void){
int number;
getUserInput(&number);
printConjResult(number);
return 0;
}
```

**Output1**

Enter a number to test the Goldbach conjecture:9Your input was invalid, please enter another number > 2:8Goldbach conjecture is verified.

Please refer to `goldbach-conjecture.c`

if you want to view the entire program and test it yourself.