Detailed mathematical approach

Problem Summary

For each integer \(n\ge 3\), the quantity \(T(n)\) is the sum of all positive offsets \(k\) that survive the divisor reformulation used by the implementations. If we write the corresponding endpoint as \(D=n+k\), then the admissible values are exactly those divisors of \(n(n-1)\) whose complementary factor has the opposite parity. Define

$E(n)=\left\{D>n: D\mid n(n-1),\ D\not\equiv \frac{n(n-1)}{D}\pmod 2\right\}.$

Then

$T(n)=\sum_{D\in E(n)}(D-n),\qquad U(N)=\sum_{n=3}^{N}T(n).$

The brute-force view would search through many possible offsets \(k\). The useful number-theoretic view is that the parity restriction becomes very simple after separating the full power of \(2\) from \(n(n-1)\).

Mathematical Approach

The implementations are built around a divisor description of the admissible endpoints. Once that description is written down, every contribution comes from the odd part of \(n(n-1)\).

Step 1: Replace Offsets by Divisor Endpoints

Write the positive offset as \(k=D-n\), so \(D=n+k\) and \(D>n\). The admissible values are precisely those for which \(D\) appears in a factor pair

$D\,Q=n(n-1)$

with opposite parity:

$D\not\equiv Q\pmod 2.$

For every such divisor \(D\), the contribution to \(T(n)\) is just the excess \(D-n\). Therefore the entire problem becomes a structured divisor sum over \(n(n-1)\).

Step 2: Separate the Full Power of Two

Write

$n(n-1)=2^t m,\qquad m\text{ odd}.$

Every divisor of \(n(n-1)\) can be written uniquely as

$D=2^j d,\qquad 0\le j\le t,\qquad d\mid m.$

Its complementary factor is then

$Q=2^{t-j}\frac{m}{d}.$

The parity condition says that exactly one of \(D\) and \(Q\) must be odd. That happens only in the two extreme cases \(j=0\) or \(j=t\). So the admissible endpoints are exactly

$D=d\qquad\text{or}\qquad D=2^t d\qquad(d\mid m).$

All intermediate choices \(0<j<t\) make both factors even, so they never contribute.

Step 3: Enumerate the Odd Divisors

Factor the odd kernel as

$m=\prod_{r=1}^{s} p_r^{e_r}.$

Then every odd divisor of \(m\) has the form

$d=\prod_{r=1}^{s} p_r^{\alpha_r},\qquad 0\le \alpha_r\le e_r.$

So once the prime exponents of \(m\) are known, generating all admissible odd divisors is a standard exponent-recursion over \(\alpha_1,\dots,\alpha_s\). This is why the implementations spend their effort on fast factorization and clean divisor enumeration rather than on testing offsets directly.

Step 4: Convert Each Divisor into a Contribution

Each odd divisor \(d\mid m\) produces two candidate endpoints, \(d\) and \(2^t d\). Only values larger than \(n\) generate a positive offset, so the contribution formula is

$T(n)=\sum_{d\mid m}\left(\max\{d-n,0\}+\max\{2^t d-n,0\}\right).$

This formula is equivalent to the earlier definition using \(E(n)\), but it is far more efficient because the loop now runs only over divisors of the odd part \(m\).

Worked Example: \(n=12\)

Here

$12\cdot 11=132=2^2\cdot 33,$

so \(t=2\) and \(m=33\). The odd divisors of \(33\) are

$1,\ 3,\ 11,\ 33.$

By Step 2, the admissible endpoints are the odd divisors themselves and the same divisors multiplied by \(2^t=4\):

$1,\ 3,\ 11,\ 33,\qquad 4,\ 12,\ 44,\ 132.$

Only the endpoints exceeding \(12\) contribute, namely \(33\), \(44\), and \(132\). Therefore

$T(12)=(33-12)+(44-12)+(132-12)=21+32+120=173.$

The divisors \(22\) and \(66\) do not appear, because they would correspond to the intermediate two-adic choice \(j=1\); their complementary factors are also even, so the parity condition fails.

Step 5: Sum Over All \(n\)

After computing \(T(n)\) for one value of \(n\), the final answer is simply

$U(N)=\sum_{n=3}^{N}T(n).$

There is no need for a separate closed form. The important reduction is the divisor formula for each \(T(n)\), because that is what makes the range up to \(1{,}234{,}567\) practical.

How the Code Works

The C++, Python, and Java implementations all follow the same algorithm. First, they build a smallest-prime-factor table up to \(N\), which makes repeated factorizations cheap. Then, for each \(n\), they remove all factors of \(2\) from \(n\) and \(n-1\), so the total removed exponent is exactly the \(t\) in

$n(n-1)=2^t m.$

The remaining odd parts are factored with the precomputed table, and their prime exponents are merged to obtain the factorization of \(m\). A recursive divisor generator then visits every odd divisor \(d\mid m\) exactly once. For each such \(d\), the implementation checks the two admissible endpoints \(d\) and \(2^t d\); whenever an endpoint exceeds \(n\), it adds the excess over \(n\) to the running total for \(T(n)\). Finally, it accumulates those values from \(n=3\) up to \(N\) to produce \(U(N)\).

Complexity Analysis

Building the smallest-prime-factor table costs \(O(N\log\log N)\) time and \(O(N)\) memory. For a fixed \(n\), stripping powers of two is negligible, factoring the odd parts is proportional to the number of prime factors encountered, and the divisor-generation step visits exactly \(\tau(m)\) odd divisors, where \(m=\operatorname{odd}(n(n-1))\). Thus the natural overall bound is

$O\!\left(N\log\log N+\sum_{n=3}^{N}\tau\!\bigl(\operatorname{odd}(n(n-1))\bigr)\right),$

with \(O(N)\) memory for the sieve plus a small amount of recursion state for the current factorization.

Footnotes and References

1. Problem page: Project Euler 834 - Add and Divide
2. Parity in number theory: Wikipedia - Parity (mathematics)
3. \(p\)-adic valuation and in particular \(v_2\): Wikipedia - p-adic valuation
4. Prime factorization: Wikipedia - Fundamental theorem of arithmetic
5. Divisor-counting function: Wikipedia - Divisor function
6. Sieve precomputation: Wikipedia - Sieve of Eratosthenes