Detailed mathematical approach

Problem Summary

For a positive integer \(N\), let

$U(N)=\{d \mid N : \gcd(d, N/d)=1\}$

be the set of unitary divisors of \(N\). The function in this problem is

$S(N)=\sum_{d \in U(N)} d^2.$

We must compute \(S(100000000!) \bmod 1000000009\). A direct construction of the factorial or of all its divisors is impossible, so the solution has to work entirely from prime exponents.

Mathematical Approach

Step 1: Prime Factorization of the Factorial

If \(n=100000000\), then

$n! = \prod_{p \le n} p^{e_p},$

where the exponent of each prime \(p\) is given by Legendre's formula:

$e_p = v_p(n!) = \sum_{k \ge 1}\left\lfloor \frac{n}{p^k} \right\rfloor.$

The sum is finite because once \(p^k > n\), the quotient becomes zero. This formula is exactly what the implementation evaluates by repeated integer division.

Step 2: Characterize the Unitary Divisors

Any divisor of \(N=\prod p^{e_p}\) has the form

$d=\prod p^{a_p}, \qquad 0 \le a_p \le e_p.$

The unitary condition \(\gcd(d,N/d)=1\) means that no prime may appear in both \(d\) and \(N/d\). Therefore, for every prime \(p\), the exponent \(a_p\) has only two valid choices:

$a_p \in \{0, e_p\}.$

If \(0 < a_p < e_p\), then \(p\) divides both \(d\) and \(N/d\), so the gcd would be larger than 1. Conversely, choosing only \(0\) or \(e_p\) makes the prime supports disjoint, so the divisor is unitary.

Step 3: Derive the Product Formula

Because each prime contributes independently, every unitary divisor corresponds to choosing either “exclude \(p^{e_p}\)” or “include \(p^{e_p}\)”. Squaring such a divisor gives either a factor \(1\) or a factor \(p^{2e_p}\) from that prime. Hence

$S(N)=\prod_{p \mid N}\left(\sum_{\varepsilon \in \{0,1\}} p^{2\varepsilon e_p}\right)=\prod_{p \mid N}\left(1+p^{2e_p}\right).$

This is the crucial simplification: the huge sum over divisors becomes one multiplicative factor per prime.

Step 4: Apply the Formula to the Factorial

Substituting the factorial exponents gives

$\boxed{S(n!)=\prod_{p \le n}\left(1+p^{2v_p(n!)}\right).}$

For the actual problem we evaluate this modulo

$M=1000000009,$

so the computation performed by the implementation is

$S(n!) \equiv \prod_{p \le n}\left(1+p^{2e_p}\right) \pmod{M}.$

No step ever needs the decimal expansion of \(n!\) itself.

Worked Example: \(4!\)

This small case is useful because it matches a checkpoint used by the implementation. We have

$4! = 24 = 2^3 \cdot 3^1.$

A unitary divisor must take exponent \(0\) or the full exponent for each prime, so the unitary divisors are

$1,\quad 2^3=8,\quad 3,\quad 2^3\cdot 3=24.$

The sum of squares is

$1^2+8^2+3^2+24^2 = 1+64+9+576 = 650.$

The product formula gives the same result immediately:

$S(4!)=(1+2^{2\cdot 3})(1+3^{2\cdot 1})=(1+64)(1+9)=65\cdot 10=650.$

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they generate every prime up to \(n\) with a sieve of Eratosthenes. Then, for each prime \(p\), they compute \(e_p=v_p(n!)\) by repeatedly dividing \(n\) by \(p\), then by \(p\) again, and accumulating the quotients \(\left\lfloor n/p \right\rfloor\), \(\left\lfloor n/p^2 \right\rfloor\), and so on.

After that, they evaluate \(p^{2e_p} \bmod M\) with binary modular exponentiation, form the factor \((1+p^{2e_p}) \bmod M\), and multiply it into a running product modulo \(M\). This avoids both overflow from the factorial itself and any attempt to enumerate divisors.

Complexity Analysis

The sieve up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. For each prime \(p\), exponent extraction needs \(O(\log_p n)\) divisions, so over all primes the extra work is

$O\left(\sum_{p \le n}\log_p n\right),$

and each modular power uses \(O(\log e_p)\) multiplications. In practice these stages are smaller than the sieve cost, so the overall method is dominated by prime generation and remains near

$O(n\log\log n)$

time with

$O(n)$

memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=429
2. Unitary divisor: Wikipedia — Unitary divisor
3. Legendre's formula: Wikipedia — Legendre's formula
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
5. Multiplicative function: Wikipedia — Multiplicative function