A020230 -id:A020230 - cp's OEIS frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

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

Offset: 1

Gary Detlefs, Jul 02 2014

nonn

This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is an odd 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 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
Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+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

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

Cf. A001567, A003629, A070179.

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;

a(18) corrected by Jens Kruse Andersen, Jul 13 2014

A020233 Strong pseudoprimes to base 7.

Original entry on oeis.org

25, 325, 703, 2101, 2353, 4525, 11041, 14089, 20197, 29857, 29891, 39331, 49241, 58825, 64681, 76627, 78937, 79381, 87673, 88399, 88831, 102943, 109061, 137257, 144901, 149171, 173951, 178709, 188191, 197633, 219781, 227767, 231793, 245281

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..200 from R. J. Mathar)
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A005938, A001262, A020229, A020230, A020231, A020232.

A020232 Strong pseudoprimes to base 6.

Original entry on oeis.org

217, 481, 1111, 1261, 2701, 3589, 5713, 6533, 11041, 14701, 20017, 29341, 34441, 39493, 43621, 46657, 46873, 49141, 49661, 58969, 74023, 74563, 76921, 83333, 87061, 92053, 94657, 94697, 97751, 97921, 109061, 115921, 125563, 128627, 151387, 173377

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..210 from R. J. Mathar)
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A005937, A001262, A020229, A020230, A020231.

A020234 Strong pseudoprimes to base 8.

Original entry on oeis.org

9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, 15841, 16589, 19561, 24311, 24929, 29341, 41441, 42799, 45761, 49141, 52429, 52633, 54161, 55969, 56033, 59291, 61337, 65281, 66197, 74023, 74665, 77161, 80581, 85489, 87061

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..237 from R. J. Mathar)
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A020137, A001262, A020229, A020230, A020231, A020232, A020233.

A298756 Least strong pseudoprime to base n.

Original entry on oeis.org

2047, 121, 341, 781, 217, 25, 9, 91, 9, 133, 91, 85, 15, 1687, 15, 9, 25, 9, 21, 221, 21, 169, 25, 217, 9, 121, 9, 15, 49, 15, 25, 545, 33, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 481, 9, 65, 49, 25, 49, 25, 51, 9, 55, 9, 55, 25, 57, 15, 481, 15, 9, 529, 9, 33

Offset: 2

Amiram Eldar, Jan 26 2018

nonn

a(n)=9 if and only if n == 1 or 8 (mod 9). - Robert Israel, Mar 27 2018

Robert Israel, Table of n, a(n) for n = 2..10000
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.

filter:= proc(n,b) local d,s,r;
  if isprime(n) then return false fi;
  s:= padic:-ordp(n-1,2);
  d:= (n-1)/2^s;
  if b &^ d mod n = 1 then return true fi;
  for r from 0 to s-1 do
    if b &^ (d*2^r) + 1 mod n = 0 then return true fi
  od;
false
end proc:
f:= proc(b) local n;
  for n from 9 by 2 do if filter(n,b) then return n fi od
end proc:
map(f, [$2..100]); # Robert Israel, Mar 27 2018

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := Module[{ans=False},s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, ans=True, Do[If[PowerMod[b, d*2^r, n] == n-1, ans=True], {r, 0, s-1}]];ans];leastSPP[b_] := Module[{k=3}, While[ !sppQ[k,b],k+=2];k]; Table[leastSPP[n],{n, 2, 100}] (* after Jean-François Alcover at A020229 *)

is_a001262(n, a)={ (bittest(n, 0) && !isprime(n) && n>8) || return; my(s=valuation(n-1, 2)); if(1==a=Mod(a, n)^(n>>s), return(1)); while(a!=-1 && s--, a=a^2); a==-1} \\ after M. F. Hasler in A001262
a(n) = forcomposite(c=1, , if(is_a001262(c, n), return(c))) \\ Felix Fröhlich, Mar 28 2018

A020237 Strong pseudoprimes to base 11.

Original entry on oeis.org

133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711, 23377, 43213, 43739, 47611, 48283, 49601, 50737, 50997, 56057, 58969, 68137, 74089, 85879, 86347, 87913, 88831, 102173, 111055, 114211, 115231, 137149, 139231, 171601, 172369, 193249, 196555

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..636 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A020139, A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A020236.

/* insert A001262 code here */
isA020237(n)={
        isStrongPsp(n,11)
}
{
for(n=1,10000000000,
        if(isA020237(n), print(n) ;) ;
) ;
} /* R. J. Mathar, Mar 07 2012 */

