Algoritmo de Meissel-Lehmer

El algoritmo de Meissel-Lehmer (después de Ernst Meissel y Derrick Henry Lehmer ) es un algoritmo que calcula valores exactos de la función de conteo de primos . ^{[ 1 ]}^{[ 2 ]}

Descripción

El problema de contar el número exacto de primos menores o iguales a x , sin enumerarlos todos, se remonta a Legendre . Observó en la Criba de Eratóstenes que

\pi (x)-\pi (x^{1/2})+1=\lfloor x\rfloor -\sum _{i}\lfloor x/p_{i}\rfloor +\sum _{i<j}\lfloor x/p_{i}p_{j}\rfloor -\ldots

donde $⌊ x ⌋$ es la función piso , que denota el mayor entero menor o igual a $x$ y el $p i$ recorre todos los primos $\leq \sqrt x$ . ^{[ 1 ]}^{[ 2 ]}

Dado que la evaluación de esta fórmula de suma se vuelve cada vez más compleja y confusa para valores grandes de $x$ , Meissel intentó simplificar el conteo de los números en la Criba de Eratóstenes. Por lo tanto, él y Lehmer introdujeron ciertas funciones de criba, que se detallan a continuación.

Funciones clave

Sean $p 1, p 2, \dots, p n$ los primeros $n$ números primos. Para un número natural $a \geq 1$ , definimos

\varphi (x,a):=\left|\left\{n\leq x:p|n\implies p>p_{a}\right\}\right|,

que cuenta los números naturales no mayores que $x$ con todos los factores primos mayores que $p a$ . También defina para un número natural $k$ ,

P_{k}(x,a):=\left|\left\{n\leq x:n=q_{1}q_{2}\cdots q_{k},~{\text{con}}~q_{1},\ldots ,q_{k}>p_{a}\right\}\right|,

que cuenta los números naturales no mayores que $x$ con exactamente $k$ factores primos, todos mayores que $p a$ . Con estos, tenemos

\varphi (x,a)=\sum _{k=0}^{\infty }P_{k}(x,a),

donde la suma solo tiene un número finito de términos distintos de cero porque $P k (x, a) = 0$ cuando $p k a > x$ . Usando el hecho de que $P 0 (x, a) = 1$ y $P 1 (x, a) = π (x) - a$ , obtenemos

\pi (x)=\varphi (x,a)+a-1-\sum _{k=2}^{\infty }P_{k}(x,a),

lo cual prueba que se puede calcular $π (x)$ calculando $φ (x, a)$ y $P k (x, a)$ para $k \geq 2$ . Esto es lo que hace el algoritmo de Meissel-Lehmer.

Fórmula para P _k ( x , a )

Para $k = 2$ , obtenemos la siguiente fórmula para $P k (x, a)$ :

{\begin{aligned}P_{2}(x,a)&=\left|\left\{n:n\leq x,~n=p_{b}p_{c},~{\text{con}}~a<b\leq c\right\}\right|\\&=\sum _{b=a+1}^{\pi (x^{1/2})}\left|\left\{n:n\leq x,~n=p_{b}p_{c},~{\text{con}}~b\leq c\leq \pi \left({\frac {x}{p_{b}}}\right)\right\}\right|\\&=\sum _{b=a+1}^{\pi (x^{1/2})}\left(\pi \left({\frac {x}{p_{b}}}\right)-(b-1)\right)\\&={\binom {a}{2}}-{\binom {\pi (x^{1/2})}{2}}+\sum _{b=a+1}^{\pi (x^{1/2})}\pi \left({\frac {x}{p_{b}}}\right).\end{aligned}}

Para $k \geq 3$ , las identidades para $P k (x, a)$ se pueden derivar de manera similar. ^{[ 1 ]}

Expandiendo $φ (x, a)$

Con la condición inicial

\varphi (x,0)=\lfloor x\rfloor ,

y la recurrencia

\varphi (x,a)=\varphi (x,a-1)-\varphi \left({\frac {x}{p_{a}}},a-1\right),

Cada valor de $φ (x, a)$ se puede calcular recursivamente.

Combinando los términos

Lo único que queda por hacer es evaluar $φ (x, a)$ y $P k (x, a)$ para $k \geq 2$ , para ciertos valores de $x$ y $a$ . Esto se puede hacer mediante tamizado directo y utilizando las fórmulas anteriores.

