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

%I #12 Nov 08 2019 18:17:43

%S 0,0,1,12,36,114,375,1071,2939,7706,20417,53332,139597,364217,957111,

%T 2526795,6725234,18069359,48961462

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

%C 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

%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, section A12, p. 44.

%H Jan Feitsma and William F. Galway, <a href="http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html">Tables of pseudoprimes and related data</a>.

%H Richard G.E. Pinch, <a href="https://doi.org/10.1007/10722028_30">The pseudoprimes up to 10^13</a>, Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2-7, 2000, Proceedings, Springer, Berlin, Heidelberg, 2000, pp. 459-473, <a href="https://www.researchgate.net/publication/239577634_Algorithmic_Number_Theory_4th_International_Symposium_ANTS-IV_Leiden_The_Netherlands_July_2-7_2000_Proceedings">alternative link</a>.

%H Carl Pomerance, John L. Selfridge, and Samuel S. Wagstaff, <a href="https://doi.org/10.1090/S0025-5718-1980-0572872-7">The pseudoprimes to 25*10^9</a>, Mathematics of Computation, Vol. 35, No. 151 (1980), pp. 1003-1026.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Euler-JacobiPseudoprime.html">Euler-Jacobi Pseudoprime.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudoprime.html">Pseudoprime.</a>

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

%t 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 *)

%Y Cf. A047713, A055550, A055552.

%K nonn,more

%O 1,4

%A _Eric W. Weisstein_

%E a(13) corrected and a(14)-a(19) added by _Amiram Eldar_, Nov 08 2019 (calculated from Feitsma & Galway's tables)