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 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

12 ln ⁡ 2 π 2 ln ⁡ n + o ( ln ⁡ n ) . {\displaystyle {\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:

C = 6 ln ⁡ 2 π 2 [ 3 ln ⁡ 2 + 4 γ − 24 π 2 ζ ′ ( 2 ) − 2 ] − 1 2 = 6 ln ⁡ 2 ( ( 48 ln ⁡ A ) − ( ln ⁡ 2 ) − ( 4 ln ⁡ π ) − 2 ) π 2 − 1 2 = 1.4670780794 … {\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}}}

where

γ {\displaystyle \gamma } is the Euler–Mascheroni constant

ζ {\displaystyle \zeta } is the Riemann zeta function

A {\displaystyle A} is the Glaisher–Kinkelin constant

(sequence A086237 in the OEIS)

− ζ ′ ( 2 ) = π 2 6 [ 12 ln ⁡ A − γ − ln ⁡ ( 2 π ) ] = ∑ k = 2 ∞ ln ⁡ k k 2 {\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}}}}

{\displaystyle }

Approximations

The simple approximations of the Porter's constant accurate up to 3 digits can be found as

C = 2 21 / 38 = 1.466758730139474... , {\displaystyle C=2^{21/38}=1.466758730139474...,}

accurate up to 4 digits as

C = 2 26 / 47 = 1.467328090156686... , {\displaystyle C=2^{26/47}=1.467328090156686...,}

and up to 6 digits as

C = 2 47 / 85 = 1.467073525425601.... {\displaystyle C=2^{47/85}=1.467073525425601....}

See also