Constante de Porter

En mathématiques, la constante de Porter C (suite A086237 de l'OEIS) apparaît dans l'étude de l'efficacité de l'algorithme d'Euclide. Elle porte le nom de J. W. Porter de l'Université de Cardiff.

L'algorithme d'Euclide trouve le plus grand diviseur commun de deux entiers positifs m et n. Hans Heilbronn a prouvé que le nombre moyen d'itérations de l'algorithme d'Euclide, pour n fixe et moyenné sur tous les choix d'entiers relativement premiers m < n, est

${\frac {12\ln 2}{\pi ^{2}}}\ln n+o(\ln n).$

Porter a démontrer que le terme d'erreur dans cette estimation est constant, et Donald Knuth a donné son expression exacte :

${\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}}$

où

$\gamma$ est la constante d'Euler–Mascheroni,

$\zeta$ est la fonction zêta de Riemann,

$A$ est la constante de Glaisher–Kinkelin,

$-\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}}}$

Articles connexes

• Théorème de Lochs
• Constante de Lévy

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Porter's constant » (voir la liste des auteurs).