Detailed mathematical approach

Problem Summary

We seek the \(N\)-th XOR-prime among the integers below \(2^M\). The key reinterpretation is that an integer is not viewed with ordinary arithmetic, but as a polynomial over \(\mathbb F_2\): if

$n=\sum_{k\ge0} b_k2^k,\qquad b_k\in\{0,1\},$

then it represents

$P_n(x)=\sum_{k\ge0} b_kx^k\in\mathbb F_2[x].$

An XOR-prime is therefore an integer whose associated polynomial is irreducible in \(\mathbb F_2[x]\). The implementations enumerate these objects in increasing integer order. The special even value \(2\), corresponding to the polynomial \(x\), is counted first; after that, every remaining XOR-prime is odd.

Mathematical Approach

The solution is a sieve in the polynomial ring \(\mathbb F_2[x]\). Instead of ordinary multiplication with carries, it works with carryless multiplication, which matches polynomial multiplication with coefficients reduced modulo \(2\).

Step 1: Encode Integers as Binary Polynomials

The map

$n\longleftrightarrow P_n(x)=\sum_{k\ge0} b_kx^k$

turns the binary digits of \(n\) into polynomial coefficients. Under this encoding, bitwise XOR is simply polynomial addition in \(\mathbb F_2[x]\). If \(a\leftrightarrow A(x)\) and \(b\leftrightarrow B(x)\), then the XOR-product is

$A(x)B(x)=\sum_{t\ge0} c_tx^t,\qquad c_t=\bigoplus_{i+j=t}(a_i\land b_j).$

So a number is XOR-composite precisely when its polynomial factors nontrivially over \(\mathbb F_2\).

Step 2: Isolate the Special Even Case

If \(n\) is even, then its least significant bit is \(0\), so the constant term of \(P_n(x)\) is \(0\). That means

$P_n(x)=xQ(x)$

for some polynomial \(Q(x)\). Therefore every even code larger than \(2\) is automatically XOR-composite. The only even XOR-prime is

$2\leftrightarrow x,$

which is irreducible because it has degree \(1\). This explains why the implementations count \(2\) immediately and then sieve only odd integers.

Step 3: Turn Reducibility into a Sieve

Let \(p\) be an odd XOR-prime, and let its binary length be \(\ell\). Then the associated polynomial has degree

$\deg P_p=\ell-1.$

Any odd XOR-composite that has \(p\) as a factor can be written as

$P_n(x)=P_p(x)\,Q(x),$

where \(Q(x)\) is another nonconstant polynomial with constant term \(1\). If \(Q\) has degree \(j\), then

$\deg P_n=(\ell-1)+j.$

Since the search is restricted to integers below \(2^M\), we need

$\deg P_n\le M-1,$

so the admissible cofactor degrees satisfy

$j\le M-\ell.$

The sieve marks every such product. Whatever odd code survives all these marking passes must be irreducible.

Step 4: Enumerate All Monic Cofactors of a Fixed Degree

Fix a cofactor degree \(j\). Every monic polynomial of degree \(j\) has code

$2^j\oplus t,\qquad 0\le t\lt 2^j,$

because the top bit must be \(1\) and the lower \(j\) coefficients are free. So for one base polynomial \(p\), the values that must be marked are

$p\otimes(2^j\oplus t),$

with \(\otimes\) denoting carryless multiplication. There are exactly \(2^j\) such cofactors for this degree, and the implementations enumerate all of them.

Step 5: Why the Lowbit Update Generates the Next Product Cheaply

Recomputing every carryless product from scratch would be too slow. Instead, the implementations traverse the lower part \(t\) in Gray-code order. Starting from \(g_0=0\), define

$g_n=g_{n-1}\oplus \operatorname{lowbit}(n),$

where \(\operatorname{lowbit}(n)\) is the least significant set bit of \(n\). This visits every value in \([0,2^j)\) exactly once, and consecutive values differ in only one bit. If the current cofactor changes by one bit \(2^r\), then the product changes by

$p\otimes 2^r,$

which is just a left shift of \(p\), because \(2^r\) represents the monomial \(x^r\). So each next marked value is obtained from the previous one with a single XOR against one shifted copy of the base code.

Step 6: Why the Degree Range Starts at \(\ell-1\)

The sieve only needs cofactor degrees

$j\ge \ell-1.$

This is the polynomial analogue of starting the ordinary sieve of Eratosthenes at \(p^2\). If \(P_n=P_pQ\) with \(\deg Q\lt \deg P_p\), then \(Q\) has some irreducible factor of smaller degree than \(P_p\), so \(n\) will already be marked when that smaller-degree factor is processed. Beginning at equal degree therefore removes unnecessary work without losing any composite numbers.

Worked Example

The first few XOR-primes illustrate the idea:

$2\leftrightarrow x,\qquad 3\leftrightarrow x+1,\qquad 7\leftrightarrow x^2+x+1.$

Nearby odd integers can be XOR-composite for purely polynomial reasons. For example,

$5\leftrightarrow x^2+1=(x+1)^2,$

$9\leftrightarrow x^3+1=(x+1)(x^2+x+1).$

So \(5\) and \(9\) are removed by the sieve, while \(7\) survives. Listing all survivors in increasing order begins

$2,\,3,\,7,\,11,\,13,\,19,\,25,\,31,\,37,\,41,\dots$

Hence the \(10\)-th XOR-prime is \(41\), which is the small checkpoint matched by the implementations.

How the Code Works

The C++, Python, and Java implementations allocate a mark table for all integers below \(2^M\) and initially treat every entry as a possible XOR-prime. They count \(2\) first, then scan only odd codes in increasing order. Whenever an odd code is still unmarked, the implementation has found the next XOR-prime and advances the running rank.

For each such survivor, the implementation computes its bit length, which gives the degree of the corresponding polynomial. It then loops over all admissible cofactor degrees \(j\). For each \(j\), it starts from the product with \(x^j\), which is just a left shift, and then walks through all monic degree-\(j\) cofactors in Gray-code order. Every generated product is marked as XOR-composite.

The crucial optimization is that consecutive cofactors differ by exactly one lower bit, so the next product is derived from the previous product with one XOR against a shifted copy of the base polynomial. The search stops immediately once the requested rank \(N\) has been reached.

Complexity Analysis

The mark table has size \(2^M\), so memory usage is \(O(2^M)\). The outer scan over odd integers is also \(O(2^M)\). For a surviving XOR-prime of degree \(d\), the marking work is

$\sum_{j=d}^{M-d-1} 2^j = 2^{M-d}-2^d.$

A simple worst-case summary is therefore \(O(M2^M)\) time. In practice the constant factors are low, because the inner loop consists only of bit operations, and only surviving XOR-primes generate marking passes.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=810
2. Finite fields and \(\mathbb F_2\): Wikipedia — Finite field
3. Irreducible polynomials: Wikipedia — Irreducible polynomial
4. Carryless multiplication: Wikipedia — Carry-less product
5. Gray code: Wikipedia — Gray code