Sum of Squares II

For a positive integer, $n$, define $g(n)$ to be the maximum perfect square that divides $n$.
For example, $g(18) = 9$, $g(19) = 1$.

Also define
$$\displaystyle S(N) = \sum_{n=1}^N g(n)$$

For example, $S(10) = 24$ and $S(100) = 767$.

Find $S(10^{14})$. Give your answer modulo $1\,000\,000\,007$.

The solution of this problem uses number theory and a bit of combinatorics.

Let’s think of each number in terms of its prime factorization. Each number can be written as $p_1^{a_1}p_2^{a_2}…p_k^{a_k}$ where $p_i$ are primes and $a_i$ are the powers of those primes.

Now, using the definition of function $g(n)$, we can note that the maximum perfect square that divides $n$ will be a product of the square of primes, where for each prime, its power will be the largest even number not more than $a_i$.

So we can write $g(p_1^{a_1}p_2^{a_2}…p_k^{a_k})$ as $p_1^{[a_1/2]*2}p_2^{[a_2/2]*2}…p_k^{[a_k/2]*2}$
where $[x]$ indicates the floor of x or the greatest integer less than or equal to x.

So the series $S(N)$, $\displaystyle S(N) = \sum_{n=1}^N g(n)$ breaks down to $\displaystyle S(N) = \sum_{p_1^{a_1},p_2^{a_2},..,p_k^{a_k}\le N} p_1^{[a_1/2]*2}p_2^{[a_2/2]*2}…p_k^{[a_k/2]*2}$.

If we look more closely, the powers of the primes that contribute to this summation are always even (0, 2, 4, 6,…).

So, instead of putting all powers of primes which are less than or equal to N, we can go for all primes and their even powers which are less than or equal to N.

It makes computation easier and more manageable.

Let P be the set of primes less than or equal to N. Now the summation will be for numbers of the form $p_1^{a_1}p_2^{a_2}…p_k^{a_k}$ , here $p_i$ is from set P and $a_i$ is an even number such that the number $p_1^{a_1}p_2^{a_2}…p_k^{a_k}$ is less than or equal to N.

Now, calculate this sum over all these possible numbers and find it modulo $1,000,000,007$

Note: Calculating the sum over all possible numbers under these conditions is a difficult task if done directly and requires optimization using dynamic programming or recursion.
For the ideal calculation of $S(10^{14})$ modulo $1,000,000,007$, it might require significant computational assistance to pull it off because of the large input size.

Remember the primary approach to solve this problem: We must find all combinations of prime’s even powers such that they jointly don’t exceed $N$.

More Answers: