TOPICS
Search

Hafner-Sarnak-McCurley Constant

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Given two randomly chosen n×n integer matrices, what is the probability D(n) that the corresponding determinants are relatively prime? Hafner et al. (1993) showed that

D(n)=product_(k=1)^infty{1-[1-product_(j=1)^n(1-p_k^(-j))]^2},
(1)

where p_n is the nth prime.

HafnerSarnakMcCurley

The case D(1) is just the probability that two random integers are relatively prime,

D(1)=6/(pi^2)=0.6079271019...
(2)

(OEIS A059956). No analytic results are known for n>=2. Approximate values for the first few n are given by

D(2) approx 0.453103
(3)
D(3) approx 0.397276
(4)
D(4) approx 0.373913
(5)
D(5) approx 0.363321.
(6)

Vardi (1991) computed the limit

sigma=lim_(n->infty)D(n)=0.3532363719...
(7)

(A085849). The speed of convergence is roughly ∼0.57^n (Flajolet and Vardi 1996).

See also

Integer Matrix, Relatively Prime

Explore with Wolfram|Alpha

References

Finch, S. R. "Hafner-Sarnak-McCurley Constant." §2.5 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 110-112, 2003.Flajolet, P. and Vardi, I. "Zeta Function Expansions of Classical Constants." Unpublished manuscript. 1996. http://algo.inria.fr/flajolet/Publications/landau.ps.Hafner, J. L.; Sarnak, P.; and McCurley, K. "Relatively Prime Values of Polynomials." In A Tribute to Emil Grosswald: Number Theory and Related Analysis (Ed. M. Knopp and M. Seingorn). Providence, RI: Amer. Math. Soc., 1993.Sloane, N. J. A. Sequences A059956 and A085849 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, 1991.

Referenced on Wolfram|Alpha

Hafner-Sarnak-McCurley Constant

Cite this as:

Weisstein, Eric W. "Hafner-Sarnak-McCurley Constant." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Hafner-Sarnak-McCurleyConstant.html

Subject classifications