Detailed mathematical approach

Problem Summary

The problem asks for

$U(10^4)=\sum_{n=1}^{10^4}u(n^3),$

where the arithmetic function \(u(m)\) is determined by a 2-adic valuation. If we set \(k=m+1\) and define the 2-adically convergent series

$S_k=\sum_{j\ge 0}(-2)^j\binom{2(k+j)}{k+j},$

then the required quantity is

$u(m)=k+v_2(-3S_k).$

Here \(v_2(x)\) denotes the exponent of 2 dividing \(x\). The difficulty is not the outer sum itself but recovering the power of 2 in this series for many large cubic inputs without expanding enormous exact integers.

Mathematical Approach

The key idea is to stay inside \(\mathbb{Z}/2^{64}\mathbb{Z}\). At that precision the relevant 2-adic valuation is still visible, while every arithmetic step fits into machine-word computations.

Step 1: Truncate the 2-adic series at fixed precision

Let \(C_r=\binom{2r}{r}\). A standard fact for central binomial coefficients is

$v_2(C_r)=s_2(r),$

where \(s_2(r)\) is the number of 1-bits in the binary expansion of \(r\). Therefore

$v_2\!\left((-2)^j C_{k+j}\right)=j+s_2(k+j)\ge j+1.$

So modulo \(2^{64}\), all sufficiently late terms vanish automatically. A 64-step accumulation is enough at the chosen precision, which converts an infinite 2-adic series into a fixed-size computation.

Step 2: Separate powers of 2 from odd parts

For any nonzero integer define its odd part by

$\operatorname{Odd}(x)=\frac{x}{2^{v_2(x)}}.$

Then every central binomial coefficient splits as

$C_r=\operatorname{Odd}(C_r)\,2^{s_2(r)}.$

The power of 2 is therefore known immediately from the binary digit count of \(r\). The remaining task is to evaluate the odd part efficiently. Using factorials,

$\operatorname{Odd}(C_r)=\frac{\operatorname{Odd}((2r)!)}{\operatorname{Odd}(r!)^2}.$

Because the denominator is odd, it is invertible modulo \(2^{64}\), so division can be replaced by multiplication with odd modular inverses.

Step 3: Build the odd part of a factorial recursively

Introduce the odd prefix product

$F(u)=\prod_{t=0}^{u-1}(2t+1)=1\cdot 3\cdot 5\cdots (2u-1).$

Every factor in \(n!\) is either odd or twice a smaller integer. After stripping away powers of 2, this gives

$\operatorname{Odd}(n!)=\operatorname{Odd}\!\left(\left\lfloor\frac{n}{2}\right\rfloor!\right)\,F\!\left(\left\lceil\frac{n}{2}\right\rceil\right).$

Iterating the recursion yields

$\operatorname{Odd}(n!)=\prod_{a\ge 0}F\!\left(\left\lfloor\frac{n+2^a}{2^{a+1}}\right\rfloor\right),$

with only \(O(\log n)\) nontrivial factors. This is why the implementation can evaluate the odd part of very large factorials without ever materializing the factorial itself.

Step 4: Evaluate \(F(u)\) modulo \(2^{64}\) with a Newton series

In the working 2-adic setting, the implementation evaluates \(F(u)\) from a forward-difference expansion

$F(u)\equiv \sum_{t=0}^{126}\Delta^tF(0)\binom{u}{t}\pmod{2^{64}}.$

Only the first 127 coefficients are needed at this precision, so they are precomputed once from \(F(0),F(1),\dots,F(126)\). The generalized binomial coefficients \(\binom{u}{t}\) are also formed modulo \(2^{64}\) by separating powers of 2 from odd numerator and denominator parts.

Whenever an odd denominator must be inverted, Newton's method in the 2-adic world is used:

$x_{r+1}=x_r(2-ax_r)\pmod{2^{64}},\qquad a\text{ odd}.$

Each iteration doubles the number of correct low bits, so six rounds already reach full 64-bit precision.

Step 5: Update consecutive central binomial coefficients cheaply

Once the odd part of \(C_k\) is known, the next one follows from

$\frac{C_{r+1}}{C_r}=\frac{2(2r+1)}{r+1}.$

After removing powers of 2, the odd parts satisfy

$\operatorname{Odd}(C_{r+1})=\operatorname{Odd}(C_r)\,\frac{2r+1}{\operatorname{Odd}(r+1)}.$

So the implementation computes the first central binomial term at \(r=k\), then advances through \(r=k,k+1,\dots\) with a short recurrence. At each step it restores the full coefficient by shifting the odd part by \(s_2(r)\), multiplies by the appropriate power of \(-2\), and accumulates modulo \(2^{64}\).

Step 6: Worked example for \(m=4\)

Here \(k=m+1=5\). The first central binomial coefficients are

$\binom{10}{5}=252=2^2\cdot 63,\qquad \binom{12}{6}=924=2^2\cdot 231,\qquad \binom{14}{7}=3432=2^3\cdot 429.$

Hence the first terms of the series have valuations

$v_2\!\left(\binom{10}{5}\right)=2,\qquad v_2\!\left(-2\binom{12}{6}\right)=3,\qquad v_2\!\left(4\binom{14}{7}\right)=5.$

Modulo \(8\), only the first term survives, so

$S_5\equiv \binom{10}{5}\equiv 4\pmod{8}.$

Multiplication by \(-3\) does not change the 2-adic valuation because 3 is odd. Therefore

$v_2(-3S_5)=2,$

and thus

$u(4)=5+2=7.$

This matches the small checkpoint used by the implementation and shows why the low 2-adic valuation, not the exact integer magnitude, is the critical object.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they precompute the odd prefix products \(F(0),\dots,F(126)\), the associated forward differences, and the inverses of the small odd numbers needed in the Newton expansion. Then, for each cube input \(m=n^3\), the implementation constructs the odd part of the first central binomial coefficient at \(k=m+1\), restores its full power of 2 from the binary digit count, and evaluates the fixed-length alternating series modulo \(2^{64}\).

After the series has been accumulated, the implementation multiplies by \(-3\), counts the exponent of 2 in the resulting residue, adds \(k\), and obtains \(u(m)\). The outer loop sums these values for \(n=1,2,\dots,10^4\). The direct compiled implementations also split that outer range across available processor cores, while the Python version delegates to the same optimized core computation.

Complexity Analysis

The precomputation phase is constant-sized: it stores only 127 forward-difference entries and a matching set of small odd inverses, so its cost is \(O(1)\) for this problem. For one value \(u(m)\), the odd-factorial formula needs \(O(\log m)\) evaluations of \(F\), each performed in constant time with the fixed Newton expansion, and the series summation always uses 64 iterations. Thus one query costs \(O(\log m)\) word operations, and summing \(u(n^3)\) for \(1\le n\le N\) costs

$O\!\left(\sum_{n=1}^{N}\log(n^3)\right)=O(N\log N)$

total time with \(O(1)\) extra memory beyond the fixed tables. In practice the constants are small because all arithmetic is carried out modulo \(2^{64}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=792
2. 2-adic valuation: Wikipedia - P-adic valuation
3. Central binomial coefficient: Wikipedia - Central binomial coefficient
4. Legendre's formula: Wikipedia - Legendre's formula
5. Hensel's lemma: Wikipedia - Hensel's lemma
6. Newton series: Wikipedia - Newton series