From Puzzles to Programming

1. Can you prove that the sum of any two prime numbers (except 2) is an even number?

Answer

Primes play a major part in the study of the theory of numbers. A prime p is defined as a prime if its only divisors are ±1, and ±p. The first 10 positive prime numbers are 2,3,5,7,11,13,17,19,23, and 29.

Any prime number (except 2) should be followed by an even number in the number system. If p and q are any prime numbers then p can be written as (e1-1) and q as (e2-1) where both e1 and e2 are the immediate even numbers that follow them respectively in the number system. It follows that the sum of any 2 prime numbers p and q = p + q  =

(e1-1)+(e2-1) = e1+e2-2 = e which is also an even number.

In the same scenario, the difference of 2 primes is an even number.

2. Can you prove that every even number can actually be expressed as sum of 2 prime numbers (Goldbach Conjecture)??

This is difficult one. I leave it for you to solve. 

3. Can you find a way to generate the set of prime numbers less than an integer n?

Answer

One method is called the Cribble of Eratosthene. In this method, you write the integers from 1 to n.

Now cancel all the multiples of 2 that are different from 2. Then cancel all the multiples of 3 that are different from 3. Finally, cancel all the multiples of 5 that are different from 5.

Note that the first multiple of 3 to be cancelled is 3² because 3x2 is already cancelled. Similarly, the first multiple of 5 to be cancelled is 5² because 5x2, 5x2x2, and 5x3  are already cancelled. Therefore, we continue this operation up to the prime number p such that p²> = n.

4. We proved earlier that the sum of any two prime numbers is an even number. This was easy because of the fact that every prime (except 2) is preceded or followed by an even number. However, to prove that any even number E is the sum of two prime numbers is not straight forward because there is more than one set of pairs of primes whose sum is equal to E. For example, the set of pairs of primes whose sum is equal to 50 is {(3,47), (7,43), (13,37), (19,31)}.

One way is to generate even numbers from prime numbers in the same way as Cribble of Eratosthene. Since any 2 prime numbers add to an even number then

adding (3 and 3); (3 and 5); (3 and 7); (3 and 11)...will generate even numbers.

Continue by adding (5 and 5), but this is already made by adding (3 and 7) so it is skipped. Next would be adding (5 and 7),…

Next add (7 and 7) (also skipped as it is made by adding (3 and 11)), and add (7 and 11) (also skipped)... Continue until reaching the even integer n. In this method, all the integers generated are even numbers and this can be done for any positive even integer n.

One easy and fast way to split an even number E into a pair of primes is to choose the primes that are both as close as possible to E/2. The algorithm is as follows:

Readln(E);

E = E/2 + E/2;

Let A=E/2 and B=E/2

If Testprime(A)=true and Testprime(B)=true then

   { both A and B are prime}

   Writeln (A, B);

Else

While Testprime(A)<>true and Testprime(B)<>true do

        begin A=A+1; B=B-1; Testprime(A);Testprime(B); end.

Writeln(A, B);

Testprime(n) is a procedure that returns a Boolean value true or false. It tests if n is a multiple of prime numbers 3,5,7,..and so on until p²>=n where p is a prime number.

Another algorithm for Testprime(x) that tests if all the integers less than x are divisors of x is as follows:

Function Testprime(x)

Testprime = true

For I = 2 to x-1

   If (x mod I) = 0 then Testprime = false;

5. A rich and wise man put a number of diamonds in each of 3 closed boxes and a pot and presented them to his son. A number was written on the outside of the pot. He gave this pot to his son and he told him that if he want the other 3 boxes then he has to know how many diamonds each contains. The son answered "I cannot unless you give me a hint". The father said "Ok. The product of the numbers of the diamonds in the 3 boxes is 2450 and their sum together is as the number on the pot you have." After some calculations, the son said "I need another hint." The father then smiled and said "Of course you need another hint; if I tell you that one of the boxes with the largest number of diamonds has more diamonds than the pot you have, then you should be able to solve it." The son was able to tell the number of diamonds in the pot and each of the 3 boxes and he took them all. How was that?  

Answer

These kinds of problems are based on a fact that any non prime number can be written as a product of prime factors. The number 2450 can be written as 2x5x5x7x7. These 5 prime factors can be assigned to the 3 boxes in the following ways:

Only number 64 is repeated twice. Each of the other sums is mentioned only once. Since the son could not tell the combination of number of diamonds based on the product and the sum then the number labeling the pot -which is equal to the sum- is 64. The possible numbers of diamonds in the 3 boxes are (10, 5, 49) or (7, 7, 50). The second hint says that the son can solve the problem only if he knows that the box with the largest number of diamonds has more diamonds than that of the pot. Now the pot cannot have less diamonds than 49 because if it is the case then both combinations i.e. (5,10,49) and (7,7,50) are still valid and the son still cannot solve the problem. Therefore, the pot must have a number of diamonds less than 50 but more or equal than 49. Since we are not dealing with fractions of diamonds, it is obvious that the pot has 49 diamonds; and the other boxes have 5, 10, 50 diamonds.

6. In the above example, we “stated” that a non-prime integer is a product of prime factors, and this was the basis for the solution of the above puzzle. How can this be proved?

Answer

Any natural integer 'n' admits at least a prime divisor 'a1' in such a way n=a1q1.

Now, if q1 is a prime then n will be a product of 2 prime numbers a1 and q1.

If q1 is not a prime, then q1 admits a prime divisor a2 such that q1 = a2q2 and n = a1a2q2.

If q2 is a prime then n is a product of 3 prime numbers a1,a2, and q2

else q2 = a3q3 and n = a1a2a3q3..and so on 

Now, n = a1a2a3a4..qr with qr the smallest prime divisor. If qr is not a prime then qr has a prime divisor ar+1 such that qr = qr+1 ar+1 with qr+1 smaller than qr which is a contradiction. Therefore, n = a1a2a3…qr with qr the smallest prime divisor.