Detailed mathematical approach

Problem Summary

For a bound \(n\), we consider all pairs of nonnegative integers \((u,v)\) with \(u \le v \le n\) that satisfy the carry-less equation

$u \otimes u \oplus \bigl((2u) \otimes v\bigr) \oplus (v \otimes v)=5.$

Here \(\oplus\) is bitwise XOR and \(\otimes\) is carry-less multiplication, meaning binary digits are multiplied without carries. The required value is

$X(n)=\bigoplus_{\substack{(u,v)\text{ solves the equation}\\v\le n}} v.$

A direct search over all pairs up to \(n\) would cost \(O(n^2)\), so the real task is to describe the complete solution set in a structured way and then aggregate the second coordinates.

Mathematical Approach

The decisive simplification is to reinterpret binary integers as polynomials over \(\mathbb{F}_2\). In that model, XOR becomes addition, carry-less multiplication becomes ordinary polynomial multiplication, and the equation turns into a quadratic form preserved by a simple recurrence.

Step 1: Translate the bit operations into polynomial algebra

Write the binary expansions

$u=\sum_{i\ge 0} u_i 2^i,\qquad v=\sum_{i\ge 0} v_i 2^i,\qquad u_i,v_i\in\{0,1\},$

and associate to them the polynomials

$U(t)=\sum_{i\ge 0} u_i t^i,\qquad V(t)=\sum_{i\ge 0} v_i t^i.$

Under this dictionary, bitwise XOR is just addition in \(\mathbb{F}_2[t]\):

$u\oplus v \leftrightarrow U(t)+V(t).$

Carry-less multiplication is exactly polynomial multiplication:

$u\otimes v \leftrightarrow U(t)V(t).$

Also, multiplying an integer by \(2\) shifts every bit left by one place, so it corresponds to multiplication by \(t\):

$2u \leftrightarrow tU(t).$

Because \(5=101_2\), the constant on the right becomes

$5 \leftrightarrow 1+t^2.$

Therefore the original equation is equivalent to

$U(t)^2+tU(t)V(t)+V(t)^2=1+t^2.$

It is convenient to define the quadratic form

$Q(U,V)=U^2+tUV+V^2.$

The problem is now: find all polynomial pairs \((U,V)\) over \(\mathbb{F}_2[t]\) such that \(Q(U,V)=1+t^2\), then XOR the corresponding integer values of \(v\).

Step 2: Find a transformation that preserves the quadratic form

Consider the map

$T(U,V)=\bigl(V,tV+U\bigr).$

A direct calculation in characteristic \(2\) shows that it preserves \(Q\):

$\begin{aligned} Q\bigl(V,tV+U\bigr) &=V^2+tV(tV+U)+(tV+U)^2\\ &=V^2+t^2V^2+tUV+t^2V^2+U^2\\ &=U^2+tUV+V^2\\ &=Q(U,V). \end{aligned}$

The cancellation of the two \(t^2V^2\) terms is the key point. So every solution generates another solution after one application of \(T\).

The pair

$\bigl(0,1+t\bigr)$

is an obvious base solution because

$Q(0,1+t)=(1+t)^2=1+t^2.$

Mapping back from polynomials to integers gives the first valid pair

$(0,3).$

Step 3: Prove that every solution comes from that base solution

The inverse map is just as simple:

$T^{-1}(U,V)=\bigl(V+tU,U\bigr).$

It also preserves \(Q\). Now suppose \((U,V)\) is any nonzero solution and \(\deg U \le \deg V=d\). Since the right-hand side \(1+t^2\) has degree \(2\), the leading term of \(V^2\), which has degree \(2d\), must disappear whenever \(d>1\).

The only other term that can cancel degree \(2d\) is \(tUV\). Therefore

$\deg U=d-1.$

That means the leading terms of \(V\) and \(tU\) are equal, so in characteristic \(2\) they cancel and

$\deg(V+tU)<d.$

Applying \(T^{-1}\) to \((U,V)\) yields another solution whose maximum degree is strictly smaller. Repeating this descent eventually reaches a solution with \(\deg V=1\).

At that point we can write

$U=c,\qquad V=t+d,\qquad c,d\in\{0,1\},$

and substitute into \(Q(U,V)=1+t^2\). Comparing coefficients shows that the unique possibility is

$U=0,\qquad V=1+t.$

So every admissible pair lies in the orbit generated by repeated applications of \(T\) to the base solution.

Step 4: Convert the orbit into an integer recurrence

If \((u_k,v_k)\) is the integer pair corresponding to \((U_k,V_k)\), then multiplying \(V_k\) by \(t\) means left-shifting by one bit. So the polynomial recurrence becomes the integer recurrence

$u_{k+1}=v_k,\qquad v_{k+1}=(2v_k)\oplus u_k,$

with initial values

$(u_0,v_0)=(0,3).$

The first few pairs are

$(0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\dots$

Every valid pair with \(u\le v\) appears exactly once in this sequence. The same degree argument also explains why the sequence grows quickly: if \(\deg v_k=d\), then \(\deg u_k=d-1\), so the new highest term in \(2v_k\) survives the XOR and \(\deg v_{k+1}=d+1\). Thus the second coordinate gains one binary digit at each step.

Worked Example

Take \(n=10\). Starting from the base pair, the recurrence gives

$(0,3)\to(3,6)\to(6,15).$

The third second-coordinate already exceeds \(10\), so the only relevant solutions are

$(0,3)\quad\text{and}\quad(3,6).$

Therefore

$X(10)=3\oplus 6=5.$

This small case matches the built-in checkpoint used by the implementations and illustrates the whole method: generate the orbit, stop at the bound, XOR the second coordinates.

How the Code Works

The C++, Python, and Java implementations all use the same compact loop. They store the current solution pair, maintain a running XOR accumulator, and repeatedly apply

$ (u,v)\mapsto \bigl(v,(2v)\oplus u\bigr). $

Whenever the current second coordinate satisfies \(v\le n\), it is folded into the accumulator. As soon as the next second coordinate exceeds the bound, the loop stops and the accumulator is returned.

This is correct because the mathematical argument above proves both directions: the recurrence never leaves the solution set, and every admissible solution belongs to that same orbit. One implementation also performs a tiny brute-force check on small bounds, but the real computation for the Euler input uses only the recurrence.

Complexity Analysis

Each iteration performs constant work: one left shift, one XOR to create the next solution, one XOR into the answer, and one comparison with the bound. Since the second coordinate gains one bit per step, the number of iterations up to \(n\) is \(O(\log n)\). The memory usage is \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=877
2. Carry-less product: Wikipedia - Carry-less product
3. Exclusive OR: Wikipedia - Exclusive OR
4. Polynomial ring: Wikipedia - Polynomial ring
5. Recurrence relation: Wikipedia - Recurrence relation