A001262 -id:A001262 - cp's OEIS frontend

A062568 a(n) is the smallest n-digit strong pseudoprime (in base 2).

2047, 15841, 104653, 1004653, 10323769, 100463443, 1002261781, 10000321321, 100004790097, 1000002977551, 10000130243671, 100002236680837, 1000003918690669, 10000008250001701, 100000150553089531, 1000000274500018837, 10000003599249373469

Offset: 4

Shyam Sunder Gupta, Feb 13 2002

			a(1)=2047 because 2047 is the smallest 4-digit strong pseudoprime to base 2.

Patrick De Geest, Smallest n-digit pseudoprimes (base 2)
Index entries for sequences related to pseudoprimes

Cf. A001567, A068216, A067845, A001262, A062852.

Edited by Charles R Greathouse IV, Nov 01 2009

a(17)-a(20) from Charles R Greathouse IV, Mar 14 2011

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.

A067845 Largest n-digit pseudoprime (to base 2).

Original entry on oeis.org

645, 8911, 93961, 997633, 9995671, 99971821, 999828727, 9999109081, 99983971501, 999986341201, 9999946514845, 99999856404001, 999994510007533, 9999999191658001, 99999984319096601, 999999995115616561, 9999999995077192591

Offset: 3

Shyam Sunder Gupta, Feb 14 2002

			a(2)=8911, so largest pseudoprime (base 2) of 4 digits is 8911.

Patrick De Geest, Smallest n-digit Pseudoprimes
Index entries for sequences related to pseudoprimes

Cf. A001567, A068216, A001262, A062568, A062852.

More terms from Farideh Firoozbakht, Jan 11 2007

a(17)-a(19) from Amiram Eldar, Jun 30 2019

A071294 Number of witnesses for strong pseudoprimality of 2n+1, i.e., number of bases b, 1 <= b <= 2n, in which 2n+1 is a strong pseudoprime.

Original entry on oeis.org

2, 4, 6, 2, 10, 12, 2, 16, 18, 2, 22, 4, 2, 28, 30, 2, 2, 36, 2, 40, 42, 2, 46, 6, 2, 52, 2, 2, 58, 60, 2, 6, 66, 2, 70, 72, 2, 2, 78, 2, 82, 6, 2, 88, 18, 2, 2, 96, 2, 100, 102, 2, 106, 108, 2, 112, 2, 2, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 6, 2, 148, 150, 2, 2, 156, 2, 2

Offset: 1

J.-F. Guiffes (guiffes.jean-francois(AT)wanadoo.fr), Jun 11 2002

nonn

Number of integers b, 1 <= b <= 2n, such that if 2n = 2^k*m with odd m, then the sequence (b^m, b^(2*m), ..., b^(2^k*m)) modulo 2n+1 satisfies the Rabin-Miller test.
Comments from R. J. Mathar, Jul 03 2012 (Start)
The subsequence related to composite 2n+1 is characterized with records in A195328 and associated 2n+1 tabulated in A141768.
Let N = 2n+1 = product_{i=1..s} p_i^r_i be the prime factorization of the odd 2n+1. Related odd parts q and q_i are defined by N-1=2^k*q and p_i-1 = 2^(k_i)*q_i, with sorting such that k_1 <= k_2 <=k_3... Then a(n) = (1+sum_{j=0..k1-1} 2^(j*s)) *product_{i=1..s} gcd(q,qi).
Reduces to A006093 if 2n+1 is prime.
This might be correlated with 2*A195508(n). (End)

Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 98.

Amiram Eldar, Table of n, a(n) for n = 1..10000
F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881.
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Wikipedia, Strong pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A000265, A001221, A006093, A007814, A063994, A141768, A195328.
Cf. also A001262, A020229, A020231, A020233.
Different from A060684.

rabinmiller := proc(n,a); k := 0; mu := n-1; while irem(mu,2)=0 do k := k+1; mu := mu/2 od; G := a&^mu mod(n); h := 0; if G=1 then RETURN(1) else while h1 do h := h+1; G := G&^2 mod n; od; if h n-1 then RETURN(0) else RETURN(1) fi; if G=1 then RETURN(1); fi; fi; end; compte := proc(n) local l; RETURN(sum('rabinmiller(2*n+1,l)','l'=1..2*n)); end;
Maple code from R. J. Mathar, Jul 03 2012 (Start)
A000265 := proc(n)
     n/2^padic[ordp](n,2) ;
