

A244628


Composite numbers n such that n == 3 (mod 8) and 2^((n1)/2) == 1 (mod n).


4



476971, 877099, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 3090091, 3116107, 5256091, 5919187, 7883731, 9371251, 11081459, 11541307, 12263131, 13057787, 13338371, 15976747, 17134043, 18740971, 19404139, 20261251, 21623659, 22075579, 24214051
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

This sequence contains the n mod 8 = 3 pseudoprimes to the following modified Fermat primality criterion:
If p is a prime congruent to {3,5} mod 8 then 2^((p1)/2) mod p = p1.
This conjecture has been tested to 10^8.
This modified primality test has far fewer pseudoprimes than the 2^(n1) 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^(n1) mod n = 1 and 5^(n1) 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


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, (n1)/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

Cf. A003629, A070179, A175865.
Sequence in context: A183659 A213994 A201226 * A290050 A244086 A015332
Adjacent sequences: A244625 A244626 A244627 * A244629 A244630 A244631


KEYWORD

nonn


AUTHOR

Gary Detlefs, Jul 02 2014


STATUS

approved



