Algoritmo más rápido para Calcular la Suma de los números Primos?

Question

Alguien me puede ayudar con referencias a la corriente más rápida de algoritmos de cómputo de la suma exacta de los números primos menos que un número n? Estoy específicamente curiosidad sobre el mejor de los casos los tiempos de ejecución, por supuesto. Estoy bastante familiarizado con los distintos rápido algoritmos para el primer conteo, pero estoy teniendo un momento más difícil de rastrear suma de primer algoritmos...

Answer 1

Deléglise-Dusart-Roblot [1] dar un algoritmo que determina el $\pi(x,k,l)$, el número de números primos hasta el $x$ que son congruentes a $l$ modulo $k,$ en el tiempo $O(x^{2/3}/\log^2x).$ el Uso de este algoritmo para contar el número de números primos en todas las clases de residuos $k<2\log x$ toma $$1+\sum_{p<2\log x}(p-2)\sim\frac{2\log^2x}{\log\log x}$$ invocaciones de Deléglise-Dusart-Roblot, para un total de $O(x^{2/3}/\log\log x)$ del tiempo.

Esto le permite a uno para determinar el valor de $\sum_{p\le x}p$ mod todos los números primos hasta el $2\log x$ y, por lo tanto, por el Teorema de los números Primos y el Teorema del Resto Chino, el valor de la suma de mod $\exp(\vartheta(2\log x))=x^2(1+o(1)).$ Junto con límites en el valor de $\sum_{p\le x}p$ [2], esto permite el cálculo de la suma.

Tenga en cuenta que los números primos ligeramente más allá de la $2\log x$ puede ser necesaria dependiendo del valor de $\vartheta(2\log x).$ Prácticamente hablando, a excepción de $x$ pequeños, $2\log x+\log x/\log\log x$ es suficiente. Esto no cambia el asymptotics.

No sé si es posible modificar el Lagarias-Odlyzko fórmula analítica [3] a contar en el residuo de clases. Si es así, esto podría permitir a un $O(x^{1/2+o(1)})$ algoritmo.

Referencias

[1] Marc Deléglise, Pierre Dusart, y Xavier-François Roblot, el Conteo de los números primos en el residuo de clases, las Matemáticas de la Computación 73:247 (2004), pp 1565-1575. doi 10.1.1.100.779

[2] Nilotpal Kanti Sinha, En la asintótica de expansión de la suma de los n primeros números primos (2010).

[3] J. C. Lagarias y A. M. Odlyzko, Computing $\pi(x)$: Un método analítico, Diario de Algoritmos 8 (1987), pp 173-191.

Answer 2

Editar Nov 22: se ha Cambiado la condición de la función de prueba de $\Phi$ algo para simplificar mi argumento (retirado una suma en la identidad de abajo).

Aunque me gusta Charles respuesta y su aplicación del teorema del resto Chino, déjame darte una opinión diferente sobre el problema. Es posible utilizar un método analítico más directamente (similar a la Lagarias-Odlyzko método), usando sólo la de Riemann zeta función y no de la teoría de la Dirichlet L-funciones (o primos en aritmética de las secuencias). Este método se pueden tratar más bien arbitraria sumas $$ \sum_{ p < x } f(p) $$ for smooth functions $f$.