end proc:
a := proc(n)
     q := A000265(n-1) ;
     B := 1;
     s := 0 ;
     k1 := 10000000000000 ;
     for pf in ifactors(n)[2] do
         pi := op(1,pf) ;
         qi := A000265(pi-1) ;
         ki := ilog2((pi-1)/qi) ;
         k1 := min(k1,ki) ;
         B := B*igcd(q,qi) ;
         s := s+1 ;
     end do:
     1+add(2^(j*s),j=0..k1-1) ;
     return B*% ;
end proc:
seq(a(2*n+1),n=1..60) ;

o[n_] := (n-1)/2^IntegerExponent[n-1, 2]; a[n_?PrimeQ] := n-1; a[n_] := Module[{p = FactorInteger[n][[;;, 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2]& /@ (p - 1)]) - 1)/(2^om - 1))]; Table[a[n], {n, 3, 121, 2}] (* Amiram Eldar, Nov 08 2019 *)

For k = 2*n+1, a(k) = k - 1 if k is prime, otherwise, a(k) = (1 + 2^(omega(k)*nu(k)) - 1)/(2^omega(k)-1)) * Product_{p|k} gcd(od(k-1), od(p-1)), where omega(m) is the number of distinct prime factors of m (A001221), od(m) is the largest odd divisor of m (A000265) and nu(m) = min_{p|m} A007814(p-1). - Amiram Eldar, Nov 08 2019

Edited by Max Alekseyev, Sep 20 2018

Edited by N. J. A. Sloane, Nov 15 2019, merging R. J. Mathar's A182291 with this entry.

A072276 Strong pseudoprimes to bases 2 and 3.

Original entry on oeis.org

1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429, 16879501, 25326001, 27509653, 27664033, 28527049, 54029741, 61832377, 66096253, 74927161, 80375707, 101649241

Offset: 1

Francois R. Grieu, Jul 09 2002

nonn

Composites that pass the Miller-Rabin test for bases 2 and 3. The intersection of A001262 (strong pseudoprimes to base 2) and A020229 (strong pseudoprimes to base 3).

The Washington Bomfim link references a table with all terms up to 2^64. Data from Jan Feitsma and William Galway, see link below, permitted an easy determination of these terms. I tested the Mathematica function PrimeQ[n] with those numbers to verify that it is correct for all n < 2^64. - Washington Bomfim, May 13 2012

Don Reble, Table of n, a(n) for n = 1..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
D. Bleichenbacher, Thesis and strong pseudoprimes to 2 and 3 up to 10^16
Washington Bomfim, Table of n, a(n) for n=1..1499371 [a large file]
Jan Feitsma and William Galway, Tables of pseudoprimes and related data
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, section 4.2.3, Miller-Rabin test.
Eric Weisstein's World of Mathematics, Rabin-Miller test
Index entries for sequences related to pseudoprimes

Cf. A001262, A006945, A014233, A020229.

nmax = 10^8; 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}]]); A072276 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 2] && sppQ[n, 3] , Print[n]; AppendTo[ A072276, n]]]; A072276 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

A175865 Numbers k with property that 2^(k-1) == 1 (mod k) and 2^((3*k-1)/2) - 2^((k-1)/2) + 1 == 0 (mod k).

Original entry on oeis.org

3, 5, 11, 13, 19, 29, 37, 43, 53, 59, 61, 67, 83, 101, 107, 109, 131, 139, 149, 157, 163, 173, 179, 181, 197, 211, 227, 229, 251, 269, 277, 283, 293, 307, 317, 331, 347, 349, 373, 379, 389, 397, 419, 421, 443, 461, 467, 491, 499, 509, 523, 541, 547, 557, 563

Offset: 1

Alzhekeyev Ascar M, Sep 30 2010

nonn

