Aller au contenu

Constante de Porter

Un article de Wikipédia, l'encyclopédie libre.

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

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

est la constante d'Euler–Mascheroni,
est la fonction zêta de Riemann,
est la constante de Glaisher–Kinkelin, et
.

Articles connexes

[modifier | modifier le code]

Références

[modifier | modifier le code]
  1. Donald E. Knuth, « Evaluation of Porter's constant », Computers & Mathematics with Applications, vol. 2, no 2,‎ , p. 137–139 (DOI 10.1016/0898-1221(76)90025-0 Accès libre)
  2. J. W. Porter, « On a theorem of Heilbronn », Mathematika, vol. 22, no 1,‎ , p. 20–28 (DOI 10.1112/S0025579300004459, MR 0498452).