Project Euler Problem 926

Solution

Answer: 40410219

For a number $n$, the roundness in base $b$ is the largest $k$ such that $b^k \mid n$.

Hence:

$$R(n)=\sum_{b\ge2} v_b(n)$$

where $v_b(n)$ is the exponent of $b$ dividing $n$.

Now observe:

$$v_b(n)=\sum_{k\ge1} [b^k\mid n]$$

$$R(n)=\sum_{k\ge1} #{b\ge2 : b^k\mid n}.$$

$$n=\prod p_i^{a_i},$$

then $b^k\mid n$ iff every prime exponent of $b$ is at most $\left\lfloor a_i/k\right\rfloor$.

Therefore the number of such $b$ is

$$\prod_i \left(\left\lfloor \frac{a_i}{k}\right\rfloor+1\right)-1,$$

(the “$-1$” excludes $b=1$).

So:

$$R(n)=\sum_{k\ge1} \left( \prod_i \left(\left\lfloor \frac{a_i}{k}\right\rfloor+1\right)-1 \right).$$

For $n=N!$, the exponents are

$$a_p=v_p(N!)=\sum_{j\ge1}\left\lfloor \frac{N}{p^j}\right\rfloor.$$

The following Python code computes the value efficiently.

MOD = 10**9 + 7
N = 10_000_000

# exponent of 2 in N! gives the maximum possible k
a2 = 0
t = N
while t:
    t //= 2
    a2 += t

# D[k] = product over primes p of (floor(v_p(N!)/k) + 1)
D = [1] * (a2 + 1)

# sieve of Eratosthenes
sieve = bytearray(b"\x01") * (N + 1)
sieve[0] = sieve[1] = 0

limit = int(N**0.5)
for i in range(2, limit + 1):
    if sieve[i]:
        step = i
        start = i * i
        sieve[start:N + 1:step] = b"\x00" * (((N - start) // step) + 1)

primes = [i for i in range(2, N + 1) if sieve[i]]

# process each prime exponent in N!
for p in primes:
    a = 0
    t = N
    while t:
        t //= p
        a += t

    for k in range(1, a + 1):
        D[k] = (D[k] * (a // k + 1)) % MOD

answer = sum(x - 1 for x in D) % MOD
print(answer)

Verification on the sample:

$R(20)=6$
$R(10!)=312$

both match the statement.

Running the computation for $10,000,000!$ gives:

Answer: 40410219