Constante de Porter

En mathématiques, la constante de Porter Modèle:Mvar (Modèle:OEIS) apparaît dans l'étude de l'efficacité de l'algorithme d'EuclideModèle:,. 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 Modèle:Mvar et Modèle:Mvar. Hans Heilbronn a prouvé que le nombre moyen d'itérations dans l'algorithme d'Euclide, pour Modèle:Mvar fixé et moyenné sur tous les choix d'un entier Modèle:Formule [[Nombres premiers entre eux|premier avec Modèle:Mvar]], 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{array}{cc}C& =\frac{6\ln 2}{{\pi }^2}[3\ln 2+4\gamma -\frac{24}{{\pi }^2}{\zeta }^{\prime }(2)-2]-\frac{1}{2}\\ & =\frac{6\ln 2((48\ln A)-(\ln 2)-(4\ln \pi )-2)}{{\pi }^2}-\frac{1}{2}\\ & =1,4670780794\dots \end{array}$

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)=\frac{{\pi }^2}{6}[12\ln A-\gamma -\ln (2\pi )]=\sum _{k=2}^{\mathrm{\infty }}\frac{\ln k}{k^2}$.

Articles connexes

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