Porter's constant

In mathematics, Porter's constant C arises in the study of the efficiency of the Euclidean algorithm.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, Porter's constant C arises in the study of the efficiency of the Euclidean algorithm. It is named after J. W. Porter of University College, Cardiff. Euclid's algorithm finds the greatest common divisor of two positive integers and .

Hans Heilbronn proved that the average number of iterations of Euclid's algorithm, for fixed and averaged over all choices of relatively prime integers , is : \frac{12\ln 2}{\pi^2}\ln n+o(\ln n). 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: : \begin{align} C & = {{6 \ln2}\over{\pi^2}} \left[ 3 \ln 2 +4 \gamma - {{24}\over{\pi^2}}\zeta'(2)-2\right] -{{1}\over{2}} \\[6pt] & = {{{6 \ln2}((48 \ln A )- (\ln 2 )-(4 \ln \pi) -2)}\over{\pi^2}} - {{1}\over{2}} \\[6pt] & = 1.46707 80794 \ldots \end{align} where : \gamma is the Euler–Mascheroni constant : \zeta is the Riemann zeta function : A is the Glaisher–Kinkelin constant : -\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}} :

In mathematics, Porter's constant C arises in the study of the efficiency of the Euclidean algorithm. It is named after J. W. Porter of University College, Cardiff. Euclid's algorithm finds the greatest common divisor of two positive integers and .

Hans Heilbronn proved that the average number of iterations of Euclid's algorithm, for fixed and averaged over all choices of relatively prime integers , is \frac{12\ln 2}{\pi^2}\ln n+o(\ln n). 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: \begin{align} C & = {{6 \ln2}\over{\pi^2}} \left[ 3 \ln 2 +4 \gamma - {{24}\over{\pi^2}}\zeta'(2)-2\right] -{{1}\over{2}} \\[6pt] & = {{{6 \ln2}((48 \ln A )- (\ln 2 )-(4 \ln \pi) -2)}\over{\pi^2}} - {{1}\over{2}} \\[6pt] & = 1.46707 80794 \ldots \end{align} where \gamma is the Euler–Mascheroni constant \zeta is the Riemann zeta function A is the Glaisher–Kinkelin constant -\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}}

Approximations

The simple approximations of the Porter's constant accurate up to 3 digits can be found as C=2^{21/38}=1.466758730139474... , accurate up to 4 digits as C=2^{26/47}=1.467328090156686... , and up to 6 digits as C=2^{47/85}=1.467073525425601 ... .

See also

Lochs' theorem Lévy's constant

Text derived from https://en.wikipedia.org/w/index.php?oldid=1330155771 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.