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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1. 13
3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 489997, 800605, 838861, 873181, 1004653, 1251949, 1373653, 1509709, 1678541, 1811573, 1987021, 2269093, 2284453, 2387797, 2746477, 2909197, 3400013, 3429037, 3539101, 3605429, 4360621, 4502485, 5590621, 5599765 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:

If p is an odd prime congruent to (3,5} mod 8 then 2^((p-1)/2) mod p = k-1.

This conjecture has been tested to 10^8.

This criterion produces far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a higher probability of success. The number of pseudoprimes for the two tests up to 10^k are:

10^5   5   26      19.23 %

10^6   13  78      16.66 %

10^7   40  228     17.54 %

There are 40 terms < 10^7. If an additional constraint 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 is added, only 4 terms remain: (29341, 314821, 873181, 9863461).

This sequence appears to be a subset of A175865, A001262, A047713, A020230.

Number of terms below 10^k for k = 5..15: 5, 13, 40, 132, 369, 975, 2534, 6592, 17403, 45801, 122473. The corresponding numbers for 2^(n-1) mod n = 1: 26, 78, 228, 637, 1718, 4505, 11645, 29902, 76587, 197455, 513601. - Jens Kruse Andersen, Jul 13 2014

LINKS

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

MAPLE

for n from 5 to 10^7 by 8 do if 2^((n-1)/2) mod n = n-1 and not isprime(n) then print(n) fi od;

CROSSREFS

Cf. A001567, A003629, A070179.

Sequence in context: A141629 A116460 A245482 * A270204 A293626 A152506

Adjacent sequences:  A244623 A244624 A244625 * A244627 A244628 A244629

KEYWORD

nonn

AUTHOR

Gary Detlefs, Jul 02 2014

EXTENSIONS

a(18) corrected by Jens Kruse Andersen, Jul 13 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 September 20 01:58 EDT 2019. Contains 327207 sequences. (Running on oeis4.)