---

Problem 810

---

XOR-Primes

We use $x\oplus y$ for the bitwise XOR of $x$ and $y$.

Define the XOR-product of $x$ and $y$, denoted by $x \otimes y$, similar to a long multiplication in base $2$, except that the intermediate results are XORed instead of the usual integer addition.

For example, $7 \otimes 3 = 9$, or in base $2$, $111_2 \otimes 11_2 = 1001_2$:

$$
\begin{aligned}
\phantom{\otimes 111} 111_2 \\
\otimes \phantom{1111} 11_2 \\
\hline
\phantom{\otimes 111} 111_2 \\
\oplus \phantom{11} 111_2 \phantom{9} \\
\hline
\phantom{\otimes 11} 1001_2 \\
\end{aligned}
$$

An XOR-prime is an integer $n$ greater than $1$ that is not an XOR-product of two integers greater than $1$. The above example shows that $9$ is not an XOR-prime. Similarly, $5 = 3 \otimes 3$ is not an XOR-prime. The first few XOR-primes are $2, 3, 7, 11, 13, …$ and the $10$th XOR-prime is $41$.

Find the $5\ 000\ 000$th XOR-prime.

---

异或质数

记$x\oplus y$为$x$和$y$按位异或的结果。

我们定义一种新运算，称为$x$和$y$的异或积并记作$x \otimes y$。这种运算类似于对$x$和$y$的二进制表示做长乘法，但是将其中的相加替换为异或。

例如，$7 \otimes 3 = 9$，或用二进制表示写作$111_2 \otimes 11_2 = 1001_2$：
$$
\begin{aligned}
\phantom{\otimes 111} 111_2 \\
\otimes \phantom{1111} 11_2 \\
\hline
\phantom{\otimes 111} 111_2 \\
\oplus \phantom{11} 111_2 \phantom{9} \\
\hline
\phantom{\otimes 11} 1001_2 \\
\end{aligned}
$$

若大于$1$的整数$n$不是任意两个大于$1$的整数的异或积，则称之为异或质数。上面的例子说明$9$不是一个异或质数。类似地，$5 = 3 \otimes 3$也不是一个异或质数。较小的异或质数包括$2, 3, 7, 11, 13, …$，而第$10$个异或质数是$41$。

求第$5\ 000\ 000$个异或质数。

---