Detailed mathematical approach

Problem Summary

For a positive integer \(m=\prod p_i^{a_i}\), its roundness is the largest integer \(r\ge 1\) such that \(m\) is a perfect \(r\)th power. For every nontrivial \(m\), that is exactly

$\rho(m)=\gcd(a_1,a_2,\dots).$

The total roundness of \(N\) is defined by summing \(\rho(d)\) over every divisor \(d\mid N\) with \(d>1\):

$T(N)=\sum_{\substack{d\mid N\\ d>1}}\rho(d).$

Problem 926 asks for \(T(10^7!)\bmod 10^9+7\). The divisor \(1\) is excluded for an important reason: it is a perfect \(k\)th power for every \(k\), so any layer-by-layer counting formula would otherwise contain an infinite extra contribution.

Mathematical Approach

The implementations never enumerate divisors of \(10^7!\), and they never compute \(\gcd\) values divisor by divisor. Instead, they describe every divisor through the prime exponents of the factorial, convert roundness into a sum over perfect-power layers, and then maintain the layer counts with a sweep over the breakpoints of floor quotients.

Prime-Exponent Description of the Divisors of \(n!\)

Write

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

where each exponent is given by Legendre's formula

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

Every divisor of \(n!\) is then uniquely determined by choosing exponents

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

For \(d>1\), only the positive exponents matter, so

$\rho(d)=\gcd\{a_p:\ a_p>0\}.$

This is the real problem-specific object behind the task: the answer depends only on the multiset of factorial exponents \(\{e_p\}\), not on the divisors themselves as standalone integers.

Counting Perfect-Power Layers Instead of Individual \(\gcd\) Values

A divisor with roundness \(g\) is a perfect \(k\)th power for exactly the integers \(k\) with \(1\le k\le g\). Equivalently,

$\rho(d)=\sum_{k\ge 1}\mathbf{1}\!\left(d\text{ is a perfect }k\text{th power}\right).$

Summing that identity over all nontrivial divisors gives

$T(n!)=\sum_{k\ge 1}\#\left\{d\mid n!:\ d>1,\ d\text{ is a perfect }k\text{th power}\right\}.$

For a fixed \(k\), the divisor \(d=\prod p^{a_p}\) is a perfect \(k\)th power exactly when each exponent is divisible by \(k\), so we can write \(a_p=k b_p\) with

$0\le b_p\le \left\lfloor\frac{e_p}{k}\right\rfloor.$

That makes the number of perfect \(k\)th-power divisors

$D_k-1,\qquad D_k=\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right).$

The factor \(D_k\) counts all choices of the scaled exponents \(b_p\), including the all-zero choice that produces the divisor \(1\); the final \(-1\) removes that forbidden divisor.

Since the largest factorial exponent is \(e_2=v_2(n!)\), the sum stops at

$E=\max_{p\le n} e_p=v_2(n!).$

So the whole task becomes

$\boxed{T(n!)=\sum_{k=1}^{E}\left(\prod_{p\le n}\left(\left\lfloor\frac{e_p}{k}\right\rfloor+1\right)-1\right)\pmod{10^9+7}.}$

At \(k=1\), this product is simply the divisor count \(\tau(n!)\), so the first layer already contributes \(\tau(n!)-1\).

Compressing Equal Factorial Exponents

Rebuilding the product over all primes for every \(k\) would still be too slow, because \(n=10^7\) has hundreds of thousands of primes. The key compression used by all three implementations is to group primes by the value of their factorial exponent. Define

$c_e=\#\left\{p\le n:\ v_p(n!)=e\right\}.$

Then the layer count becomes

$D_k=\prod_{e\ge 1}\left(\left\lfloor\frac{e}{k}\right\rfloor+1\right)^{c_e}.$

Now the problem is no longer indexed by primes, but by distinct exponent values \(e\). Many primes share the same \(e\), so this representation is dramatically smaller than the raw prime list while remaining exactly equivalent.

Where the Product Changes, and Why a Sweep Works

For one fixed exponent value \(e\), only the factor

$f_e(k)=\left\lfloor\frac{e}{k}\right\rfloor+1$

matters. This function is piecewise constant in \(k\). If at some left endpoint \(l\) we have

$q=\left\lfloor\frac{e}{l}\right\rfloor,$

then the same quotient persists up to

