Porter's constant explained

In mathematics, Porter's constant C arises in the study of the efficiency of the Euclidean algorithm.^[1] 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

(12ln2)/(\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 }} \\[ 6 pt] & = {{{ 6 ln2 }(( 48 ln A ) - ( ln 2 ) - ( 4 ln \pi) -2 )}\over{\pi ^{2}}} - {{ 1 }\over{ 2 }} \\[ 6 pt] & = 1 . 46707 80794 \ldots \end{align} where\gamma is the Euler–Mascheroni constant- \zeta ^{\prime} ( 2 ) = {{\pi ^{2}} \over 6 } \left[ 12 ln A - \gamma -ln ( 2 \pi)\right] = \sum ^{inf ty} _{k =2} {{ ln k}\over{k ^{2}}}

See also

• Lochs' theorem
• Lévy's constant

Notes and References

1. .