Question

One class of prime numbers is represented in binary as a string of 1s in every position, for example: 1111 1111

Identify the function to generate this sequence of numbers.

Prove that the function does not always generate a prime.

What type of proof is used to show that not all numbers generated by the function are prime?

Answer 1

1. Function:

function generate_sequence():

x = 1

prime_numbers = []

while(true):

prime_numbers.append(x)

x = x<<1 + 1

return prime_numbers

The above function can genrate all the numbers of sequence by shifting the current number to left by 1 and then add 1 to it. for example if x = 1 then x<<1 = 10 and 10+1 = 11.

2. let us assume that all the numbers generated by the function are prime.

this means that 1111 is a prime number.

Let's convert 1111 to decimal i.e 15.

A prime number does not have more than 2 factors but 15 has 1,3,5,15 as it's factors. Thus our assumption that all the numbers generated by the function are prime is wrong.

Therefore, the function does not always generate a prime.

Hence Proved.

3. The method used to show  that not all numbers generated by the function are prime is Proof by contradiction.