La idea es considerar la identidad $$\sum_{ p < x } f(p) =\sum_{p} f(p)\Phi \left( \frac {p-x} {\sqrt x} \right ) - \sum_{x< p < x + \sqrt x } f(p) \Phi \left(\frac {p-x} {\sqrt x} \right), $$ donde $\Phi(x)$ es suave a prueba de función tal que $\Phi(x)=1$ para $x<0$ e $\Phi(x)=0$ para $x>1$. Está claro que la última suma se puede calcular en $O( x^{1/2} )$ tiempo (digamos cribado de la de los números primos en el intervalo, y el cálculo explícito). Ahora la idea es utilizar el Mellin de transformación de la identidad $$ \sum_{p}f(p)\Phi \left( \frac {p-x} {\sqrt x} \right )= \frac 1 {2 \pi i} \int_{c-\infty i}^{c+\infty i} \sum_{p} p^{-s} \int_0^\infty \Phi \left(\frac{y-x}{\sqrt x} \right)f(y) y^{s-1} dyds. (c>1)$$ El punto aquí es que la Mellin transformar $\int_0^\infty \Phi(\frac{y-x}{\sqrt x})f(y) y^{s-1}dy$ es pequeño cuando se $|\Im(s)|>x^{1/2+\epsilon}$ e $\Re(s)=c$ cualquier $\epsilon>0$, por lo que parte de la integral puede ser desechado. El de la serie de Dirichlet $\sum_{p} p^{-s}$ puede ser expresada en términos del logaritmo de la función zeta de los argumentos $ks$ (suma de más de $k$). Ahora el Odlyzko-Schönhage algoritmo (Bastante agradable algoritmo, se utiliza la transformada rápida de fourier) nos permite calcular los valores de la Riemann zeta función para decir $s=c+it$ para $ |t| < x^{1/2+\epsilon}$ en $O(x^{1/2+\epsilon+o(1)})$ del tiempo. Tambien comentar que los Weil explícita la fórmula puede usarse en lugar de este complejo integral (entonces los ceros de la de Riemann zeta función debe calcular rápido, pero esto también puede ser hecho por el Odlyzko-Schönhage algoritmo). Esto significa que el tiempo total para calcular el $\sum_{ p < x } f(p)$ será $O(x^{1/2+\epsilon})$ cualquier $\epsilon>0$.

Tenga en cuenta que el mismo argumento se aplica cuando los números primos en progresión aritmética se refiere (ver mi comentario sobre Charles respuesta). Desde el Odlyzko-Schönhage algoritmo tiene también para el de Dirichlet L-funciones, este caso puede ser tratado de la misma manera.

Answer 3

Voy a poner en un enchufe para mi original en papel con Lagarias y Odlyzko, así como un reciente artículo de Bach, Klyve y Sorenson: http://www.ams.org/journals/mcom/2009-78-268/S0025-5718-09-02249-2/home.html Computación en primer armónico sumas de Matemáticas. Comp. 78 (2009), 2283-2305. Aunque los algoritmos de Lagarias y Odlyzko (con el algoritmo de Odlyzko-Schonhage para el cómputo de buenas aproximaciones a un montón de valores de $\zeta(s)$) son asintóticamente la mejor, teniendo la complejidad de la $O(x^{1/2 + \epsilon})$ la combinatoria de los algoritmos probablemente funcionará mejor para cualquiera de los rangos razonables. A pesar de que uno debe mirar J. Buethe, J. Franke, A. Jost, y T. Kleinjung, "Condicional Cálculo de pi(10^24)", la Publicación de la Teoría de los números de la Lista de Correo, Jul 29 2010. Un poco más de detalle (que es todo lo que tengo ahora mismo), está contenida en la charla de David Platt: www.maths.bris.ac.uk/~madjp/junior%20talk.pdf . La idea en la combinatoria método es el siguiente:

Supongamos que $f(n)$ es totalmente una función multiplicativa de los números enteros positivos. En el caso de cálculo de $\pi(x)$, tomamos $f(n) = 1$. En el caso de calcular la suma de los números primos $\le x$ tomamos $f(n) = n$. En el caso de Cálculo de $\pi(x,a,q)$ tomamos $f(n)$ a ser una de Dirichlet carácter mod $q$.

Definir $\phi(x,a)$ como la suma de $f(n)$ para todos los enteros $n \le x$ que son no divisible por el primer $a$ números primos. Claramente $\phi(x,0) = \sum_{n \le x} f(n)$. Tenemos la recursividad:

$\phi(x,a+1) = \phi(x,a) - f(p_{a+1})\phi(x/p_{a+1},a).$

Imagine que tiene una etiqueta de árbol, donde las etiquetas se $\pm f(k) \phi(x/k,b)$ para algunos $k$ e $b$. Usted puede ampliar cualquier nodo en el árbol que desea mediante la aplicación de la fórmula anterior. Este tiene la propiedad de que sale de la suma de los valores en las hojas de la misma. Así que la idea es comenzar con un árbol que consta de un nodo etiquetado $\phi(x,\pi(\sqrt x))$ y seguir ampliando hasta que cualquiera de las $b=0$ o $x/k < $ algunos de corte. Si se acumulan todos los nodos se pueden evaluar todos ellos por tamizado (y una estructura de datos especial-consulte la Lagarias-Miller-Odlyzko documento para más detalles), y el valor óptimo para el corte es $x^{2/3}$ tal vez multiplicado por algunos logarítmica factores.

