Algoritmo de Meissel-Lehmer - Meissel–Lehmer algorithm

O algoritmo Meissel-Lehmer (em homenagem a Ernst Meissel e Derrick Henry Lehmer ) é um algoritmo que calcula a função de contagem de primos .

Descrição

A identidade chave

Dado , pode-se definir as seguintes funções: Em primeiro 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 função mede o conjunto ( intervalo fechado ) quando alguém peneirou múltiplos dos primeiros primos ( incluindo estes próprios primos); ou seja, é a sequência de números primos em ordem crescente. ${\ 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 dividir isso ainda mais com as funções

${\ 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 {tem exatamente}} k {\ text {fatores primos}} \} \ right |,}$

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

estes medem o conjunto, mas consideram apenas os números que têm exatamente fatores primos (isso é bem definido pelo teorema fundamental da aritmética ). Com estes, temos ${\ 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);}$

a soma à direita é finita, pois os números têm, por exemplo, fatores primos. ${\ displaystyle \ leq x}$${\ displaystyle \ leq \ lfloor x \ rfloor}$

As 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)}$

provar que se pode calcular pela computação e , . E é isso que o algoritmo Meissel-Lehmer faz. ${\ displaystyle \ pi (x)}$${\ displaystyle \ varphi (x, a)}$${\ displaystyle P_ {k} (x, a)}$${\ displaystyle k \ geq 2}$

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

Para , obtemos a seguinte fórmula para : ${\ displaystyle k = 2}$${\ displaystyle P_ {k} (x, a)}$

${\ displaystyle {\ begin {alinhados} 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 {alinhado}}}$

Pois , há uma expansão semelhante. ${\ displaystyle k = 3}$

Expandindo 𝜑 ( x , a )

Usando a fórmula

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

${\ displaystyle \ varphi (x, a)}$ pode ser expandido. Cada soma, por sua vez, pode ser expandida da mesma maneira, de modo que surge uma soma alternada muito grande.

Combinando os termos

Resta avaliar e para certos valores de e . Isso pode ser feito por peneiramento direto e usando as fórmulas acima. ${\ displaystyle \ varphi (x, a)}$${\ displaystyle P_ {k} (x, a), k = 1,2, \ ldots}$${\ displaystyle x}$${\ displaystyle a}$

Uma variante moderna

Jeffrey Lagarias , Victor Miller e Andrew Odlyzko publicaram uma realização desse algoritmo que calcula no tempo e no espaço para qualquer um . Após a configuração , a árvore de tem nós de folha. ${\ 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})}$

Referências