Problems & Puzzles: Puzzles

 Puzzle 1129 OEIS A137990 Alain Rochelli sent on Jan 23, 2023 the following puzzle Related to A137990, "a(n) is the least prime p of the form c*3^n+1 with c not divisible by 3" (n>=0). Q1 : Can you verify by computation that a(n) is also the least prime such that 3^(n+1), but not 3^(n+2), divides 2^(a(n)-1)-1 ? Q2 : Can you get an explanation (proof) of this? Among other things, use recursive reasoning. Are there more primes of this form?

From April 29 to May 5, contributions came from Emmanuel Vantieghem, Adam Stinchcombe and  Oscar Volpatti

***

Emmanuel wrote:

***

You can prove this using the binomial theorem, by expanding 2^(an-1) = (3-1)^(c*3^n) = sum( (c*3^n  C  k * (-1)^(c*3^n-k)*(3)^k, k=0 to c*3^n).  Ignore the +1/-1 term which doesn't influence divisibility.  The first term is 1 which gets subtracted off in 2^(an-1)-1.  The next term is c*3^n/1*3^1 which is divisible by 3^(n+1) because c is rel prime to 3.  The next term is (c*3^n)(c*3^n-1)/(1*2)*3^2 which is divisible by 3^(n+2).  The next term shows you need to be careful because you get a 3 in the denominator, (c*3^n)(c*3^n-1)(c*3^n-2/(1*2*3)*3^3, divisible by 3^(n+2).  Et cetera.   You have to worry about the factors of 3 that show up in the denominator k! versus the numerator 3^k.  How many factors of 3 in (k!)?  Sum(floor(k/3^t,t=1..infinity)) which is smaller than Sum(k/3^t,t=1..infinity) which is a geometric series that converges to (k/3)/(1-1/3) =k/2.  You pick up n factors of 3 in 3^n, you pick up k factors of 3 in 3^k, and you lose at most k/2 in the denominator.  You inspect small k (above) and then the rest of the terms have >=n+2 factors of 3 as k gets big.

***

Oscar wrote:

About puzzle 1129, Alan Rochelli was right, but only for n>0.
Let's explicitly define his new sequence b(n), with n>=0:
b(n) is the least prime such that 3^(n+1), but not 3^(n+2), divides 2^(b(n)-1)-1.
It is possible to prove that b(n) is also the least ODD prime of the form c*3^n+1 with c not divisible by 3.

The proof uses a known theorem:

if g is a primitive root modulo prime p, and if g^(p-1) is not congruent to 1 modulo p^2, then g is also a primitive root modulo all powers p^k.
Number g=2 is a primitive root modulo prime p=3;

congruence relation  2^2 == 4 != 1 mod 9   holds too;
therefore 2 is also a primitive root modulo all powers 3^k.
In other words, power 3^k divides Mersenne number M(x) = 2^x-1 if and only if x itself is divisible by Phi(3^k) = 2*3^(k-1).

Let's go back to sequence b(n).
3^(n+1) divides 2^(b(n)-1)-1, so 2*3^n divides b(n)-1;
3^(n+2) doesn't divide 2^(b(n)-1)-1, so 2*3^(n+1) doesn't divide b(n)-1;
therefore b(n)-1 = d*2*3^n, with d not divisible by 3.
It must be d = 3*q+1 or d = 3*q+2, so that b(n) has one of the following forms:
(6*3^n)*q+(2*3^n+1),
(6*3^n)*q+(4*3^n+1).
In both cases we have a linear polynomial which produces primes for infinitely many values of variable q, by Dirichlet's theorem on arithmetic progressions.

Let's compare Alan Rochelli's sequence with OEIS A137990:
prime b(n) is of the form c*3^n+1 with c = 2*d, so that b(n) is forced to be odd.

But, for n>0, a(n) is forced to be an odd prime too, because it must be greater than prime 2:
a(n) >= 1*3^n+1 > 1*3^0+1 = 2.
Therefore identity a(n) = b(n) always holds for n>0.
But it doesn't hold for n = 0, because a(0) = 2 while b(0) = 3.

***

 Records   |  Conjectures  |  Problems  |  Puzzles