Aquí está la referencia a mi papel con Lagarias y Odlyzko: Informática $\pi(x)$: El Meissel-Lehmer Método Autor(es): J. C. Lagarias, V. S. Miller, A. M. Odlyzko Fuente: las Matemáticas de la Computación, Vol. 44, Nº 170 (Abr., 1985), pp 537-560

Answer 4

Esto ha sido genial. Algunas buenas respuestas aquí - voy a aceptar un poco.

Yo estaba buscando un iluminado de revisión, ya que me han puesto en práctica un enfoque que se ejecuta en $O(n^\frac{2}{3} \log n)$ tiempo y $O(n^\frac{1}{3} \log n)$ espacio para sumar los números primos a entero no negativo poderes, y quería ver cómo se comparan. No estaba listo para escribir lo que había hecho, pero creo que me voy a tomar una puñalada. Para los curiosos:

PARTE 1 - La Identidad General

Comience con la siguiente identidad

$\displaystyle\sum_{j=2}^n\frac{\Lambda(j)}{\log j}j^a = \sum_{j=2}^nj^a - \frac{1}{2}\sum_{j=2}^n\sum_{k=2}^{\frac{n}{j}}j^a \cdot k^a+ \frac{1}{3}\sum_{j=2}^n\sum_{k=2}^{\frac{n}{j}}\sum_{l=2}^{\frac{n}{jk}}j^a \cdot k^a \cdot l^a - \frac{1}{4}...$

donde $\Lambda(n)$ es el Mangoldt función. Esta es una generalización de Linnik de la identidad, que se dan aquí. Para facilitar la notación, el uso de

$D_{a,k}(n) = \displaystyle\sum_{j=2}^n j^a \cdot D_{a,k-1}(\frac{n}{j})$ y $D_{a,0}(n) = 1$

reescribir la anidados sumas de dinero en el derecho a darnos

$\displaystyle\sum_{j=2}^n\frac{\Lambda(j)}{\log j}j^a = \sum_{j=1}^{\log_2 n} \frac{-1^{j+1}}{j}D_{a,j}(n)$

Evaluamos $\log_2 n$, debido a $D_{a,k}(n) = 0$ al $n < 2^k$,

Esto es una especie de suma de primer poderes. Podemos contar el primer sumas por una especie de inversión de moebius

$\displaystyle\sum_{p \leq n} p^a = \sum_{j=1}^{\log_2 n} \sum_{k=1}^{\log_2 (n^\frac{1}{j})} \frac{-1^{k+1}}{j \cdot k}\mu(j) D_{a \cdot j, k}(n^{\frac{1}{j}})$

Por lo tanto, si podemos encontrar métodos rápidos de la informática $D_{a,k}(n)$, vamos a tener un rápido maneras de calcular $\sum_{p \leq n} p^a$

En Mathematica, esto es

DD[a_, k_, n_] := Sum[j^un DD[a, k - 1, n/j], {j, 2, n}]

DD[a_, 1, n_] := Sum[j^a, {j, 2, n}]

SumPrimes[a_, n_] := Sum[(-1)^(k + 1)/(j k) MoebiusMu[j] DD[j, k, n^(1/j)], {j, 1, Log[2, n]}, {k, 1, Log[2, (n^(1/j))]}]

SumPrimes[0,n] va a devolver el número de números primos, SumPrimes[1,n] devolverá la suma de los números primos menor que n, y así sucesivamente.

PARTE 2 - El Algoritmo Específico

Aquí está mi enfoque más rápido para el cálculo de $D_{a,k}(n)$ es inspirado por este método para el cálculo de la función de Mertens. (Si usted encuentra la siguiente valoración crítica muy interesante, pero se apresuraron, he escrito sobre mi enfoque con algo más de detalle aquí y, para el caso especial de sólo primer conteo, aquí. Una implementación en C++ es aquí)

Oso conmigo; este es un poco implicado. Se requiere de dos observaciones.

En primer lugar, podemos utilizar tamizado, para calcular los valores de $D_{a,k}(n)$ a a $n^\frac{2}{3}$ en aproximadamente el $O(n^\frac{2}{3} \log n)$ tiempo y $O(n^\frac{1}{3} \log n)$ espacio con el siguiente enfoque.

