Eficiente manera de computar $\sum_{i=1}^n \varphi(i) $

Question

Dado que algunos límite superior $n$ es allí una manera eficiente para calcular los siguientes:

$$\sum_{i=1}^n \varphi(i) $$

Soy consciente de que:

$$\sum_{i=1}^n \varphi(i) = \frac 12 \left( 1+\sum_{i=1}^n \mu(i) \left \lfloor \frac ni \right\rfloor ^2 \right) $$

Donde:
$\varphi(x) $ es de Euler Totient
$\mu(x) $ es la función de Möbius

Me pregunto si hay una forma para reducir el problema a simple cálculos porque mi límite superior será muy grande, es decir: $n \approx 10^{11} $.

Ni $\varphi(x) $ ni $\mu(x) $, son eficientes para calcular para un gran atado de $n$

Ingenuo algoritmos tomará un tiempo inaceptablemente largo para calcular (días) o me tendría tendría un costo prohibitivo cantidad de memoria RAM para almacenar tablas de búsqueda.

Answer 1

Usted puede calcular el $\mu$ eficiente por tamizado en intervalos. Con $n\approx10^{11},$ intervalos de longitud de $10^7$ debería funcionar bien, teniendo sólo un par de megabytes. El tiempo necesario es $O(n\log\log n)$ y del espacio es proporcional a $\sqrt n$ o así.

Para mejorar esto, tenga en cuenta que $\lfloor n/i\rfloor$ será constante en grandes extensiones y por lo que no necesitan ser calculadas muy a menudo. Usted puede entonces utilizar fast técnicas para calcular $M(k)$ para un pequeño número de $k$: $n/2,\ n/3,\ n/4,\ \ldots.$ el Tiempo necesario es de aproximadamente el $n^{5/6}$ y en el espacio es un poco más de $n^{1/3}$ usando Deléglise & Rivat. Usted puede utilizar el cribado para terminar el resto en el mismo tiempo, aunque se necesita un poco más de espacio ($\sqrt n$ sería suficiente, $n^{5/12}$ es probablemente alcanzable sin problemas). Prácticamente hablando, usted probablemente va a elegir algo más de memoria a la velocidad a la computación.

Tenga en cuenta que esta es la secuencia de A002088 en la OEIS.

Edit: también debo mencionar la secuencia de A064018 que ha $$ \sum_{n=1}^{10^{11}}\varphi(n)=3039635509283386211140 $$ (calculado por la tarde Donovan Johnson) además de la suma de otras potencias de 10.

Answer 2

Si de manera eficiente puede calcular $\sum_{i=1}^n \varphi(i)$, luego que de manera eficiente puede calcular dos valores consecutivos, por lo que de manera eficiente puede calcular $\varphi(n)$. Puesto que usted ya sabe que $\varphi(n)$ no es eficiente computable, se deduce que el $\sum_{i=1}^n \varphi(i)$ no.