login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244628 Composite numbers n such that n == 3 (mod 8) and 2^((n-1)/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^((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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 15:05 EDT 2019. Contains 322209 sequences. (Running on oeis4.)