$r=\left\lfloor\frac{e}{q}\right\rfloor.$

So one quotient value controls the entire interval \(l\le k\le r\). The implementations exploit exactly those interval boundaries. They start from

$D_1=\prod_{e\ge 1}(e+1)^{c_e},$

and whenever a group with multiplicity \(c_e\) changes from an old factor \(t_{\text{old}}\) to a new factor \(t_{\text{new}}\), the current product is updated by

$\left(\frac{t_{\text{new}}}{t_{\text{old}}}\right)^{c_e} \pmod{10^9+7}.$

Because the modulus is prime, those divisions are implemented with modular inverses. When \(k=e+1\), the factor for that group becomes \(1\) permanently, so no further updates from that group are needed.

A concrete one-group example makes the event logic visible. For \(e=8\), the values of \(\left\lfloor 8/k\right\rfloor+1\) are

$9\text{ at }k=1,\quad 5\text{ at }k=2,\quad 3\text{ at }k=3,4,\quad 2\text{ at }k=5,6,7,8,\quad 1\text{ afterwards}.$

So this single exponent group generates updates exactly at the breakpoints \(k=2,3,5,9\). The global algorithm does the same for every distinct exponent value, sorts all update events, and sweeps upward through \(k\).

Worked Example: \(10!\)

For \(n=10\), Legendre's formula gives

$10!=2^8\cdot 3^4\cdot 5^2\cdot 7^1.$

So the factorial exponents are \(8,4,2,1\), and the perfect-power layer counts are

$\begin{aligned} D_1&=(8+1)(4+1)(2+1)(1+1)=270,\\ D_2&=(4+1)(2+1)(1+1)(0+1)=30,\\ D_3&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_4&=(2+1)(1+1)(0+1)(0+1)=6,\\ D_5&=D_6=D_7=D_8=2. \end{aligned}$

Therefore

$T(10!)=(270-1)+(30-1)+(6-1)+(6-1)+4\cdot(2-1)=312.$

This example shows the exact meaning of the layer formula. The first layer counts all nontrivial divisors, the second layer counts all nontrivial square divisors, the third layer counts all nontrivial cube divisors, and so on. Summing those layers reproduces the sum of roundness values without ever enumerating the divisors themselves.

How the Code Works

Computing the Exponent Groups

The C++, Python, and Java implementations first generate the primes up to \(n\) with a sieve. For each prime \(p\), they evaluate \(v_p(n!)\) by repeated division, which is exactly Legendre's formula in iterative form. While doing that, they build the multiplicities \(c_e\) and record the maximum exponent \(E\).

Turning Quotient Drops into Multiplicative Events

Once the groups \((e,c_e)\) are known, the implementations compute the initial product \(D_1\). Then each distinct exponent value is processed independently. Using the interval rule \(r=\lfloor e/q\rfloor\), the code locates every \(k\) where \(\lfloor e/k\rfloor\) changes and emits one event containing that sweep position and the multiplicative ratio that updates the contribution of the whole group. After all groups have emitted their events, those events are sorted by \(k\).

Sweeping \(k\) While Maintaining the Invariant \( \text{current}=D_k \)

The final sweep runs from \(k=1\) to \(k=E\). Before adding the contribution for a given \(k\), the implementation applies every event scheduled at that position. The maintained invariant is simple and exact: after processing all events at \(k\), the running product equals \(D_k\) modulo \(10^9+7\). The answer then adds \(D_k-1\), again subtracting the trivial divisor \(1\). That is the whole algorithm.

Complexity Analysis

Let \(E=v_2(n!)\), and let \(B\) be the total number of update events produced by all distinct exponent groups. The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Computing all factorial exponents costs \(O\!\left(\sum_{p\le n}\log_p n\right)\) arithmetic steps.

After that, event generation costs \(O(B)\), sorting costs \(O(B\log B)\), and the sweep costs \(O(E+B)\). In practice, \(B\) is far smaller than the naive \(E\cdot\pi(n)\) recomputation cost because each exponent group changes only at quotient breakpoints rather than at every value of \(k\). Memory usage is \(O(n+B)\), dominated by the sieve storage and the event list.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=926
2. Legendre's formula: Wikipedia - Legendre's formula
3. Perfect power: Wikipedia - Perfect power
4. Divisor function: Wikipedia - Divisor function
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
6. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse