Porter's constant

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 alsoEdit

ReferencesEdit

  1. ^ 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
  2. ^ Porter, J. W. (1975), "On a theorem of Heilbronn", Mathematika, 22 (1): 20–28, doi:10.1112/S0025579300004459, MR 0498452.