Queremos tamiz de números de hasta el $n^\frac{2}{3}$ de tal manera que tenemos la plena potencia de la firma, con $ n = {p_1} ^ {a_1} \cdot {p_2} ^ {a_2} \cdot {p_3} ^ {a_3} \cdot ... $. Con esto, el recuento normal de divisor función es $d_k(n) = \binom {{a_1} + k - 1} {a_1} \cdot \binom {{a_2} + k - 1} {a_2} \cdot \binom {{a_3} + k - 1} {a_3} \cdot ...$ El estricto recuento de los divisores de la función, un recuento de divisor de la función de exclusión de 1 factor, y es, a su vez, $d_k'(n) = \sum_{j=0}^k -1^{k-j} \binom {k}{j} d_j(n)$. Con la estricta recuento de los divisores de la función, podemos decir $ D_{a,k}(n) = D_{a,k}(n-1) + d_k'(n) \cdot n^a $ . Por lo tanto, si nos tamiz de todos los números de 1 a $n^\frac{2}{3}$, para cada número que podemos calcular sus valores de $d_k(n)$, a partir de la cual podemos calcular el $d_k'(n)$, que a su vez nos permite mantener una ejecución total de $D_{a,k}(n)$. Vamos segmento de nuestro tamiz en bloques de tamaño $n^\frac{1}{3}$ a permanecer en nuestra memoria obligado.

La segunda observación es que, utilizando la siguiente identidad, podemos expresar $D_{a,k}(n)$ como sumas que se basan únicamente en $D_{a,k}(j)$ donde $j < n^\frac{2}{3}$ y arbitraria de los valores de $D_{a,1}(j) = \sum_{k=2}^j k^a$, que en general puede ser calculada en constante o registro de tiempo para todos los valores de j para los valores de a que estamos trabajando.

Si dejamos $d_{a,k}(n) = D_{a,k}(n) - D_{a,k}(n-1)$, empezamos con esta combinatoria de identidad, cuya derivación he escrito en otro lugar, pero no tienen el espacio para mostrar:

$D_{a,k}(n) = $ $\displaystyle\sum_{j=t+1}^n d_{a,1}(j) \cdot D_{a, k-1}(\frac{n}{j}) $ $\displaystyle + \sum_{j=2}^t d_{a,k-1}(j) \cdot D_{a,1}( \frac{n}{j}) $ $+ \displaystyle \sum_{j=2}^t \sum_{s=\frac{t}{j} + 1}^\frac{n}{j} \sum_{m=1}^{k-2} d_{a,1}(s) \cdot d_{a,m}(j) \cdot D_{a, k-m-1}( \frac{n}{js} )$

Para esta identidad, t es el valor tal que $1 < t < n$. Si se mira a través de las sumas de cerca, usted debe ver que el lado derecho no depende de los valores de $d_{a,k}(j)$ donde $j > t$ e $D_{a,k}(j)$ donde $ j > \frac{n}{t}$ , excepto cuando se $k = 1$, como se desee.

Incluso si dejamos de $t=n^\frac{2}{3}$ y el tamiz de los valores de $D_{a,k}(j)$ a a $n^\frac{2}{3}$, estas sumas son demasiado grandes para ser computada en nuestro limitado en el tiempo. En su lugar, tenemos que tomar ventaja de ciertas simetrías para reducir los cálculos de estas sumas. Me voy a la mano de onda sobre el proceso que conduce a este - se puede encontrar una descripción de la misma y mucho más aquí, pero, tomando un último salto, el siguiente código de Mathematica toma la identidad estábamos hablando y evoluciona además, como la función de la etiqueta DDFast - recuerde, cuando el seguimiento a través del siguiente código, que en una implementación completa de todas las instancias de DD y d en DDFast sería miró gracias a tamizado y almacenamiento en caché dentro de nuestro tiempo y el espacio de los límites, así que lo que sigue no es un reflejo exacto de su tiempo de ejecución, sólo la precisión de la mecánica de DDFast.

DD[A_, k_, n_] := Sum[j^UN DD[a, k - 1, n/j], {j, 2, n}]

DD[A_, 1, n_] := Sum[j^A, {j, 2, n}]

d[ A_, k_, n_ ] := DD[ a, k, n ] - DD[ a, k, n - 1]

rng[ 0, start_, end_ ] := Floor[final] - (start - 1)

