Problems & Puzzles: Puzzles

Puzzle 1047. p*2^p+1 Sebastian Martín Ruiz sent the following puzzle. I have tested p*2^p+1 until p(7000)=70657 and all of them are composite, none a probable prime. Q. Prove that there is not any prime or find one probable prime?

---

During the week 24-30 July, 2021, contributions came from Emmanuel Vantieghem, Ken Wilke, Simon Cavegn

***

Emmanuel wrote:

In order to check Sebastian's result, I started searching for numbers  k  such that  k*2^k + 1  is prime. 

This led me very soon to  A005849  at the OEIS.  There I learned that numbers of the form  k 2^k +1  are Cullen numbers and that the present puzzle

is one of the many unsolved problems in number theory ; until now there is no prime number known of the form  p*2^p + 1  when  p  is prime.

According to some of the links in  A005849  all  p  less than 10^7  have been checked.

I think my actual computing capacity does not allow me to check the numbers  p*2^p + 1  for  p > 10^7.

...

I could not resist the temptation to work a bit further on Cullen numbers  k*2^k + 1  with prime  k  bigger than 10000000.

I examined all such Cullen numbers such that  10 000 000 < k <= 10 000 261.  They all had a 'small' prime divisor (less than 10^9.).
The next prime, 10000271  is index for a Cullen number that has no prime divisor <= 6506515801.  Despite that result, I think that Cullen number is composite. With Mathematica it would take more than one month to perform a Fermat base 2 test ...

 

 

***

Ken wrote:

Attached is a Word file with a partial result for Puzzle 1047. If I can provide more on Case 2, I will do so. It is curious that for about half of the primes, that the given expression is divisible by 3.

"Consider the expression T = p* 2^p +1 where p is a prime. Prove that T is composite or find a value of p such that T is a probable prime.

This partial result will show that T is composite for roughly half of all primes p.

Lemma: 2^ 6k == 4 (mod 6) for all positive integers k.

Proof: For k=1, 2^6 =64== 4(mod 6). Then since 4*4==4 (mod 6) an easy induction on k completes the proof of the lemma.

For p=2, T =2*(2^2) +1 =9 and for p = 3, T=3*(2^3) +1 = 25 both of which are clearly composite. Now let p be a prime > 3.

Case 1: Let p = 6n +1 for some positive integer n. Then by the lemma,

T = (6n+1)*(2^ (6n+1)) +1==2*(2^6n) +1 ==2*4 +1 ==3(mod 6). Hence T is divisible by 3 whenever p==1 (mod 6).

Case 2: Let p = 6n +5 for some positive integer n. Then by the lemma,

T = (6n+5)*(2^ (6n+5)) +1== 5*(2^5)*(2^6n) +1 ==5*32*4 +1 == 641==5(mod 6). Hence T has at least one divisor d such that d==5 (mod 6) whenever p==5 (mod 6). Since 5*5 ==1 (mod 6), either T is prime or T has an odd number of divisors of the form d==5(mod6)."

I added a small result showing an infinite series of primes of the form 6k+5 all of which are divisible by 7. It doesn’t add much to the general solution for Case 2, but it does provide a possible approach to explore.

"One can easily show that there are an infinite number for values of (6n+5) for which Tis divisible
by 7. Suppose that T = (6n+5)*(2^ (6n+5)) +1 ==0 (mod 7). Then since 2^6 ==1 (mod)7), T ==
(6n+5)*32*(2^6)^n +1 ==(6n+5)*4 +1 ==3n ==0 (mod 7). Hence n ==0 (mod 7). Thus when
n = 7m for some nonnegative integer m, 6n +5 becomes 42m+5 and
T = (42m+5)*(2^(42m+5) +1 ==0 (mod 7). Hence for all primes of the form 42 m +5, T is
divisible by 7."

***

Simon wrote:

Found nothing. Tested up to p(33630) = 397093

***