Problems & Puzzles: Puzzles

Puzzle 1033. Primes p+2^q Sebastian Martin Ruiz sent the following nice puzzle: Let p<q consecutive prime numbers Find a prime number (*) of the form p+2^q   I have found the smallest probable-prime * 22073+2^22079, with 6647 digits Note: if q-p=2  p+2^q is divisible by q If q-p=4  p+2^q is divisible by 3   Q1. Find other relationships Q2. Find larger probable primes of this form ____________________ (*) To check this I have used the PrimeQ function of MATHEMATICA. The Wolfram Language implements the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n].

---

During the week 3-9 April, 2021, contributions came from Oscar Volpatti

***

Oscar wrote:

Here are my findings for puzzle 1033.

 

Q1

Relationships involving p only:

2 divides p+2^q if and only if p = 2;

3 divides p+2^q if and only if p == 1 mod 6.

 

Relationships involving q-p only:

2 divides p+2^q if and only if q-p = 1,

3 divides p+2^q if q-p == 4 mod 6,

 

as congruence q-p == 4 mod 6 holds if and only if p == 1 mod 6 and q == 5 mod 6.

 

Q2.

I checked all pairs (p,q) with p <11000, finding no more prps

 

For each pair (p,q) I also checked numbers of the form q+2^p, finding eight primes and one prp:

 

3+2^2

5+2^3

11+2^7

17+2^13

29+2^23

41+2^37

71+2^67

89+2^83

31793+2^31771 

***