Project Euler Problem 878

Solution

Answer: 23707109

Let

$$Q(a,b)=(a\otimes a)\oplus(2\otimes a\otimes b)\oplus(b\otimes b).$$

The XOR-product is exactly polynomial multiplication over $\mathbb F_2$:

$$a=\sum a_i2^i,\qquad b=\sum b_i2^i,$$

identify them with polynomials

$$A(x)=\sum a_ix^i,\qquad B(x)=\sum b_ix^i.$$

Then XOR-product corresponds to multiplication in $\mathbb F_2[x]$, with $x$ represented by the integer $2$.

Hence

$$Q(a,b)\leftrightarrow A^2+xAB+B^2.$$

Now define the transformation

$$T(a,b)=(b,\ a\oplus (2b)).$$

In polynomial form:

$$(A,B)\mapsto (B,\ A+xB).$$

A direct computation in $\mathbb F_2[x]$ gives

$$B^2+xB(A+xB)+(A+xB)^2 = A^2+xAB+B^2,$$

because over characteristic $2$,

$$x^2B^2+x^2B^2=0.$$

So $Q(a,b)$ is invariant under $T$.

Moreover every nonzero solution belongs to exactly one infinite orbit generated by repeatedly applying $T$, and each orbit has a unique primitive representative satisfying

$$b\oplus (2a) > a.$$

For a primitive pair with $Q(a,b)\le 10^6<2^{20}$, degree considerations imply $b<2^{11}=2048$.

So we only need to enumerate primitive pairs with $0\le a\le b<2048$.

For each primitive pair, repeatedly apply $T$ until $b>10^{17}$, counting all orbit elements.

The following Python code does exactly that.

def clmul(a, b):
    """Carryless (XOR) multiplication."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        b >>= 1
    return r

def Q(a, b):
    return clmul(a, a) ^ (clmul(a, b) << 1) ^ clmul(b, b)

def primitive(a, b):
    return (a, b) == (0, 0) or ((b ^ (2 * a)) > a)

N = 10**17
M = 1_000_000

ans = 1   # (0,0) gives k=0

for a in range(2048):
    for b in range(max(a, 1), 2048):

        if not primitive(a, b):
            continue

        if Q(a, b) > M:
            continue

        x, y = a, b

        while y <= N:
            ans += 1
            x, y = y, x ^ (2 * y)

print(ans)

Checking the sample:

G(1000,100)=398

which matches the statement.

Running the full computation gives:

$$G(10^{17},1{,}000{,}000)=23707109.$$

Answer: 23707109