Constant de Porter

En matemàtiques, la constant de Porter C apareix en l'estudi de l'eficiència de l'algorisme d'Euclides.^[1][2] Duu el nom de J. W. Porter de la Universitat de Cardiff.

L'algorisme d'Euclides troba el màxim comú divisor de dos enters positius m i n. Hans Heilbronn va demostrar que la mitjana del nombre d'iteracions de l'algotisme d'Euclides, fixat el valor de m i promitjat en tots els seus enters coprimers n, és

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

Porter va demostrar que el terme error en aquesta estimació és una constant, més una correcció polinomial petita, i Donald Knuth va avaluar aquesta constant amb molta precisió. El seu valor és:

${\displaystyle C={{6\ln 2} \over {\pi ^{2}}}\left[3\ln 2+4\gamma -{{24} \over {\pi ^{2}}}\zeta '(2)-2\right]-{{1} \over {2}}={{{6\ln 2}((48\ln A)-(\ln 2)-(4\ln \pi )-2)} \over {\pi ^{2}}}-{{1} \over {2}}=1.4670780794\ldots }$

on

${\displaystyle \gamma }$ és la constant d'Euler-Mascheroni

${\displaystyle \zeta }$ és la funció zeta de Riemann

${\displaystyle A}$ és la constant de Glaisher-Kinkelin

(successió A086237 a l'OEIS)

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

${\displaystyle }$

Referències