OFFSET
1,1
COMMENTS
This sequence contains the n mod 8 = 3 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is a prime congruent to {3,5} mod 8 then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
This modified primality test has far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a much higher probability of success. The number of pseudoprimes up to 10^k for the two tests are:
10^3 0 0
10^4 0 2
10^5 0 5
10^6 2 14
10^7 16 48
This sequence appears to be a subset of the composites in A175865.
The n mod 8 = 3 pseudoprimes are much rarer than the n mod 8 = 5 pseudoprimes. There are 16 terms < 10^7. If the additional constraints 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 are added, no terms remain.
Number of terms < 10^k: 0, 0, 0, 0, 0, 2, 16, 50, 132, ..., . - Robert G. Wilson v, Jul 21 2014
Number of terms < 10^k for k=5..15: 0, 2, 16, 50, 132, 341, 876, 2330, 6234, 16625, 44885. - Jens Kruse Andersen, Jul 27 2014
It appears that the terms of the sequence are also the composite numbers of A294912. - Hilko Koning, Dec 05 2019
Also composite numbers 2k+1 with k odd such that 2k+1 | 2^k+1. - Hilko Koning, Jan 27 2022
Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k . Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - Hilko Koning, Feb 04 2022
LINKS
Jens Kruse Andersen, Table of n, a(n) for n = 1..10000 (first 132 terms from Robert G. Wilson v)
MAPLE
for n from 3 to 10^8 by 8 do if Power(2, (n-1)/2) mod n = n -1 and not isprime(n) then print(n) fi od
MATHEMATICA
fQ[n_] := !PrimeQ@ n && PowerMod[2, (n - 1)/2, n] == n - 1; k = 3; lst = {}; While[k < 10^8, If[fQ@ k, AppendTo[lst, k]]; k += 8]; lst (* Robert G. Wilson v, Jul 21 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gary Detlefs, Jul 02 2014
STATUS
approved