A001262 -id:A001262 - cp's OEIS frontend

A020229 Strong pseudoprimes to base 3.

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801

Offset: 1

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..24767 (first 752 terms from R. J. Mathar)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001262, A072276, A056915, A074773, A005935.

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s-1}]]); A020229 = {}; lst = {}; k = 3; While[k < 500000, If[sppQ[k, 3], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

is_A020229(n,b=3)={ bittest(n,0) || return;ispseudoprime(n) && return;my(d=(n-1)>>valuation(n-1,2));Mod(b,n)^d==1 || until(n-1<=d*=2,Mod(b,n)^d+1 || return(1))} \\ M. F. Hasler, Jul 19 2012

A164294 Primes prime(k) such that all integers in [(prime(k-1)+1)/2,(prime(k)-1)/2] are composite, excluding those primes in A080359.

Original entry on oeis.org

131, 151, 229, 233, 311, 571, 643, 727, 941, 1013, 1051, 1153, 1373, 1531, 1667, 1669, 1723, 1783, 1787, 1831, 1951, 1979, 2029, 2131, 2213, 2239, 2311, 2441, 2593, 2621, 2633, 2659, 2663, 2887, 3001, 3011, 3019, 3121, 3169, 3209, 3253, 3347, 3413, 3457

Offset: 1

Vladimir Shevelev, Aug 12 2009

nonn

The primes of A080359 larger than 3 all have the property that the integers in the interval selected by halving the value of the preceding prime and halving their own value are all composite. This sequence here collects the primes that are not in A080359 but still share this property of the prime-free subinterval.

			For the prime 1531=A000040(242), the preceding prime is A000040(241)=1523, and the integers from (1523+1)/2 = 762 up to (1531-1)/2 = 765 are all composite, as they fall in the gap between A000040(135) and A000040(136). In addition, 1531 is not in A080359, which adds 1531 to this sequence here.

Jean-François Alcover, Table of n, a(n) for n = 1..1106
V. Shevelev, On critical small intervals containing primes, arXiv:0908.2319 [math.NT], 2009. [From _Vladimir Shevelev_, Aug 20 2009]
V. Shevelev, Ramanujan and Labos primes, their generalizations, and classifications of primes, J. Integer Seq. 15 (2012) Article 12.5.4.

Cf. A080359, A104272, A164288, A001262, A001567, A062568, A141232, A164368.

maxPrime = 3500;
kmax = PrimePi[maxPrime];
A164333 = Select[Table[{(Prime[k - 1] + 1)/2, (Prime[k] - 1)/2}, {k, 3, kmax}], AllTrue[Range[#[[1]], #[[2]]], CompositeQ] &][[All, 2]]*2 + 1;
b[1] = 2; b[n_] := b[n] = Module[{k = b[n - 1]}, While[(PrimePi[k] - PrimePi[Quotient[k, 2]]) != n, k++]; k];
A080359 = Reap[For[n = 1, b[n] <= maxPrime, n++, Sow[b[n]]]][[2, 1]];
Complement[A164333, A080359] (* Jean-François Alcover, Sep 14 2018 *)

okprime(p) = { my(k = primepi(p)); for (i = (prime(k-1)+1)/2, (prime(k)-1)/2, if (isprime(i), return (0));); return (1);}
lista(nn) = {vlp = readvec("b080359.txt"); forprime (p=2, nn, if (! vecsearch(vlp, p) && okprime(p), print1(p, ", ")););} \\ Michel Marcus, Jan 15 2014

A164333 \ A080359.

Extended beyond 571 by R. J. Mathar, Oct 02 2009

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

Original entry on oeis.org

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

A020231 Strong pseudoprimes to base 5.

Original entry on oeis.org

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, 100651, 102311, 104721, 112141, 121463, 133141, 141361, 146611, 195313, 211951, 216457, 222301, 251521, 289081, 290629, 298271, 315121

Offset: 1

David W. Wilson

nonn

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

Cf. A005936, A001262 (base-2 SPP), A020229 (base-3 SPP), A215568 (SPP to bases 2 & 5), A215566 (SPP to bases 3 & 5), A056915 (SPP to bases 2, 3 & 5), A074773 (SPP to bases 2, 3, 5 & 7).

nmax = 400000; sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s - 1}]]); A020231 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 5] == True, Print[n]; AppendTo[A020231, n]]]; A020231 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

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.

A164333 Primes prime(k) such that all integers in the interval [(prime(k-1)+1)/2, (prime(k)-1)/2] are composite numbers.

Original entry on oeis.org