A020236 Strong pseudoprimes to base 10.

Original entry on oeis.org

9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139, 100001, 102173, 118301, 118957, 134863, 139231, 148417, 158497, 166499, 188191, 196651, 201917, 216001, 226273, 231337, 237169, 251251, 287809, 302177

Offset: 1

David W. Wilson

nonn

			From _Alonso del Arte_, Aug 10 2018: (Start)
9 is a strong pseudoprime to base 10. It's not enough to check that 10^8 = 1 mod 9. Since 8 = 1 * 2^3, we also need to verify that 10 = 1 mod 9 and 10^2 = 1 mod 9 as well. Since these are both equal to 1, we see that 9 is indeed a strong pseudoprime to base 10.
91 is also a strong pseudoprime to base 10. Besides checking that 10^90 = 1 mod 91, since 90 = 45 * 2, we also check that 10^45 = -1 mod 91; the -1 is enough to satisfy the definition of a strong pseudoprime.
99 is a Fermat pseudoprime to base 10 (see A005939) but it is not a strong pseudoprime to base 10. Although 10^98 = 1 mod 99, since 98 = 49 * 2, we have to check 10^49 mod 99, and there we find not -1 nor 1 but 10. Therefore 99 is not in this sequence. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..203 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A005939, A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.

strongPseudoprimeQ[b_, n_] := Module[{rems = Table[PowerMod[b, (n - 1)/2^expo, n], {expo, 0, IntegerExponent[n - 1,2]}]}, (rems[[-1]] == 1 || MemberQ[rems, n - 1]) && PowerMod[b, n - 1, n] == 1]; max = 5000; Select[Complement[Range[2, max], Prime[Range[PrimePi[max]]]], strongPseudoprimeQ[10, #] &] (* Alonso del Arte, Aug 10 2018 *)

A020238 Strong pseudoprimes to base 12.

Original entry on oeis.org

91, 133, 145, 247, 1649, 1729, 2821, 8911, 9073, 10585, 13051, 13333, 16471, 19517, 20737, 21361, 24013, 24727, 26467, 29539, 31483, 31621, 34219, 34861, 35881, 38311, 38503, 40321, 53083, 67861, 79381, 79501, 88831, 97351, 115231, 121301, 131977

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..210 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A020140, A001262 (base 2), A020229 (base 3), A020230, A020231, A020232, A020233, A020234, A020235, A020236, A020237.

A298757 Numbers k with record value of the least strong pseudoprime to base k (A298756).

Original entry on oeis.org

2, 1320, 4712, 5628, 7252, 7852, 14787, 17340, 61380, 78750, 254923, 486605, 1804842, 4095086, 12772344, 42162995

Offset: 1

Amiram Eldar, Jan 26 2018

The record strong pseudoprimes are 2047, 4097, 4711, 5627, 7251, 7851, 9409, 10261, 11359, 13747, 18299, 25761, 32761, 38323, 40501, 97921, ...

Index entries for sequences related to pseudoprimes

Cf. A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A298756.

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := Module[{ans=False},s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, ans=True, Do[If[PowerMod[b, d*2^r, n] == n-1, ans=True], {r, 0, s-1}]];ans]; smallestSPP[b_] := Module[ {k=3}, While[ !sppQ[k,b],k+=2];k ]; sm=0;a={};Do[s=smallestSPP[b];If[s>sm,sm=s;AppendTo[a,b]], {b,2,10^4}];a (* after Jean-François Alcover at A020229 *)

lista(nn) = {my(m=0); for (n=2, nn, my(r=a298756(n)); if (r>m, m =r; print1(n, ", ")););} \\ Michel Marcus, Jan 31 2022; using pari code in A298756

a(9)-a(16) from Jonathan Pappas, Jan 31 2022

cp's OEIS Frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

A020233 Strong pseudoprimes to base 7.

Views

Author

Keywords

Links

Crossrefs

A020232 Strong pseudoprimes to base 6.

Views

Author

Keywords

Links

Crossrefs

A020234 Strong pseudoprimes to base 8.

Views

Author

Keywords

Links

Crossrefs

A298756 Least strong pseudoprime to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A020237 Strong pseudoprimes to base 11.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A020238 Strong pseudoprimes to base 12.

Views

Author

Keywords

Links

Crossrefs

A298757 Numbers k with record value of the least strong pseudoprime to base k (A298756).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions