A055551 Number of base-2 Euler-Jacobi pseudoprimes (A047713) less than 10^n.

0, 0, 1, 12, 36, 114, 375, 1071, 2939, 7706, 20417, 53332, 139597, 364217, 957111, 2526795, 6725234, 18069359, 48961462

Offset: 1

Author

Eric W. Weisstein

Keywords

• nonn
• more

Comments

Pomerance et al. gave the terms a(3)-a(10). Pinch gave the terms a(4)-a(13), but a(13)=124882 was wrong. He later calculated the correct value, which appears in Guy's book. - Amiram Eldar, Nov 08 2019

Examples

			Below 10^3 there is only one Euler-Jacobi pseudoprime, 561. Therefore a(3) = 1.
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, section A12, p. 44.
• Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 219.

Links

• Jan Feitsma and William F. Galway, Tables of pseudoprimes and related data.
• Richard G.E. Pinch, The pseudoprimes up to 10^13, Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2-7, 2000, Proceedings, Springer, Berlin, Heidelberg, 2000, pp. 459-473, alternative link.
• Carl Pomerance, John L. Selfridge, and Samuel S. Wagstaff, The pseudoprimes to 25*10^9, Mathematics of Computation, Vol. 35, No. 151 (1980), pp. 1003-1026.
• Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
• Eric Weisstein's World of Mathematics, Pseudoprime.

Crossrefs

Cf. A047713, A055550, A055552.

Programs

Mathematica

ejpspQ[n_] := CompositeQ[n] && PowerMod[2, (n - 1)/2, n] == Mod[JacobiSymbol[2, n], n]; s = {}; c = 0; p = 10; n = 1; Do[If[ejpspQ[n], c++]; If[n > p, AppendTo[s, c]; p *= 10], {n, 1, 1000001, 2}]; s (* Amiram Eldar, Nov 08 2019 *)

Extensions

a(13) corrected and a(14)-a(19) added by Amiram Eldar, Nov 08 2019 (calculated from Feitsma & Galway's tables)