All composites in this sequence are 2-pseudoprimes, see A001567.
The subsequence of composites begins: 3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 476971, 489997, ..., . - Robert G. Wilson v, Oct 02 2010
The sequence includes all the primes of A003629. - Alzhekeyev Ascar M, Mar 09 2011
If we consider the composites in this sequence which are in the modulo classes == 3 (mod 8) or == 5 (mod 8), they are moreover strong pseudoprimes to base 2 (see A001262). - Alzhekeyev Ascar M, Mar 09 2011
Are there any composites in this sequence which are *not* in the two modulo classes == {3,5} (mod 8)? - R. J. Mathar, Mar 29 2011

			3 is a term since 2^(3-1)-1 = 3 is divisible by 3, and 2^((3*3-1)/2) - 2^((3-1)/2) + 1 = 15 is divisible by 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001262, A001567, A003629.

fQ[n_] := PowerMod[2, n - 1, n] == 1 && Mod[ PowerMod[2, (3 n - 1)/2, n] - PowerMod[2, (n - 1)/2, n], n] == n - 1; Select[ Range@ 570, fQ] (* Robert G. Wilson v, Oct 02 2010 *)

More terms from Robert G. Wilson v, Oct 02 2010

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

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Original entry on oeis.org

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443

Offset: 1

Francois R. Grieu, Mar 05 2018

nonn

The definition's congruence is verified if n is a safe prime A005385 with m the corresponding Sophie Germain prime A005384; and for a few other n, which form the sequence.
If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).
That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).
Composite n are Euler pseudoprimes A006970, and strong pseudoprimes A001262 if m is odd. The smallest is a(6534) = (2^47+1)/3 = 46912496118443 = 283*165768537521 (cf. A303448). See Peter Košinár link.
Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).

			n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n-1 (mod 341*683) and m = 341 = 11*13 is composite.
n = 301703 = 2*150851+1 is in the sequence because 2^150851 == 301704 == n+1 (mod 150851*301703) and m = 150851 = 251*601 is composite.
n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.

Francois R. Grieu, Table of n, a(n) for n = 1..2796 (terms <2^42).
Peter Košinár, Report of a composite n, Math StackExchange, Mar 06 2018.
Fedor Petrov, Proof that the congruence and m prime imply n prime, MathOverflow.

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.

For[m=1,(n=2m+1)<4444444,++m,If[MemberQ[{n+1,3n-1},PowerMod[2,m,m*n]] &&!PrimeQ[m], Print[n]]] (* Francois R. Grieu, Mar 19 2018 *)

isok(n) = {if ((n % 2) && (m=(n-1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1) || (v == 3*n-1), return (1));); return (0);} \\ Michel Marcus, Mar 06 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 */

A062852 Largest n-digit strong pseudoprimes (in base 2).

Original entry on oeis.org

8321, 90751, 983401, 9995671, 99789673, 999828727, 9998721001, 99973476433, 999855751441, 9998974546471, 99999760517281, 999985147456681, 9999952887414577, 99999984319096601, 999999916795882627, 9999999995077192591

Offset: 4

Shyam Sunder Gupta, Feb 13 2002

			a(4)=8321 since 8321 is the largest 4-digit strong pseudoprime to base 2.

Patrick De Geest, Smallest n-digit pseudoprimes(base 2)
Index entries for sequences related to pseudoprimes

Cf. A001567, A068216, A067845, A001262, A062568.

Edited by Charles R Greathouse IV, Nov 01 2009

a(16)-a(19) from Charles R Greathouse IV, Mar 14 2011

cp's OEIS Frontend

A062568 a(n) is the smallest n-digit strong pseudoprime (in base 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A020234 Strong pseudoprimes to base 8.

Views

Author

Keywords

Links

Crossrefs

A067845 Largest n-digit pseudoprime (to base 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A071294 Number of witnesses for strong pseudoprimality of 2n+1, i.e., number of bases b, 1 <= b <= 2n, in which 2n+1 is a strong pseudoprime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A072276 Strong pseudoprimes to bases 2 and 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A175865 Numbers k with property that 2^(k-1) == 1 (mod k) and 2^((3*k-1)/2) - 2^((k-1)/2) + 1 == 0 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A298756 Least strong pseudoprime to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A020237 Strong pseudoprimes to base 11.

Views