A071294 -id:A071294 - cp's OEIS frontend

A182291 Duplicate of A071294.

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

Offset: 1

R. J. Mathar, Jul 03 2012

dead

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

Original entry on oeis.org

9, 25, 49, 91, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8911, 12403, 18721, 29341, 31621, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311

Offset: 1

Charles R Greathouse IV, Sep 15 2008

These numbers are the worst cases for the Rabin-Miller probable-prime test.
Alford, Granville, & Pomerance show that this sequence is infinite.
The sequence is unchanged whether one, both, or neither of 1 and n-1 are included as bases.

			25 is a 1-, 7-, 18- and 24-strong pseudoprime and no odd number less than 25 has four or more bases to which it is a strong pseudoprime.

Charles R Greathouse IV, Table of n, a(n) for n = 1..5476
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.
Shyam Narayanan, Improving the Speed and Accuracy of the Miller-Rabin Primality Test
Shyam Narayanan, Improving the Accuracy of Primality Tests by Enhancing the Miller-Rabin Theorem (2014)
Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12:1 (1980), pp. 128-138.
Index entries for sequences related to pseudoprimes

Cf. A014233, A071294, A194946.

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])));
r=0;forstep(n=9,1e8,2,if(isprime(n),next);t=bases(n);if(t>r,r=t;print1(n",")))

Edited by Charles R Greathouse IV, Jul 23 2010

A060684 Smallest difference between consecutive divisors (ordered by size) of 2n+1.

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, 4, 2, 58, 60, 2, 4, 66, 2, 70, 72, 2, 4, 78, 2, 82, 4, 2, 88, 6, 2, 4, 96, 2, 100, 102, 2, 106, 108, 2, 112, 4, 2, 6, 10, 2, 4, 126, 2, 130, 6, 2, 136, 138, 2, 2, 4, 2, 148, 150, 2, 4, 156, 2, 6

Offset: 1

Labos Elemer, Apr 19 2001

nonn

Successively greater values of a(n) occur when 2n+1 is prime.

			For n=38, 2n+1=77; divisors={1,7,11,77}; differences={6,4,66}; a(38) = smallest difference = 4.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A060680.
Different from A071294.
Cf. A193829, A027750.

a060684 = minimum . a193829_row . (+ 1) . (* 2)
-- Reinhard Zumkeller, Jun 25 2015

a[n_ ] := Min@@(Drop[d=Divisors[2n+1], 1]-Drop[d, -1])
Array[Min[Differences[Divisors[2*#+1]]]&,80] (* Harvey P. Dale, Dec 08 2013 *)

A060680(2n+1)

Edited by Dean Hickerson, Jan 22 2002

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

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, 4, 46, 6, 2, 52, 2, 2, 58, 60, 2, 8, 66, 2, 70, 72, 2, 2, 78, 2, 82, 8, 2, 88, 18, 2, 2, 96, 2, 100, 102, 8, 106, 108, 2, 112, 2, 4, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 8, 2

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Number of bases b, 1 <= b <= 2*n, such that GCD(b, 2*n+1) = 1 and b^n == (b / 2*n+1) (mod 2*n+1), where (b / 2*n+1) is a Jacobi symbol.
If 2*n+1 is composite then it is the number of bases b, 1 <= b <= 2*n, in which 2*n+1 is an Euler-Jacobi pseudoprime.
Differs from A071294 from n = 22.

			a(1) = 2 since there are 2 bases b in which 2*1 + 1 = 3 is an Euler-Jacobi pseudoprime: b = 1 since GCD(1, 3) = 1 and 1^1 == (1 / 3) == 1 (mod 3), and b = 2 since GCD(2, 3) = 1 and 2^1 == (2 / 3) == -1 (mod 3).

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

Amiram Eldar, Table of n, a(n) for n = 1..10000
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Wikipedia, Euler-Jacobi pseudoprime.
Wikipedia, Solovay-Strassen primality test.

Cf. A006093, A007324, A007814, A047713, A063994, A071294.

v[n_] := Min[IntegerExponent[#, 2]& /@ (FactorInteger[n][[;;, 1]] - 1)];
pQ[n_, p_] := OddQ[IntegerExponent[n, p]] && IntegerExponent[p-1, 2] < IntegerExponent[n-1, 2];
psQ[n_] := AnyTrue[FactorInteger[n][[;;, 1]], pQ[n, #] &];
delta[n_] := If[IntegerExponent[n-1, 2] == v[n], 2, If[psQ[n], 1/2, 1]];
a[n_] := delta[n] * Module[{p = FactorInteger[n][[;;, 1]]}, Product[GCD[(n-1)/2, p[[k]]-1], {k, 1, Length[p]}]];
Table[a[n], {n, 3, 147, 2}]

a(n) = delta(n) * Product_{p|n} gcd((n-1)/2, p-1), where delta(n) = 2 if nu(n-1, 2) = min_{p|n} nu(p-1, 2), 1/2 if there is a prime p|n such that nu(p, n) is odd and nu(p-1, 2) < nu(n-1, 2), and 1 otherwise, where nu(n, p) is the exponent of the highest power of p dividing n.

a(p) = p-1 for prime p.

A329468 Carmichael numbers all of whose prime factors are congruent to 3 modulo 4.

Original entry on oeis.org

8911, 1024651, 1152271, 1773289, 5481451, 8830801, 9585541, 10267951, 14913991, 15888313, 26474581, 40917241, 45877861, 64377991, 67902031, 72108421, 72286501, 81926461, 94536001, 104852881, 111291181, 129762001, 139592101, 139952671, 178482151, 213835861, 368113411

Offset: 1

Amiram Eldar, Nov 13 2019

nonn

Galbraith et al. (2019) proved that for a Carmichael number m, the number of bases below m in which m is a strong pseudoprime is S(m) = A071294((m-1)/2) <= phi(m)/2^(omega(m)-1), with equality when m is a term of this sequence, where phi is the Euler totient function (A000010) and omega(m) is the number of distinct prime factors of m (A001221).
The corresponding values of S(a(n)) are 1782, 240570, 277830, 176418, 1316250, 882090, 984150, 2515590, 3611790, 1587762, ...
The least term with 3, 4, 5, ... prime factors is 8911, 1773289, 1419339691, 4077957961, 3475350807391, 440515336876021, 574539328092938671, 2426698123549677901, ...

			8911 = 7 * 19 * 67 is a term since it is a Carmichael number, and 7 == 19 == 67 == 3 (mod 4).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Steven Galbraith, Jake Massimo and Kenneth G. Paterson, Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation, in: Dongdai Lin and Kazue Sako (eds.), Public-Key Cryptography - PKC 2019, 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II, Springer, 2019.

Cf. A000010, A001221, A002997, A071294.

Supersequence of A185321.

aQ[n_] := CompositeQ[n] && Divisible[n - 1, CarmichaelLambda[n]] && AllTrue[ FactorInteger[n][[;;,1]], Mod[#, 4] == 3 &]; Select[Range[2*10^6], aQ]

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

A182291 Duplicate of A071294.

Views

Author

Keywords

A141768 Odd numbers with increasing numbers of bases to which they are strong pseudoprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A060684 Smallest difference between consecutive divisors (ordered by size) of 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A329468 Carmichael numbers all of whose prime factors are congruent to 3 modulo 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica