A141768 -id:A141768 - cp's OEIS frontend

A195328 Number of bases to which terms of A141768 are strong pseudoprimes.

2, 4, 6, 18, 50, 54, 162, 242, 450, 486, 882, 1058, 1782, 3042, 3078, 4050, 5202, 9522, 19602, 22050, 36450, 46818, 54450, 66978, 71442, 95922, 124002, 149058, 183618, 190962, 238050, 240570, 263538, 277830, 328050, 466578, 684450, 816642, 977202

Offset: 1

Charles R Greathouse IV, Sep 15 2011

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..5476
Index entries for sequences related to pseudoprimes

Cf. A141768, A195327.

star(n)={n--; n>>valuation(n, 2)};
bases(n)=my(f=factor(n)[, 1], nu=valuation(f[1]-1, 2), nn = star(n)); for(i=2, #f, nu = min(nu, valuation(f[i] - 1, 2)); ); (1 + (2^(#f * nu) - 1) / (2^#f - 1)) * prod(i=1, #f, gcd(nn, star(f[i]))); \\ Given a value of A141768, this function transforms it to a term of this sequence.

A129521 Numbers of the form pq, p and q prime with q=2p-1.

Original entry on oeis.org

6, 15, 91, 703, 1891, 2701, 12403, 18721, 38503, 49141, 79003, 88831, 104653, 146611, 188191, 218791, 226801, 269011, 286903, 385003, 497503, 597871, 665281, 721801, 736291, 765703, 873181, 954271, 1056331, 1314631, 1373653, 1537381

Offset: 1

Reinhard Zumkeller, Apr 19 2007

nonn

All terms are Fermat 4-pseudoprimes, i.e., satisfy 4^n == 4 (mod n). See A020136 and A122781.

David W. Wilson, Table of n, a(n) for n = 1..1000
D. E. Iannucci, When the small divisors of a natural number are in arithmetic progression, INTEGERS, Electronic Journal of Combinatorial Number Theory, #77, 2018. See p. 9.

Cf. A005382, A005383.
Subsequence of A006881, A129510, and A122781.
Intersection of A000384 and A001358, "hexagonal semiprimes". - Wesley Ivan Hurt, Jul 04 2013
Cf. A141768, A191311, A191592, A245365, A259676, A259677.

a129521 n = p * (2 * p - 1) where p = a005382 n
-- Reinhard Zumkeller, Nov 10 2013

[2*n^2-n: n in [0..1000]|IsPrime(n) and IsPrime(2*n-1)]; // Vincenzo Librandi, Dec 27 2010

p = Select[Prime[Range[155]], PrimeQ[2# - 1] &]; p (2p - 1) (* Robert G. Wilson v, Sep 11 2011 *)

forprime(p=2,10000,q=2*p-1;if(isprime(q),print1(p*q,", ")))

a(n) = A005382(n)*A005383(n).

A083876 Least pseudoprime to base 2 through base prime(n).

Original entry on oeis.org

341, 1105, 1729, 29341, 29341, 162401, 252601, 252601, 252601, 252601, 252601, 252601, 1152271, 2508013, 2508013, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 6733693, 6733693, 6733693

Offset: 1

Robert G. Wilson v, May 06 2003

nonn

Records: 341, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, .... - Robert G. Wilson v, May 11 2012
Conjecture: for n > 1, a(n) is the smallest Carmichael number k with lpf(k) > prime(n). It seems that such Carmichael numbers have exactly three prime factors. - Thomas Ordowski, Apr 18 2017
The conjecture is true if a(n) < A285549(n) for all n > 1. It holds for all a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
If prime(n) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= prime(n). - Thomas Ordowski, Mar 05 2018
By this conjecture in the second comment, a(n) <= A135720(n+1), with equality for n > 1 iff a(n) < a(n+1), namely for n = 2, 3, 5, 6, 12, 13, 15, 25, 28, 29, ... For such n, a(n) gives all terms of A300629 > 561. - Thomas Ordowski, Mar 10 2018

Giovanni Resta, Table of n, a(n) for n = 1..1000 (first 100 terms from Robert G. Wilson v)

Cf. A002997, A001567, A052155, A083737, A087788, A083739, A135720, A141768, A250199, A271221, A285549, A300629.

k = 4; Do[l = Table[ Prime[i], {i, 1, n}]; While[ PrimeQ[k] || Union[PowerMod[l, k - 1, k]] != {1}, k++ ]; Print[k], {n, 1, 29}]

isps(k, n) = {if (isprime(k), return (0)); my(nbok = 0); for (b=2, prime(n), if (Mod(b, k)^(k-1) == 1, nbok++, break)); if (nbok==prime(n)-1, return (1));}
a(n) = {my(k=2); while (!isps(k, n), k++); return (k);} \\ Michel Marcus, Apr 27 2018

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.

A181782 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.

Original entry on oeis.org

25, 49, 65, 85, 91, 121, 125, 133, 145, 169, 175, 185, 205, 217, 221, 231, 247, 259, 265, 289, 301, 305, 325, 341, 343, 361, 365, 377, 385, 403, 425, 427, 435, 445, 451, 469, 475, 481, 485, 493, 505, 511, 529, 533, 545, 553, 559, 561, 565, 589, 595, 625, 629, 637, 645, 651, 671, 679, 685, 689, 697

Offset: 1

Karsten Meyer, Nov 10 2010

nonn

			49 is a strong pseudoprime to the bases 18, 19, 30 and 31, so 49 is in the sequence.

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

Cf. A141768.

/* function sppq() from http://www.jjj.de/pari/rabinmiller.gpi */
sppq(n,a)=
{ /* Return whether n is a strong pseudoprime to base a (Rabin Miller) */
    local(q, t, b, e);
    q = n-1;  t = 0;  while ( 0==bitand(q,1), q\=2; t+=1 );
    /* here  n==2^t*q+1 */
    b = Mod(a, n)^q;
    if ( 1==b, return(1) );
    e = 1;
    while ( eJoerg Arndt, Dec 27 2010 */

select( is_A181782(n)={bittest(n,0) && !isprime(n) && for(a=2,n-2, my(t=valuation(n-1,2), b=Mod(a,n)^(n>>t)); b==1&&return(1); while(t-->0 && b!=-1 && b!=1, b=b^2); b==-1&&return(1))}, [1..700]) \\ Defines is_A181782(): select(...) gives a check and illustration for free. Inside the for loop is the exact equivalent of the sppq() function above. - M. F. Hasler, Nov 26 2018

Definition corrected by Max Alekseyev, Nov 12 2010

Terms corrected by Joerg Arndt, Dec 27 2010

A194946 Odd non-Carmichael numbers with increasing numbers of bases to which they are pseudoprimes.

Original entry on oeis.org

9, 15, 45, 65, 91, 231, 325, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8321, 11041, 12403, 18721, 30889, 38503, 49141, 68101, 79003, 88561, 88831, 104653, 137149, 146611, 176149, 188191, 218791, 226801, 269011, 286903, 385003, 493697, 497503, 563473

Offset: 1

Charles R Greathouse IV, Sep 13 2011

nonn

A141768 is the analog using the Rabin-Miller test rather than the Fermat test. The infinitude of that sequence implies that this sequence is likewise infinite.

Charles R Greathouse IV, Table of n, a(n) for n = 1..659
Index entries for sequences related to pseudoprimes

Cf. A195327 (number of bases).

Cf. A141768.

bases(n)=my(f=factor(n)[,1]);n--;prod(i=1,#f,gcd(f[i]-1,n))
Korselt(n)=my(f=factor(n));for(i=1,#f[,1],if(f[i,2]>1||(n-1)%(f[i,1]-1),return(0)));1
r=0;p=5;forprime(q=7,1e7,forstep(n=p+2,q-2,2,if(bases(n)>r&&!Korselt(n), r=bases(n);print1(n", ")));p=q) \\ Charles R Greathouse IV, Sep 14 2011

A090659 Odd composites with increasing proportion of nontrivial non-witnesses of compositeness by the Miller-Rabin primality test.

Original entry on oeis.org

25, 91, 703, 1891, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1056331, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 6186403, 6969511, 8086231, 9080191

Offset: 1

Ken Takusagawa, Dec 14 2003

nonn

Rabin has shown that the proportion has an upper bound of 0.25. If the trivial non-witnesses are counted, this upper bound is reached at 9. If the conjecture is true that the later terms are always the product of two primes p and (2*p-1), then the sequence continues 188191 218791 269011 286903 385003 497503 597871 736291 765703 954271 1056331 1314631 1869211 2741311 3270403 3913003 4255903 4686391 5292631.
Dickson's conjecture implies that this sequence is infinite. Can this be proved unconditionally? - Charles R Greathouse IV, Mar 10 2011
Higgins' conjecture 2 is implied by his conjecture 1, which is true by the general form of the number of non-witnesses of an odd number. - Charles R Greathouse IV, Mar 10 2011

			25 has 2 nontrivial non-witnesses (NTNW), namely (7,18), for a proportion of 2/22=0.0909. The denominator is 22 because the non-witnesses are selected from 2..23 (as 1 and 24 are trivial non-witnesses).
49 has 4 NTNW, namely (18,19,30,31) for a proportion of 4/46=0.0870. This is a smaller proportion than 0.0909 for 25.
91=7*13 has 16 NTNW in the range [2..89], namely [9, 10, 12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79, 81, 82], for a proportion of 16/88=0.182. It also has two trivial non-witnesses 1 and 90, which are not counted. The next integer with a higher proportion is 703, with 160 nontrivial non-witnesses and proportion 0.229.

Charles R Greathouse IV, Table of n, a(n) for n = 1..5411
Brian C. Higgins, The Rabin-Miller Primality Test: Some Results on the Number of Non-witnesses to Compositeness, ALLEMO Spring 1996 Meeting at IUP, Proceedings Volume 1.
S. Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test, MIT PRIMES-USA, 2015.
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128-138.

Subsequence of A141768.

Extended and edited by Charles R Greathouse IV, Mar 09 2011

A254139 a(n) = smallest composite c for which there exist exactly n bases b with b < c such that b^(c-1) == 1 (mod c), i.e., smallest composite c which is a Fermat pseudoprime to exactly n bases less than c.

Original entry on oeis.org

9, 28, 15, 66, 49, 232, 45, 190, 121, 276, 169, 1106

Offset: 1

Felix Fröhlich, Jan 26 2015

a(13) > 150000.

			With c = 49: there are exactly five bases b with b < 49 such that 49 is a Fermat pseudoprime, namely 18, 19, 30, 31 and 48. Since 49 is the smallest composite having exactly five such bases, a(5) = 49.

Cf. A001567, A141768, A181780.

for(n=1, 20, forcomposite(c=3, , b=2; i=0; while(b < c, if(Mod(b, c)^(c-1)==1, i++); b++); if(i==n, print1(c, ", "); break({1}))))

A329759 Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).

Original entry on oeis.org

15, 91, 703, 1891, 8911, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 5481451, 6186403, 6969511

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Odd numbers k such that A071294((k-1)/2) = A000010(k)/4.
For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.
The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.

			15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.

Amiram Eldar, Table of n, a(n) for n = 1..350
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.

Cf. A000010, A033181, A006945, A014233, A071294, A141768, A181782, A195328, A329468.

Cf. A001262, A020229, A020231, A020233.

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))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]

cp's OEIS Frontend

A195328 Number of bases to which terms of A141768 are strong pseudoprimes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A129521 Numbers of the form p*q, p and q prime with q=2*p-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

A083876 Least pseudoprime to base 2 through base prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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

A181782 Odd composite numbers n that are strong pseudoprimes to some base a, 2 <= a <= n-2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Extensions

A194946 Odd non-Carmichael numbers with increasing numbers of bases to which they are pseudoprimes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A090659 Odd composites with increasing proportion of nontrivial non-witnesses of compositeness by the Miller-Rabin primality test.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A254139 a(n) = smallest composite c for which there exist exactly n bases b with b < c such that b^(c-1) == 1 (mod c), i.e., smallest composite c which is a Fermat pseudoprime to exactly n bases less than c.

Views

Author

Keywords

Comments

Examples

A129521 Numbers of the form pq, p and q prime with q=2p-1.