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(i1)+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)
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(i1)+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
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
Space delimited prime numbers satisfying Double and Add 1 property in the given range N
Constraints:
1. 2< N
<= 100000
2. 1< i
<= 10
Sample Input and Output
Example
Number

Sample
Input

Sample
Output

1

100 3 
2 5 89

2

20 2 
2 5 11 