Cálculo de suma matemática resuelta

Question

Calcular la suma de la serie resuelta ahora

Answer 1

Tenga en cuenta que $$ q:=\left\lfloor \frac n{r^2}\right\rfloor$$ es el mismo para todos los $r$ con $$ \frac n{q+1}<r^2\le \frac nq.$$ Recordemos que $$Q(m):=\sum_{r=0}^m r^2 =\frac{r(r+1)(2r+1)}6$$ para que todos $r$ con $\left\lfloor \frac n{r^2}\right\rfloor=q$ contribuir $$ q\cdot(Q(\lfloor\tfrac nq\rfloor)-Q(\lfloor\tfrac n{q+1}\rfloor).$$ Esto nos permite calcular la contribución de todos los $r$ con $q\le c$ en $O(c)$ tiempo. Por otro lado, si $q>c$ entonces $r^2<\frac nc$ y la contribución de estos puede calcularse ingenuamente en $O(\sqrt{\tfrac nc})$ . Si $c=\sqrt[3]n$ las dos partes están en equilibrio y utilizamos $$O(\sqrt[3]n)$$ tiempo en total. Esto debería ser lo suficientemente bueno hasta $10^{18}$ cuando (como usted dice) los ingenuos $O(\sqrt n)$ es lo suficientemente bueno hasta $10^{14}$ .