Algoritmo de Meissel-Lehmer - Meissel–Lehmer algorithm

El algoritmo de Meissel-Lehmer (según Ernst Meissel y Derrick Henry Lehmer ) es un algoritmo que calcula la función de conteo de primos .

Descripción

La identidad clave

Dado , se pueden definir las siguientes funciones: En primer lugar, ${\ Displaystyle a \ in \ mathbb {N}}$

${\ Displaystyle \ varphi (x, a): = \ left | \ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ {a} p_ {j } \ mathbb {Z} \ right |;}$

esta función mide el conjunto ( intervalo cerrado ) cuando uno ha tamizado múltiplos de los primeros primos ( incluidos estos mismos primos); es decir, es la secuencia de números primos en orden creciente. ${\ Displaystyle [1, x] \ cap \ mathbb {N}}$${\ Displaystyle a}$${\ Displaystyle p_ {1}, \ ldots, p_ {a}}$${\ Displaystyle p_ {1}, p_ {2}, p_ {3}, \ ldots = 2,3,5, \ ldots}$

Podemos dividirlo aún más con las funciones

${\ Displaystyle P_ {k} (x, a): = \ left | \ left [\ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ { a} p_ {j} \ mathbb {Z} \ right] \ cap \ {n \ mid n {\ text {tiene exactamente}} k {\ text {factores primos}} \} \ right |,}$

${\ Displaystyle k \ in \ mathbb {N} _ {0};}$

estos miden el conjunto pero consideran solo los números que tienen exactamente factores primos (esto está bien definido por el teorema fundamental de la aritmética ). Con estos, tenemos ${\ Displaystyle \ left ([1, x] \ cap \ mathbb {N} \ right) \ setminus \ bigcup _ {j = 1} ^ {a} p_ {j} \ mathbb {Z}}$${\ Displaystyle k}$

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

la suma de la derecha es finita, ya que los números tienen, por ejemplo, factores primos. ${\ Displaystyle \ leq x}$${\ Displaystyle \ leq \ lfloor x \ rfloor}$

Las identidades

${\ Displaystyle \ pi (x) = P_ {1} (x, a) + a = a + \ varphi (x, a) -1- \ sum _ {k = 2} ^ {\ infty} P_ {k} ( x, a) \ qquad {\ text {(nota}} P_ {0} (x, a) = 1)}$

demostrar que uno puede calcular mediante el cálculo y , . Y esto es lo que hace el algoritmo de Meissel-Lehmer. ${\ Displaystyle \ pi (x)}$${\ Displaystyle \ varphi (x, a)}$${\ Displaystyle P_ {k} (x, a)}$${\ Displaystyle k \ geq 2}$

Fórmulas para la P _k ( x , a )

Para , obtenemos la siguiente fórmula para : ${\ Displaystyle k = 2}$${\ Displaystyle P_ {k} (x, a)}$

${\ Displaystyle {\ begin {alineado} P_ {2} (x, a) & = \ left | \ left \ {n \ mid n \ leq x, n = p_ {b} p_ {c}, a <b \ leq c \ right \} \ right | \\ & = \ sum _ {b = a + 1} ^ {\ pi (x ^ {1/2})} \ left | \ left \ {n ~ {\ big | } ~ n = p_ {b} p_ {c}, 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) \\ & = \ sum _ {b = a + 1} ^ {\ pi (x ^ {1/2})} \ pi \ left ({\ frac {x} {p_ { b}}} \ right) + {\ binom {a} {2}} - {\ binom {\ pi (x ^ {1/2})} {2}}. \ end {alineado}}}$

Porque hay una expansión similar. ${\ Displaystyle k = 3}$

Expandiendo 𝜑 ( x , a )

Usando la fórmula

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

${\ Displaystyle \ varphi (x, a)}$ puede ampliarse. Cada sumando, a su vez, puede expandirse de la misma manera, de modo que surja una suma alterna muy grande.

Combinando los términos

Lo único que queda por hacer es evaluar y para ciertos valores de y . Esto se puede hacer tamizando directamente y usando las fórmulas anteriores. ${\ Displaystyle \ varphi (x, a)}$${\ Displaystyle P_ {k} (x, a), k = 1,2, \ ldots}$${\ Displaystyle x}$${\ Displaystyle a}$

Una variante moderna

Jeffrey Lagarias , Victor Miller y Andrew Odlyzko publicaron una realización de este algoritmo que calcula en tiempo y espacio para cualquiera . Al establecerse , el árbol de tiene nodos de hojas. ${\ Displaystyle \ pi (x)}$${\ Displaystyle O (x ^ {2/3 + \ varepsilon})}$${\ Displaystyle O (x ^ {1/3 + \ varepsilon})}$${\ Displaystyle \ varepsilon> 0}$${\ Displaystyle a = \ pi (x ^ {1/3})}$${\ Displaystyle \ varphi (x, a)}$${\ Displaystyle O (x ^ {2/3})}$

Referencias