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 permet d'obtenir le plus grand diviseur commun de deux entiers strictement positifs m et n. Hans Heilbronn a prouvé que le nombre moyen d'itérations dans l'algorithme d'Euclide, pour n fixé et moyenné sur tous les choix d'un entier m < n premier avec n, est

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

Porter a démontré 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, et

$-\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).