rng[ 1, start_, end_ ] := Piso[final] (Piso[final] + 1)/2 - (start - 1)/2

rng[ 2, start_, end_ ] := Piso[final] (Piso[final] + 1) (2 Piso[final] + 1)/ 6 - (start - 1) inicio (2 start - 1)/6

rng[ A_, start_, end_ ] := Sum[m^A, {m, inicio, fin}]

DDFast[A_, 1, n_] := rng[a, 2, n]

DDFast[A_, k_, n_] := Sum[j^UN DD[a, k - 1, n/j], {j, Piso[n^(1/3)] + 1, n^(1/2)}] + Sum[rng[A, Piso[n/(j + 1)] + 1, n/j] DD[a, k - 1, j], {j, 1, n/Piso[n^(1/2)] - 1}] + Sum[d[a, k - 1, j] rng[a, 2, n/j], {j, 2, n^(1/3)}] + Sum[s^a d[a, m, j] DD[a, k - m - 1, n/(j s)], {j, 2, n^(1/3)}, {s, Piso[Planta[n^(1/3)]/j] + 1, Piso[n/j]^(1/2)}, {m, 1, k - 2}] + Sum[(rng[A, Piso[n/(j (s + 1))] + 1, n/(j s)]) (Sum[ d[a, m, j] DD[a, k - m - 1, s], {m, 1, k - 2}]), {j, 2, n^(1/3)}, {s, 1, Piso[n/j]/Piso[Planta[n/j]^(1/2)] - 1}]

SumPrimesFast[A_, n_] := Sum[(-1)^(k + 1)/(j k) MoebiusMu[j] DDFast[j, k, n^(1/j)], {j, 1, Log[2, n]}, {k, 1, Log[2, (n^(1/j))]}]

La función de la etiqueta DDFast, que realmente es la clave aquí, puede ser calculado en $O(n^\frac{2}{3})$ tiempo de todas las funciones a las que hace referencia la memoria caché.

Así que ahí lo tenemos. Si calcular SumPrimesFast y, a su vez, DDFast, pero interleave el cálculo de dichos importes con el proceso de tamizado se describe anteriormente, usted puede terminar con algo como un $O(n^\frac{2}{3} \log n)$ tiempo y $O(n^\frac{1}{3} \log n)$ espacio algoritmo que puede contar el primer sumas de dinero para no negativo, de potencias enteras, incluyendo como principal función de conteo de $a = 0$.

Vale la pena echar un vistazo, también, en rng[ A_, start_, end_ ] := Sum[m^A, {m, inicio, fin}] - la razón por la que este algoritmo funciona de enteros no negativos es que el generador de números aleatorios puede ser calculado en tiempo constante para no negativo, valores enteros con Faulhaber la Fórmula. Es posible que el algoritmo podría trabajar para otros poderes si el rng puede ser útil extendida a otros poderes con la suficiente velocidad y precisión.

Tengo una implementación de este algoritmo en C++ aquí. Tiene un par de C de matemáticas de precisión cuestiones no he rastreado, por lo que suele ser apagado por 2 o 3, pero no es esencialmente práctica lo que he descrito aquí, y que podrían ser útiles para recorrer paso a paso con breakpoints.

Un poco más de la pulpa de la descripción de esto se puede encontrar aquí. Varios detalles que he mano-saludó aquí se describen. Incluso mejor escrito es una descripción de esto como un primer recuento de algoritmo, aquí. Se hace un mejor trabajo que muestra una serie de derivaciones.

Answer 5

Este es un problema difícil. Le pregunté acerca de ello aquí en matemáticas.sí , y aquí en cstheory. En ambos casos, mi pregunta era algo más amplio: permitir que las sumas de los diferentes exponentes en vez de solo 1. En el segundo enlace que he permitido también interactivo de pruebas.

He notado que para el exponente 0 existen algoritmos eficientes (superior a la enumeración de los números primos): las diversas analíticas o combinatoria $\pi(x)$ algoritmos. Pero nadie fue capaz de sugerir un medio eficaz para resolver el problema para cualquier exponente. Un interactivo prueba fue propuesta que permite a una persona para comprobar una propuesta de la prueba en el tiempo lineal, sino de la confianza en la prueba de ello es asintóticamente 0% contra un astuto adversario.

Yo no soy consciente de que cualquier dureza de los resultados, sin embargo, esto parece ser abiertos.