Detailed mathematical approach

Problem Summary

The implementations first collapse the original three-operator expression with the identity

$(u \oplus v) + (u \wedge v) + \operatorname{OR}(u,v)=2\operatorname{OR}(u,v).$

So the target quantity can be written as

$G(n)=2\sum_{x=0}^{n}\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr),$

where \(\operatorname{OR}\) denotes bitwise OR. The real input is \(n=10^{18}\), so a direct double loop is hopeless. The solution therefore derives recurrences that replace \(n\) by roughly \(n/2\) at every step.

Mathematical Approach

Introduce the diagonal sum

$T(x)=\sum_{k=0}^{x}\operatorname{OR}\bigl(k,x-k\bigr)$

and its prefix sum

$Q(n)=\sum_{x=0}^{n}T(x).$

Then the desired answer is simply

$G(n)=2Q(n).$

Step 1: Use bitwise parity identities

Writing integers as \(2a\) or \(2a+1\) isolates the least significant bit. The four cases are

$\operatorname{OR}(2a,2b)=2\operatorname{OR}(a,b),$

$\operatorname{OR}(2a+1,2b)=2\operatorname{OR}(a,b)+1,$

$\operatorname{OR}(2a,2b+1)=2\operatorname{OR}(a,b)+1,$

$\operatorname{OR}(2a+1,2b+1)=2\operatorname{OR}(a,b)+1.$

Each identity strips off one binary digit and replaces the original pair by a smaller pair. That is the key divide-and-conquer observation.

Step 2: Derive the recurrence for one diagonal \(T(x)\)

Take an even argument \(x=2m\). The pairs \((k,2m-k)\) split into even-even and odd-odd cases.

If \(k=2a\), then \(2m-k=2(m-a)\), so the contribution is \(2\operatorname{OR}(a,m-a)\).

If \(k=2a+1\), then \(2m-k=2(m-a-1)+1\), so the contribution is \(2\operatorname{OR}(a,m-a-1)+1\).

Summing both families gives

$\begin{aligned} T(2m) &=\sum_{a=0}^{m}2\operatorname{OR}(a,m-a)+\sum_{a=0}^{m-1}\left(2\operatorname{OR}(a,m-1-a)+1\right)\\ &=2T(m)+2T(m-1)+m. \end{aligned}$

For an odd argument \(x=2m+1\), every pair has opposite parity, and both parity orders reduce to the same smaller problem. Therefore

$\begin{aligned} T(2m+1) &=\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)+\sum_{a=0}^{m}\left(2\operatorname{OR}(a,m-a)+1\right)\\ &=4T(m)+2(m+1). \end{aligned}$

Step 3: Turn \(T(x)\) into a recurrence for the prefix sum \(Q(n)\)

Since \(Q(n)\) is the prefix sum of \(T\), an even index can be grouped by parity:

$Q(2m)=\sum_{j=0}^{m}T(2j)+\sum_{j=0}^{m-1}T(2j+1).$

Substituting the formulas from Step 2 and collecting the repeated terms yields

$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2}.$

For odd indices, start from \(Q(2m+1)=Q(2m)+T(2m+1)\). Because

$T(m)=Q(m)-Q(m-1),$

the odd case simplifies to

$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$

Step 4: Final recurrence system and boundary values

The whole computation is determined by the zero boundary rule

$T(n)=Q(n)=0 \qquad \text{for } n\le 0,$

together with

$T(2m)=2T(m)+2T(m-1)+m,$

$T(2m+1)=4T(m)+2(m+1),$

$Q(2m)=2Q(m)+6Q(m-1)+\frac{3m(m+1)}{2},$

$Q(2m+1)=6Q(m)+2Q(m-1)+\frac{3m^2+7m+4}{2}.$

The polynomial parts are always integers: \(m(m+1)\) is even, and \(3m^2+7m+4 \equiv m(m+1)\pmod 2\) is even as well. This is why the modular implementation can safely replace division by \(2\) with multiplication by the modular inverse of \(2\).

Step 5: Worked example for \(n=10\)

Start from the small diagonal values:

$T(1)=2,\qquad T(2)=5,\qquad T(4)=16,\qquad T(5)=26.$

The even recurrence then gives

$T(10)=2T(5)+2T(4)+5=2\cdot 26+2\cdot 16+5=89.$

For the prefix sums, one obtains

$Q(4)=35,\qquad Q(5)=61,$

so

$Q(10)=2Q(5)+6Q(4)+\frac{3\cdot 5\cdot 6}{2}=2\cdot 61+6\cdot 35+45=377.$

Finally,

$G(10)=2Q(10)=754,$

which matches the checkpoint used by the implementations. A second checkpoint is \(G(100)=583766\).

How the Code Works

The C++, Python, and Java implementations memoize the pair \((T(n),Q(n))\) for each requested argument. When a new state is needed, they first evaluate the two smaller states at \(\lfloor n/2\rfloor\) and \(\lfloor n/2\rfloor-1\), then apply the even or odd formula above.

All arithmetic is performed modulo \(10^9+7\). The coefficients involving \(\frac{1}{2}\) are handled by multiplying with the modular inverse of \(2\), so the recurrence remains exact in modular arithmetic.

Once the memoized prefix value \(Q(n)\) is known, the final answer is returned as \(2Q(n)\bmod 10^9+7\).

Complexity Analysis

Each recurrence step replaces \(n\) by \(\lfloor n/2\rfloor\) or \(\lfloor n/2\rfloor-1\), so only a logarithmic number of distinct arguments are memoized. That gives \(O(\log n)\) time and \(O(\log n)\) memory. The direct definition, by contrast, needs \(\Theta(n^2)\) bitwise evaluations.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=760
2. Bitwise operation: Wikipedia — Bitwise operation
3. Exclusive or: Wikipedia — Exclusive or
4. Divide-and-conquer algorithm: Wikipedia — Divide-and-conquer algorithm
5. Memoization: Wikipedia — Memoization
6. Recurrence relation: Wikipedia — Recurrence relation