TCS Code Vita Season-5 Round-1 set-2 Program-2

Problem : Double And Add One

If you like numbers, you may have been fascinated by prime numbers.
Here’s a problem related to prime numbers: Accept input numbers N and i. Identify all prime numbers P up to N with the following property:

P1=2*P+1 is also prime
P2=2*P1+1 is also prime

Pi=2*P(i-1)+1 is also prime

Example: Inputs N=100, i=3

Let’s start with p=2(it is also prime ). Since i=3 we need 3 consecutive prime numbers that satisfy the Double and Add 1 property explained below:
p1=2*p+1 translates to p1=2*2+1=5, which is prime
p2=2*p1+1 translates to p2=2*5+1=11, which is prime
p3=2*p2+1 translates to p3=2*11+1=23, which is prime

Hence p=2 is to be included in the output.

Next, if p=3, the derived numbers are 7, 15, 31 of which 15 is not prime. Hence p=3 is not a solution

Exploring other primes up to 100 in this fashion, we identify the following additional numbers to be included in the solution for i=3:

5 (since the derived numbers 11, 23, 47 are all prime)
89 (since the derived numbers 179, 359, 719 are all prime)

Hence the output would be: 2, 5, 89

Input format for the example: 100 3
Output format for the example: 2 5 89
(Numbers separated by single space)

Input Format:

First line contains an integer N
Second line contains integer i

Output Format:

Space delimited prime numbers satisfying Double and Add 1 property in the given range N

1.    2< N <= 100000 
2.    1< i <= 10 

Sample Input and Output


Example Number
Sample Input
Sample Output

2 5 89


2 5 11