Constant de Porter

En matemàtiques, la constant de Porter C apareix en l'estudi de l'eficiència de l'algorisme d'Euclides. 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

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

$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$

on

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

$\zeta$ és la funció zeta de Riemann

$A$ és la constant de Glaisher-Kinkelin

$-{\zeta }^{\prime }(2)=\frac{{\pi }^2}{6}[12\ln A-\gamma -\ln (2\pi )]=\sum _{k=2}^{\mathrm{\infty }}\frac{\ln k}{k^2}$

${\displaystyle }$