Problems & Puzzles: Puzzles

Puzzle 1134 F(n)=|(2^n-1)/(2n+1)|

By Sebastián Martín Ruiz. Consider the integer values of the function F(n)=(2^n-1)/(2n+1). We have if F(n) is prime then n and 2n+1 are also prime numbers.

Q1) Prove it or find a counterexample.

I have found the following values expressed in MATHEMATICA


Do[If[PrimeQ[F[n]],Print[F[n]," ",n," ",2n+1," ",PrimeQ[F[n]]," ",PrimeQ[n]," ",PrimeQ[2n+1]]],{n,1,15000}]

89 11 23 True True True

178481 23 47 True True True

57912614113275649087721 83 167 True True True

10350794431055162386718619237468234569 131 263 True True True

0802238405154786248043073 3359 6719 True True True

Q2) Find more prime values of F(n) , n and 2n+1


During the week 10-16 JUne 2023, contributoons came from Michael Branicky, Alessandro Casini, Giorgos Kalogeropoulos, Oscar Volpatti, Emmanuel Vantieghem

Michael wrote:

This problem is partially studied in OEIS A239638, so besides n =  11, 23, 83, 131, and 3359 above, we have n = 130439 and 406583 are solutions with n and 2n+1 prime.


Alessandro wrote:

Two related OEIS sequence are A085724 and A002326.


Q1)  I could neither find a counterexample nor prove the statement. However, here is the proof of a (very) little step towards it. Therefore the search for counterexamples is limited to composite with 2n+1 composite only, that are nevertheless a lot.


Q2) No other N < 10^5



Giorgos wrote:

Q2: We know two more terms from A239638
n=130439 (prime) and 2n+1=260879 (prime)
n=406583 (prime) and 2n+1=813167 (prime)
F(n) is also prime in both cases because it is stated that 2^n-1 is semiprime


Oscar Volpatti wrote:

About Q1, the statement by Sebastián Martín Ruiz is true.
I'll prove it in two steps.
Step 1: if F(n) is a prime number, then n is prime too.
Step 2: if F(n) is an integer and n is a prime number, then 2*n+1 is prime too.

Given the Mersenne number M(n)=2^n-1 (exponent not notessarily prime), let A(n)=2*n+1 be its desired factor, so that F(n)=M(n)/A(n).
Also define functions B(n)=2^sqrt(n)-1 and C(n)=2^(n/2)-1, which will be used later.
Consider the following inequality chain:
n < A(n) < B(n) < C(n) < F(n) < M(n).
It necessarily holds for n large enough, because the given functions have different, increasing growth rates.
More precisely, the chain actually holds for every integer n>40; the bottleneck is inequality A(n)<B(n).

Proof by contradiction for n>40.
Assume that F(n) is a prime number but n is composite, so that n=x*y with 2<=x<=y.
As F(n) is prime, M(n) has no divisor d belonging to interval A(n)<d<F(n):
if d is coprime with F(n), then d<= A(n);
otherwise d must be a positive multiple of F(n), therefore d>=F(n).
But, as n has the proper factor y, M(n) has the proper factor M(y)=2^y-1, belonging to the forbidden interval:
n=x*y<=y^2, so y>=sqrt(n), so M(y)>=B(n)>A(n);
x>=2, so y=n/x<=n/2, so M(y)<=C(n)<F(n).
Contradiction, QED.

Exaustive search for 0<=n<=40.
F(n) is an integer for n in {0,3,8,11,15,20,23,35,36,39}.
F(n) is a prime for n in {11,23}; in both cases, n is prime too.

The value F(2)=3/5 is not an integer, so let n be an odd prime. A(n) divides M(n), so:
2^n == 1  mod  A(n),
4^n = (2^n)^2 == 1*1 == 1  mod  A(n).
By Miguel Pineda Martin's proof of puzzle 1133, A(n) is prime.

About Q2, next prime value of sequence F(n) is F(130439),
I tested prime arguments n<=200000; A(n) divides M(n) for about one thousand primes.  
I checked if M(n) has more small factors of the form q=2*n*k+1, with k<=10^6, excluding about 50% of candidates.
Then I checked if F(n) is a Fermat 3-PRP, obtaining a positive answer for n=130439.
According to, F(130439) is actually a proven prime, with certificate uploaded by Alan Mock in February 2023.


Emmanuel wrote:

The sequence  11, 23, 83, 131, 3359  is  A239638  in the OEIS.
There we find two extra terms : 130439  and  406583.
Also, in the comment lines we find that the next term (if existing) is > 500000






Records   |  Conjectures  |  Problems  |  Puzzles