13, 19, 31, 43, 53, 61, 71, 73, 101, 103, 109, 113, 131, 139, 151, 157, 173, 181, 191, 193, 199, 229, 233, 239, 241, 251, 269, 271, 283, 293, 311, 313, 349, 353, 373, 379, 409, 419, 421, 433, 439, 443, 463, 491, 499, 509, 523, 571, 577, 593, 599, 601, 607, 613, 619, 643

Offset: 1

Vladimir Shevelev, Aug 13 2009

nonn

Let p_k be the k-th prime. A prime p is in the sequence iff the interval of the form (2p_k, 2p_(k+1)), containing p, also contains a prime less than p. The sequence is connected with the following classification of primes: the first two primes 2,3 form a separate set of primes; let p >= 5 be in the interval (2p_k, 2p_(k+1)), then 1) if in this interval there are only primes greater than p, then p is called a right prime; 2) if in this interval there are only primes less than p, then p is called a left prime; 3) if in this interval there are primes both greater and less than p, then p is called a central prime; 4) if this interval does not contain other primes, then p is called an isolated prime. In particular, the right primes form sequence A166307, and all Ramanujan primes (A104272) greater than 2 are either right or central primes; the left primes form sequence A182365, and all Labos primes (A080359) greater than 3 are either left or central primes; the central primes form A166252 and the isolated primes form A166251. [Vladimir Shevelev, Oct 10 2009] [Sequence reference updated by Peter Munn, Jun 01 2023]

Disjoint union of A166252 and A182365. - Peter Munn, Jun 01 2023 [an edited version of a contribution by Vladimir Shevelev in 2009]

			Let p=53. We see that 2*23<53<2*29. Since the interval (46, 58) contains prime 47<53 and does not contain any prime more than 53, then, by the considered classification 53 is left prime and it is in the sequence. [_Vladimir Shevelev_, Oct 10 2009]

V. Shevelev, On critical small intervals containing primes, arXiv:0908.2319 [math.NT], 2009.
V. Shevelev, Ramanujan and Labos Primes, Their Generalizations, and Classifications of Primes, J. Int. Seq. 15 (2012) # 12.5.4
J. Sondow, J. W. Nicholson, and T. D. Noe, Ramanujan Primes: Bounds, Runs, Twins, and Gaps, arXiv:1105.2249 [math.NT], 2011; J. Integer Seq. 14 (2011) Article 11.6.2.

Cf. A080359, A104272, A164288, A164294, A164332, A001262, A001567, A062568, A141232.
Cf. A164368, A164554, A166251, A166252. [Vladimir Shevelev, Oct 10 2009]
Cf. A166307, A182365.

isA164333 := proc(n)
        local i ;
        if isprime(n) and n > 3 then
                for i from (prevprime(n)+1)/2 to (n-1)/2 do
                        if isprime(i) then
                                return false;
                        end if;
                end do;
                return true;
        else
                false;
        end if;
end proc:
for i from 2 to 700 do
        if isA164333(i) then
                printf("%d,",i);
        end if;
end do: # R. J. Mathar, Oct 29 2011

