In mathematics, Porter's constant C arises in the study of the efficiency of the Euclidean algorithm.[1][2] It is named after J. W. Porter of University College, Cardiff.
Euclid's algorithm finds the greatest common divisor of two positive integers m and n. Hans Heilbronn proved that the average number of iterations of Euclid's algorithm, for fixed n and averaged over all choices of relatively prime integers m < n, is
![{\displaystyle {\frac {12\ln 2}{\pi ^{2}}}\ln n+o(\ln n).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f031b743ba40bbab3ef821512d9282b689749a2f)
Porter showed that the error term in this estimate is a constant, plus a polynomially-small correction, and Donald Knuth evaluated this constant to high accuracy. It is:
![{\displaystyle {\begin{aligned}C&={{6\ln 2} \over {\pi ^{2}}}\left[3\ln 2+4\gamma -{{24} \over {\pi ^{2}}}\zeta '(2)-2\right]-{{1} \over {2}}\\[6pt]&={{{6\ln 2}((48\ln A)-(\ln 2)-(4\ln \pi )-2)} \over {\pi ^{2}}}-{{1} \over {2}}\\[6pt]&=1.4670780794\ldots \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c74b6e5ed4af0f47171ae91204a311eeb35f1134)
where
is the Euler–Mascheroni constant
is the Riemann zeta function
is the Glaisher–Kinkelin constant
(sequence A086237 in the OEIS)
![{\displaystyle -\zeta ^{\prime }(2)={{\pi ^{2}} \over 6}\left[12\ln A-\gamma -\ln(2\pi )\right]=\sum _{k=2}^{\infty }{{\ln k} \over {k^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1754181b8dc988a345bb47581b278ce8b7613466)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
See also
References
- ^ Knuth, Donald E. (1976), "Evaluation of Porter's constant", Computers & Mathematics with Applications, 2 (2): 137–139, doi:10.1016/0898-1221(76)90025-0
- ^ Porter, J. W. (1975), "On a theorem of Heilbronn", Mathematika, 22 (1): 20–28, doi:10.1112/S0025579300004459, MR 0498452.