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.