Sum of Squares of Unitary Divisors

A unitary divisor $d$ of a number $n$ is a divisor of $n$ that has the property $\gcd(d, n/d) = 1$.
The unitary divisors of $4! = 24$ are $1, 3, 8$ and $24$.
The sum of their squares is $1^2 + 3^2 + 8^2 + 24^2 = 650$.

Let $S(n)$ represent the sum of the squares of the unitary divisors of $n$. Thus $S(4!)=650$.

Find $S(100\,000\,000!)$ modulo $1\,000\,000\,009$.

Let’s first understand the task: we’re given the function $S(n)$ which evaluates to the sum of the squares of the unitary divisors of factorials. We are asked to find the value of $S(100\,000\,000!)$ modulo $1\,000\,000\,009$.

This is a hard number theory problem that can’t be solved directly, we need to use some theory and a programming solution for it.

We will use a couple of facts:
1. A unitary divisor is created by taking a subset of prime factors of a number, where each prime in the subset is raised to the same power that it is raised to in the factorization of the number.
2. If $n$ is a power of a prime number, then the sum of the squares of the unitary divisors of $n$ is given by $(1^2+2^2+…+n^2)$.

For example, if we look at $5! = 5 * 4 * 3 * 2 * 1$, where the prime factorization has powers of $1, 2, 1,$ and $3$ respectively, then the unitary divisors of $5!$ and their squares are:

$2^0 (or 1), 2^1, 2^2$ which gives $1^2, 2^2, 4^2 = 1, 4, 16$, and
$3^0 (or 1), 3^1$ which gives $1^2, 3^2 = 1, 9$ and
$5^0 (or 1), 5^1$ which gives $1^2, 5^2 = 1, 25$

When you multiply these together, you get all the unitary divisors of $5!$ Their squares are all the perfect squares that divide $5!$

The problem can be solved using dynamic programming and inclusion-exclusion principle along with the two facts above.

Using Fast Fourier Transform (FFT) or Number Theoretic Transform (NTT), we can compute the sum of squares of unitary divisors of $n!$ for each prime $p$ up to $n$ fast. After we got those sums, we multiply them together by the convolution of polynomial.

Finding the prime numbers can be done with the Sieve of Eratosthenes, and there are less than $50$ million primes less than $100$ million, which is doable on a computer.

The specific calculation steps involve continuous multiplication, so the result cannot be calculated directly, but the modulo operation can be used to keep the number within a manageable range.

This kind of problem requires not only clever mathematical transformations, but also efficient use of computational resources. Regularly, a solution in programming language such as Python or C++ is used to get the final answer.

More Answers: