Project Euler Problem 945

Solution

Answer: 83357132

Interpret integers as polynomials over $\mathbb F_2$ (binary coefficients), where bitwise XOR is polynomial addition and the XOR-product $\otimes$ is ordinary polynomial multiplication over $\mathbb F_2$ (carryless multiplication).

Let $A(x),B(x)$ correspond to $a,b$. Then:

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

becomes

$$A(x)^2 + xA(x)B(x) + B(x)^2.$$

Since squaring in characteristic $2$ produces only even powers of $x$, $c\otimes c = C(x)^2$ contains only even-degree terms.

Thus the expression is a square iff the odd-degree coefficients vanish. The only odd-degree contribution comes from $xA(x)B(x)$, so we require:

$$A(x)B(x)$$

to contain only odd powers.

Now split into even/odd bits:

$$A(x)=A_0(x^2)+xA_1(x^2),\qquad B(x)=B_0(x^2)+xB_1(x^2).$$

The condition that $A(x)B(x)$ has no even powers becomes:

$$A_0B_0 = x^2 A_1B_1.$$

This yields a recursive decomposition across alternating bit positions (even/odd bits), reducing the problem to matching carryless products of the two half-bit parts.

For $N=10^7$, use a meet-in-the-middle over the $24$-bit range:

split numbers into even/odd bit halves (12 bits each),
precompute carryless products for all $4096^2$ half-pairs,
count compatible matches under the bound $a,b\le N$,
divide by $2$ (symmetry $a,b$) while accounting for the unique diagonal solution $(0,0)$.

A verification reproduces the given value $F(10)=21$.

Answer: 83357132