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

On July 23, 2026 Davide Rotondo sent the following Conjecture.

I would like to share with you 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.

Also I hope you can prove my conjecture and look (using this test) to the biggest prime number of the form 2^n + 3.