Detailed mathematical approach

Problem Summary

Let \(p_m\#=\prod_{i=1}^{m} p_i\) be the primorial of the first \(m\) primes, let \(\tau(n)\) be the divisor-counting function, and define

$S(N)=\sum_{d \mid N}\tau(d)-\tau(N),\qquad E(m,n)=v_2\!\left(S\!\left((p_m\#)^n\right)\right).$

The required quantity is the cumulative sum

$Q(m,N)=\sum_{n=1}^{N}E(m,n).$

For the actual problem instance, \(m=904961\) and \(N=10^{12}\). Because that \(m\) is odd and \(N\) is enormous, the solution must turn the divisor expression into a closed formula rather than evaluating every term separately.

Mathematical Approach

The key observation is that a primorial power has exactly \(m\) distinct prime factors and all of them appear with the same exponent \(n\). That symmetry makes both the divisor sum and the \(2\)-adic valuation collapse into elementary arithmetic.

Step 1: Expand the divisor expression on a primorial power

For \(N=(p_m\#)^n\), each of the \(m\) primes has exponent \(n\), so

$\tau\!\left((p_m\#)^n\right)=(n+1)^m.$

Every divisor is obtained by choosing one exponent from \(0\) to \(n\) independently for each prime. Therefore

$\sum_{d \mid (p_m\#)^n}\tau(d)=\left(\sum_{k=0}^{n}(k+1)\right)^m=\left(\frac{(n+1)(n+2)}{2}\right)^m.$

Substituting this into the definition of \(S\) gives

$S\!\left((p_m\#)^n\right)=\left(\frac{(n+1)(n+2)}{2}\right)^m-(n+1)^m.$

Step 2: Evaluate the odd case

Let \(n=2k-1\). Then \(n+1=2k\) and \(n+2=2k+1\), so

$S\!\left((p_m\#)^{2k-1}\right)=\bigl(k(2k+1)\bigr)^m-(2k)^m=k^m\left((2k+1)^m-2^m\right).$

The bracketed factor is odd, because an odd number minus an even number is odd. Hence the entire \(2\)-adic valuation comes from the factor \(k^m\):

$E(m,2k-1)=m\,v_2(k)=m\,v_2\!\left(\frac{n+1}{2}\right).$

Step 3: Evaluate the even case

Let \(n=2r\). Then \(n+1=2r+1\) is odd, and the same identity becomes

$S\!\left((p_m\#)^{2r}\right)=\bigl((2r+1)(r+1)\bigr)^m-(2r+1)^m=(2r+1)^m\left((r+1)^m-1\right).$

Now split according to the residue of \(n\) modulo \(4\).

If \(r\) is odd, then \(n\equiv 2 \pmod 4\) and \(r+1\) is even, so \((r+1)^m-1\) is odd. Therefore

$E(m,n)=0 \qquad \text{when } n\equiv 2 \pmod 4.$

If \(r=2t\), then \(n=4t\) and \(r+1=2t+1\) is odd. Since \(m=904961\) is odd,

$\begin{aligned} (2t+1)^m-1&=(2t)\left((2t+1)^{m-1}+(2t+1)^{m-2}+\cdots+1\right). \end{aligned}$

The parenthesized sum is odd because it contains an odd number of odd terms. Hence

$E(m,4t)=v_2(2t)=1+v_2(t)=v_2(n)-1.$

For this odd \(m\), the valuation rule is therefore

$E(m,n)= \begin{cases} m\,v_2\!\left(\frac{n+1}{2}\right), & n \text{ odd},\\ 0, & n\equiv 2 \pmod 4,\\ v_2(n)-1, & 4\mid n. \end{cases}$

Step 4: Sum the residue classes

We now sum \(E(m,n)\) from \(1\) to \(N\). The class \(n\equiv 2 \pmod 4\) contributes nothing, so only odd numbers and multiples of \(4\) remain.

For odd \(n\), write \(n=2k-1\) with

$K=\left\lfloor\frac{N+1}{2}\right\rfloor.$

Then

$\sum_{\substack{1\le n\le N\\ n\text{ odd}}}E(m,n)=m\sum_{k=1}^{K}v_2(k)=m\,v_2(K!).$

For multiples of \(4\), write \(n=4t\) with

$T=\left\lfloor\frac{N}{4}\right\rfloor.$

Then

$\sum_{\substack{1\le n\le N\\ 4\mid n}}E(m,n)=\sum_{t=1}^{T}\bigl(1+v_2(t)\bigr)=T+v_2(T!).$

So the whole cumulative quantity reduces to

$Q(m,N)=m\,v_2(K!)+T+v_2(T!).$

Step 5: Replace factorial valuations with Legendre's formula

Legendre's formula for the prime \(2\) says

$v_2(x!)=\sum_{j\ge 1}\left\lfloor\frac{x}{2^j}\right\rfloor=x-\operatorname{popcount}(x).$

This turns the final sum into direct arithmetic:

$Q(m,N)=m\left(K-\operatorname{popcount}(K)\right)+T+\left(T-\operatorname{popcount}(T)\right).$

No iteration up to \(N\) survives the derivation.

Worked Example: \(N=8\)

This checkpoint is small enough to verify by hand and already shows the full mechanism. Here

$K=\left\lfloor\frac{8+1}{2}\right\rfloor=4,\qquad T=\left\lfloor\frac{8}{4}\right\rfloor=2.$

Using Legendre,

$v_2(4!)=4-\operatorname{popcount}(4)=4-1=3,\qquad v_2(2!)=2-\operatorname{popcount}(2)=2-1=1.$

Therefore

$Q(m,8)=3m+3.$

For the actual problem parameter \(m=904961\), this becomes

$Q(904961,8)=3\cdot 904961+3=2714886,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations never loop from \(1\) to \(N\). They apply the closed form derived above directly to the odd input \(m=904961\).

Each implementation computes

$K=\left\lfloor\frac{N+1}{2}\right\rfloor,\qquad T=\left\lfloor\frac{N}{4}\right\rfloor,$

then evaluates \(v_2(K!)\) and \(v_2(T!)\) via the identity \(x-\operatorname{popcount}(x)\), and finally forms

$m\,v_2(K!)+T+v_2(T!).$

The C++ implementation also includes two small sanity checks: one confirms that \(S(6)=5\), and another confirms the checkpoint \(Q(904961,8)=2714886\). After that, the exact decimal answer for \(N=10^{12}\) is printed.

Complexity Analysis

For the fixed-size integer inputs used here, the algorithm runs in \(O(1)\) time and \(O(1)\) memory. The derivation removes every loop over \(n\); only a handful of integer divisions, bit counts, and additions remain.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=561
2. Primorial: Wikipedia — Primorial
3. Divisor function: Wikipedia — Divisor function
4. \(p\)-adic valuation: Wikipedia — \(p\)-adic valuation
5. Legendre's formula: Wikipedia — Legendre's formula