Porter's constant
From Wikipedia, the free encyclopedia
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
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:
where
- is the Euler–Mascheroni constant
- is the Riemann zeta function
- is the Glaisher–Kinkelin constant
(sequence A086237 in the OEIS)
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.