---

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{array}{r}\phantom{\otimes 111}{111}_2\\ \otimes \phantom{1111}{11}_2\\ \phantom{\otimes 111}{111}_2\\ \oplus \phantom{11}{111}_2\phantom{9}\\ \phantom{\otimes 11}{1001}_2\end{array}$$

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,\dots$ and the $10$th XOR-prime is $41$.

Find the $5000000$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{array}{r}\phantom{\otimes 111}{111}_2\\ \otimes \phantom{1111}{11}_2\\ \phantom{\otimes 111}{111}_2\\ \oplus \phantom{11}{111}_2\phantom{9}\\ \phantom{\otimes 11}{1001}_2\end{array}$$

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

求第$5000000$个异或质数。

---