Historia

Meissel ya había descubierto que para $k \geq 3$ , $P k (x, a) = 0$ si $a = π (x 1/3)$ . Utilizó la ecuación resultante para calcular $π (x)$ para valores grandes de $x$ . ^{[ 1 ]}

Meissel calculó $π (x)$ para valores de $x$ de hasta $109$ , pero no acertó por poco con el resultado correcto para el valor más grande de $x$ . ^{[ 1 ]}

Utilizando su método y una IBM 701 , Lehmer pudo calcular el valor correcto de $π (10 9)$ y falló en el valor correcto de $π (10 10)$ por 1. ^{[ 1 ]}

Algoritmo extendido

Jeffrey Lagarias , Victor Miller y Andrew Odlyzko publicaron una realización del algoritmo que calcula $π (x)$ en tiempo $O (x² /³ + ε)$ y espacio $O (x¹ /³ + ε)$ para cualquier $ε > 0.$ [ ^{2 ] Al} establecer $a = π (x¹ /³)$ , el árbol de $φ (x, a)$ tiene $O (x² /³)$ nodos hoja. ^{[ 2 ]}

Este algoritmo extendido de Meissel-Lehmer necesita menos tiempo de cálculo que el algoritmo desarrollado por Meissel y Lehmer, especialmente para valores grandes de $x$ .

M. Deleglise y J. Rivat en 1996 y X. Gourdon en 2001 (inédito) presentaron mejoras adicionales del algoritmo. ^{[ 3 ]}^{[ 4 ]}

Referencias

1 2 3 4 5 6 Lehmer, Derrick Henry (1 de abril de 1958). "SOBRE EL NÚMERO EXACTO DE PRIMOS MENORES QUE UN LÍMITE DADO" . Illinois J. Math . 3 (3): 381– 388. Recuperado el 1 de febrero de 2017 .
1 2 3 4 Lagarias, Jeffrey; Miller, Victor; Odlyzko, Andrew (11 de abril de 1985). "Informática $\pi (x)$ : El método Meissel-Lehmer" (PDF) . Matemáticas de la Computación . 44 (170): 537– 560. doi : 10.1090/S0025-5718-1985-0777285-5 . Consultado el 13 de septiembre de 2016 .
↑ Deleglise, Marc; Rivat, Joël (15 de enero de 1996). "Computing $\pi (x)$ : El método Meissel, Lehmer, Lagarias, Miller, Odlyzko" . Matemáticas de la Computación . 65 (213): 235– 245. doi : 10.1090/S0025-5718-96-00674-6 .
↑ Oliveira e Silva, Tomas (1 de marzo de 2006). "Computación $\pi (x)$ : el método combinatorio" (PDF) . Revista do Detua . 4 (6): 759– 768. Recuperado el 14 de marzo de 2023 .

[lehmer-1] 1 2 3 4 5 6 Lehmer, Derrick Henry (1 de abril de 1958). "SOBRE EL NÚMERO EXACTO DE PRIMOS MENORES QUE UN LÍMITE DADO" . Illinois J. Math . 3 (3): 381– 388. Recuperado el 1 de febrero de 2017 .

[lagarias-miller-odlyzko-2] 1 2 3 4 Lagarias, Jeffrey; Miller, Victor; Odlyzko, Andrew (11 de abril de 1985). "Informática $\pi (x)$ : El método Meissel-Lehmer" (PDF) . Matemáticas de la Computación . 44 (170): 537– 560. doi : 10.1090/S0025-5718-1985-0777285-5 . Consultado el 13 de septiembre de 2016 .

[deleglise-3] Deleglise, Marc; Rivat, Joël (15 de enero de 1996). "Computing $\pi (x)$ : El método Meissel, Lehmer, Lagarias, Miller, Odlyzko" . Matemáticas de la Computación . 65 (213): 235– 245. doi : 10.1090/S0025-5718-96-00674-6 .

[Oliveira-4] Oliveira e Silva, Tomas (1 de marzo de 2006). "Computación $\pi (x)$ : el método combinatorio" (PDF) . Revista do Detua . 4 (6): 759– 768. Recuperado el 14 de marzo de 2023 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]