Sum of Squares of Divisors

The divisors of $6$ are $1,2,3$ and $6$.
The sum of the squares of these numbers is $1+4+9+36=50$.

Let $\operatorname{sigma}_2(n)$ represent the sum of the squares of the divisors of $n$.
Thus $\operatorname{sigma}_2(6)=50$.

Let $\operatorname{SIGMA}_2$ represent the summatory function of $\operatorname{sigma}_2$, that is $\operatorname{SIGMA}_2(n)=\sum \operatorname{sigma}_2(i)$ for $i=1$ to $n$.
The first $6$ values of $\operatorname{SIGMA}_2$ are: $1,6,16,37,63$ and $113$.

Find $\operatorname{SIGMA}_2(10^{15})$ modulo $10^9$.

The problem requires a significant knowledge in number theory, specifically, divisor function and modular arithmetic. Let’s start by rewriting the function $\operatorname{sigma}_2(n)$ as a sum of divisor function.

Note that $\operatorname{sigma}_2(n) = \sum_{d|n}d^2$. This is equivalent to $\operatorname{sigma}_2(n) = \sum_{i=1}^{n} i^2 * [n \mod i = 0]$.

Rewriting the function $[n \mod i = 0]$ using Dirichlet’s notation, we get $[n \mod i = 0] = 1 * n^0 [\text{if } n \mod i = 0] + 0 * n^0 [\text{if } n \mod i \ne 0]$.

From this, expressing $\operatorname{SIGMA}_2(n)$ as a sum from $i=1$ to $n$ over $\operatorname{sigma}_2(i)$, it gives:

$\operatorname{SIGMA}_2(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} j^2 * [i \mod j = 0]$

Rearranging the sums, we can express it as:

$\operatorname{SIGMA}_2(n) = \sum_{j=1}^{n} \sum_{i=j}^{n} j^2 * [i \mod j = 0] = \sum_{j=1}^{n} j^2 * \lfloor \frac{n}{j} \rfloor$.

The last step uses the fact that if $i \mod j = 0$, then $i$ is a multiple of $j$ and there are $\lfloor \frac{n}{j} \rfloor$ multiples of $j$ from 1 to $n$.

This equation significantly simplifies the calculation of $\operatorname{SIGMA}_2(n)$, but it’s still not efficient enough to calculate $\operatorname{SIGMA}_2(10^{15})$ modulo $10^9$ directly.

Next, we observe that the equality

$\operatorname{SIGMA}_2(x) = \sum_{n=1}^{x} \left( n^2 * \left\lfloor \frac{x}{n} \right\rfloor \right)$

can be split into two sums by devising a cutoff $m$:

$\operatorname{SIGMA}_2(x) = \sum_{n=1}^{m} \left( n^2 * \left\lfloor \frac{x}{n} \right\rfloor \right) + \sum_{n=1}^{\left\lfloor \frac{x}{m} \right\rfloor} \left( x \left\lfloor \frac{x}{n} \right\rfloor^2 – (x*(\left\lfloor \frac{x}{n+1} \right\rfloor + 1)^2 ) \right)$

Here, the first sum is for small $n$ where $\left\lfloor \frac{x}{n} \right\rfloor$ changes rapidly, and the second sum is for large $n$ where $\left\lfloor \frac{x}{n} \right\rfloor$ changes slowly.

For each sum, we have a function that is easy to compute in modular arithmetic and decreases sufficiently fast. The number of terms is about $O(\sqrt{n})$, so it can be computed within time for $n = 10^{15}$.

Finally, we need to choose optimal $m$ for minimizing total number of operations. In practice, you can find $m$ using binary search or adjusting it according to the number of operations.

Using all the steps above and fast modular arithmetic, you can compute $\operatorname{SIGMA}_2(10^{15})$ modulo $10^9$ efficiently.

Please note that this is a high-level and challenging problem in number theory, requiring deep knowledge of mathematics. The detailed implementation of algorithm and code is a substantial task and may fall beyond the discussion here.

More Answers: