In mathematics, Porter's constant ''C'' arises in the study of the efficiency of the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
.
[.] 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
Hans Arnold Heilbronn (8 October 1908 – 28 April 1975) was a mathematician.
Education
He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervised ...
proved that the average number of iterations of Euclid's algorithm, for fixed and averaged over all choices of
relatively prime integers ,
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
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
:
is the
Glaisher–Kinkelin constant
:
:
See also
*
Lochs' theorem
In number theory, Lochs's theorem concerns the rate of convergence of the continued fraction expansion of a typical real number. A proof of the theorem was published in 1964 by Gustav Lochs.
The theorem states that for almost all real numbers in ...
*
Lévy's constant In mathematics Lévy's constant (sometimes known as the Khinchin–Lévy constant) occurs in an expression for the asymptotic behaviour of the denominators of the convergents of continued fractions.
In 1935, the Soviet mathematician Aleksandr Khi ...
References
Mathematical constants
Analytic number theory
{{Numtheory-stub