kmax = 200; Select[Table[{(Prime[k - 1] + 1)/2, (Prime[k] - 1)/2}, {k, 3, kmax}], AllTrue[Range[#[[1]], #[[2]]], CompositeQ]&][[All, 2]]*2 + 1 (* Jean-François Alcover, Nov 14 2017 *)

{A080359} union {A164294} = {this sequence} union {2,3}. - Vladimir Shevelev, Oct 29 2011

A164368(2)A164368(3)A164368(4)Vladimir Shevelev, Oct 10 2009]

Definition rephrased by R. J. Mathar, Oct 02 2009

A158358 Pseudoprimes to base 2 that are not squarefree, including the even pseudoprimes.

Original entry on oeis.org

1194649, 12327121, 3914864773, 5654273717, 6523978189, 22178658685, 26092328809, 31310555641, 41747009305, 53053167441, 58706246509, 74795779241, 85667085141, 129816911251, 237865367741, 259621495381, 333967711897, 346157884801, 467032496113, 575310702877, 601401837037, 605767053061

Offset: 1

Rick L. Shepherd, Mar 16 2009

nonn

Intersection of (A001567 U A006935) and A013929. Also, intersection of A015919 and A013929.
The first six terms are given by Ribenboim, who references calculations by Lehmer and by Pomerance, Selfridge & Wagstaff supporting "that the only possible factors p^2 (where p is a prime less than 6*10^9) of any pseudoprime, must be 1093 or 3511." Ribenboim states that the first four terms are strong pseudoprimes. The first two terms are squares of these Wieferich primes, 1093^2 and 3511^2.
Only Wieferich primes (A001220) can appear with an exponent greater than one. In particular, all members of this sequence are divisible by a square of a Wieferich prime. Up to 67 * 10^14 the only Wieferich primes are 1093 and 3511. - Charles R Greathouse IV, Sep 12 2012
The first term divisible by the squares of two (Wieferich) primes is a(11870) = 4578627124156945861 = 29 * 71 * 151 * 1093^2 * 3511^2. See A219346. - Charles R Greathouse IV, Sep 20 2012
Unless there are other Wieferich primes besides 1093 and 3511, the sequence is the union of A247830 and A247831. - Max Alekseyev, Nov 26 2017
The even terms are listed in A295740. - Max Alekseyev, Nov 26 2017 [Their indices in this sequence are 2882, 3476, 3573, 4692, 5434, 5581, 6332, 8349, 8681, 9515, ... - Jianing Song, Feb 08 2019]

			a(6) = 22178658685 = 5 * 47 * 79 * 1093^2 is a pseudoprime that is not squarefree.

P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, NY, 1991, pp. 77, 83, 167.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10010 (The even terms inserted by Jianing Song)
Jan Feitsma, W search: non-squarefree pseudoprimes
R. G. E. Pinch, The pseudoprimes up to 10^13, Lecture Notes in Computer Science, 1838 (2000), 459-473. - _Felix Fröhlich_, Apr 16 2014
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
Index entries for sequences related to pseudoprimes

Cf. A001567, A013929, A001220, A001262, A219346, A247830, A247831, A295740.

list(lim)=vecsort(concat(concat(apply(p->select(n->Mod(2, n)^(n-1)==1, p^2*vector(lim\p^2\2, i, 2*i-1)), [1093, 3511])), select(n->Mod(2, n)^n==2, 2*3511^2*vector(lim\3511^2\2, i, i))), , 8) \\ valid up to 4.489 * 10^31, Charles R Greathouse IV, Sep 12 2012, changed to include the even terms by Jianing Song, Feb 07 2019

More terms from Max Alekseyev, May 09 2010

Name changed by Jianing Song, Feb 07 2019 to include the even pseudoprimes to base 2 (A006935) as was suggested by Max Alekseyev.

A074773 Strong pseudoprimes to bases 2, 3, 5 and 7.

Original entry on oeis.org

3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981, 2152302898747, 2273312197621, 2366338900801, 3343433905957, 3461715915661, 3474749660383, 3477707481751, 4341937413061, 4777422165601, 5537838510751

Offset: 1

Don Reble, Sep 07 2002

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Washington Bomfim, Table with all 16757 terms up to 2^64
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.
Eric Weisstein's World of Mathematics, Miller's Primality Test
Index entries for sequences related to pseudoprimes

Cf. A001262, A020229, A020231, A020233, A056915.

sprp(n,b)=my(s=valuation(n-1,2),d=Mod(b,n)^(n>>s)); if(d==1, return(1)); for(i=1,s-1, if(d==-1, return(1)); d=d^2;); d==-1
is(n)=sprp(n,2) && sprp(n,3) && sprp(n,5) && sprp(n,7) && !isprime(n) \\ Charles R Greathouse IV, Sep 14 2015

b-file, link, and editing from Charles R Greathouse IV, Aug 14 2010

A020230 Strong pseudoprimes to base 4.

Original entry on oeis.org

341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, 13747, 14491, 15709, 15841, 19951, 29341, 31621, 42799, 49141, 49981, 52633, 60787, 65077, 65281, 74665, 80581, 83333, 85489, 88357, 90751, 104653, 123251, 129921, 130561, 137149

Offset: 1

David W. Wilson

nonn

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

Cf. A020136 (base 4), A001262 (base 2), A020229 (base 3), A020231 (base 5), A020232 (base 6), A020233 (base 7), A020234 (base 8), A020235 (base 9), A020236 (base 10), A020237 (base 11), A020238 (base 12).

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.

cp's OEIS Frontend

A020229 Strong pseudoprimes to base 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A164294 Primes prime(k) such that all integers in [(prime(k-1)+1)/2,(prime(k)-1)/2] are composite, excluding those primes in A080359.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A020231 Strong pseudoprimes to base 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A020233 Strong pseudoprimes to base 7.

Views

Author

Keywords

Links

Crossrefs

A164333 Primes prime(k) such that all integers in the interval [(prime(k-1)+1)/2, (prime(k)-1)/2] are composite numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A158358 Pseudoprimes to base 2 that are not squarefree, including the even pseudoprimes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A074773 Strong pseudoprimes to bases 2, 3, 5 and 7.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI