Constante de Porter
Apparence
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 :
où
- 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]- (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).
- 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 )
- J. W. Porter, « On a theorem of Heilbronn », Mathematika, vol. 22, no 1, , p. 20–28 (DOI 10.1112/S0025579300004459, MR 0498452).