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^[1],[2]. 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

${\displaystyle {\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 :

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

où

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

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

${\displaystyle A}$ est la constante de Glaisher–Kinkelin, et

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

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

• Portail des mathématiques