Solution

Answer: 336785000760344621

Interpret every nonnegative integer as a polynomial over $\mathbb F_2$ by reading its binary expansion as coefficients.

For example

$$13 = 1101_2 \longleftrightarrow x^3+x^2+1.$$

Under this correspondence:

XOR becomes polynomial addition over $\mathbb F_2$,
the XOR-product $\otimes$ becomes ordinary polynomial multiplication over $\mathbb F_2$.

So the problem is really taking place inside $\mathbb F_2[x]$.

1. Rewriting the equation

Let

$$A(x)\leftrightarrow a,\qquad B(x)\leftrightarrow b.$$

The equation

$$(a\otimes a)\oplus (2\otimes a\otimes b)\oplus (b\otimes b)=5$$

becomes

$$A^2+xAB+B^2=x^2+1.$$

(Here the integer $2$ corresponds to the polynomial $x$, and $5=101_2$ corresponds to $x^2+1$.)

Thus we must solve

$$A^2+xAB+B^2=x^2+1. \tag{1}$$

2. Introducing a quadratic extension

Let $u$ satisfy

$$u^2+xu+1=0.$$

Then define the conjugate

$$\bar u = x+u.$$

Indeed,

$$u+\bar u=x,\qquad u\bar u=1.$$

Now consider

$$z=A+Bu.$$

Its norm is

$$N(z)=z\bar z=(A+Bu)(A+B\bar u).$$

Expanding in characteristic $2$,

$$N(z)=A^2+xAB+B^2.$$

Therefore equation (1) is exactly

$$N(z)=x^2+1=(x+1)^2. \tag{2}$$

3. Generating all solutions

Because

$$N(u)=u\bar u=1,$$

multiplying any solution by powers of $u$ preserves the norm.

A basic solution is

$$(A,B)=(0,x+1),$$

because

$$0^2+0+(x+1)^2=x^2+1.$$

In integers this is $(a,b)=(0,3)$.

Now multiply repeatedly by $u$.

Suppose

$$A_n+B_nu=(x+1)u^n.$$

Then

$$(A_{n+1},B_{n+1})$$

comes from multiplying by $u$:

$$(A_n+B_nu)u = B_n + (A_n+xB_n)u.$$

Hence

$$A_{n+1}=B_n, \qquad B_{n+1}=A_n+xB_n.$$

Translating back to integers:

multiplication by $x$ is left shift by one bit,
addition is XOR.

Therefore

$$a_{n+1}=b_n, \qquad b_{n+1}=a_n\oplus (2b_n). \tag{3}$$

Starting from

$$(a_0,b_0)=(0,3),$$

we obtain

$$\begin{aligned} (0,3),\ (3,6),\ (6,15),\ (15,24),\ (24,63),\ldots \end{aligned}$$

exactly matching the example.

One can show from unique factorization in this quadratic extension that all solutions arise this way.

Thus $X(N)$ is simply the XOR of all $b_n\le N$.

4. Efficient computation

The recurrence is:

$$(a,b)\mapsto (b,\ a\oplus (b\ll 1)).$$

There are only about $60$ terms below $10^{18}$, so direct iteration is trivial.

5. Python implementation

def compute_X(N):
    # Initial solution
    a, b = 0, 3

    ans = 0

    while b <= N:
        ans ^= b

        # Next solution:
        # a' = b
        # b' = a XOR (b << 1)
        a, b = b, a ^ (b << 1)

    return ans

# Verification of the small example
print(compute_X(10))      # should be 5

# Final answer
print(compute_X(10**18))

6. Code walkthrough

a, b = 0, 3

Starts from the fundamental solution.

while b <= N:

Iterate through every valid solution with $b\le N$.

ans ^= b

The problem asks for XOR of all $b$-values.

a, b = b, a ^ (b << 1)

Implements recurrence (3):

$$a_{n+1}=b_n, \qquad b_{n+1}=a_n\oplus(2b_n).$$

Left shift is multiplication by $x$.

7. Verification on the sample

Solutions with $b\le 10$:

$$(0,3),\quad (3,6).$$

Hence

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

matching the statement.

8. Final computation

Running the program for

$$N=10^{18}$$

gives

$$336785000760344621.$$

The value is plausible:

only $58$ solutions occur below $10^{18}$,
XOR stays below $2^{60}$, consistent with magnitude.

Answer: 336785000760344621

Project Euler Problem 877