A possible Lucas-Lehmer type test for primes of the form 2^k+3

[Davide Rotondo]

I would like to share a computational observation and a conjecture.

Starting from the Lucas-Lehmer recurrence:

s(0) = 4 s(n+1) = s(n)^2 - 2

I considered the numbers:

N = 2^(n-1) + 3

and the following expression:

T(n) = (s(n-2)/2 + (2^n - 1)) / (2^(n-1) + 3)

The experiments suggest that this expression is connected with the primality of N, but with two different cases depending on the parity of n.

For odd n, whenever N = 2^(n-1)+3 is prime, I obtain:

s(n-2)/2 + (2^n - 1) ≡ 0 (mod N)

Examples:

n = 3 N = 7 residue = 0 n = 5 N = 19 residue = 0 n = 7 N = 67 residue = 0 n = 13 N = 4099 residue = 0 n = 17 N = 65539 residue = 0 n = 19 N = 262147 residue = 0 n = 29 N = 268435459 residue = 0 n = 31 N = 1073741827 residue = 0

For even n, the same expression does not give zero. Instead, for prime values of N, I observe:

s(n-2)/2 + (2^n - 1) ≡ -9 (mod N)

Examples:

n = 8 N = 131 residue = 122 = N-9 n = 16 N = 32771 residue = 32762 = N-9 n = 56 N = 36028797018963971 residue = N-9

Therefore I conjecture the following parity-dependent Lucas-Lehmer type behavior:

For N = 2^(n-1)+3 prime:

Case 1: n odd

s(n-2)/2 + (2^n - 1) ≡ 0 (mod N)

Case 2: n even

s(n-2)/2 + (2^n - 1) ≡ -9 (mod N)

Equivalently:

s(n-2)/2 ≡ 7 (mod N) if n is odd s(n-2)/2 ≡ -2 (mod N) if n is even

The numerical evidence suggests that the Lucas-Lehmer sequence detects the primality of numbers of the form 2^k+3 in the odd exponent case, while the even exponent case requires a correction term.

I would be interested in any theoretical interpretation or possible connections with Lucas sequences, cyclotomic identities, or known primality tests for numbers of the form 2^k+3.

Davide

[Davide Rotondo]

Dear Community,

What do you think of this conjecture?

Can You tell me if it works?

Davide

[Davide Rotondo]

Dear, I want to share with this discussion in mathoverflow https://mathoverflow.net/a/513622/596007

Davide

[Davide Rotondo]

A possible Lucas-Lehmer-Riesel type test for primes of the form x*2^n + 3.

I am studying a possible extension of the Lucas-Lehmer-Riesel idea to numbers of the form:

N = x*2^n + 3

The classical Lucas-Lehmer-Riesel test uses the recurrence:

s(n+1) = s(n)^2 - 2

with a suitable initial value.

My idea is to search for a similar structure for numbers ending with +3.

A first interesting case is:

N = 5*2^(n-1) + 3

using the initial value:

s(0) = 724

and the recurrence:

s(n+1) = s(n)^2 - 2

I studied the expression:

T(n) = (s(n-2)/2 + (5*2^n - 1) + k) / (5*2^(n-1) + 3)

where k is the smallest non-negative integer that makes T(n) an integer.

The first results show an interesting pattern.

For even n, when N is prime:

k = 0

Examples:

n = 4 → N = 43 → k = 0

n = 6 → N = 163 → k = 0

n = 8 → N = 643 → k = 0

n = 12 → N = 10243 → k = 0

For odd n greater than 3, when N is prime:

k = 9

Examples:

n = 5 → N = 83 → k = 9

n = 9 → N = 1283 → k = 9

n = 13 → N = 20483 → k = 9

n = 19 → N = 1310723 → k = 9

n = 21 → N = 5242883 → k = 9

The first case is exceptional:

n = 3 → N = 23 → k = 5

At the moment this is only an experimental conjecture, but the structure seems to show similarities with Lucas-Lehmer-Riesel type tests.

What do you think?

Davide