# 810：XOR素数

ここでは $$x$$ と $$y$$ のビットごとの排他的論理和(XOR)を $$x \oplus y$$ と表す。

$$x$$ と $$y$$ の**XOR積**を、基数2の積み算による乗算と同様であるが、中間結果を通常の整数の加算の代わりにXORするものと定義し、$$x \otimes y$$ と表す。

例えば、$$7 \otimes 3 = 9$$もしくは2進表記で $$111_2 \otimes 11_2 = 1001_2$$ である：

$$
\begin{align*}
\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{align*}
$$

**XOR素数**とは、1より大きい整数 $$n$$ で、1より大きい二つの整数のXOR積ではないものをいう。\
上の例は9がXOR素数でないことを示している。\
同様に、$$5 = 3 \otimes 3$$ はXOR素数でない。\
XOR素数は小さいものから順に $$2, 3, 7, 11, 13, \dots$$ で、10個めのXOR素数は41である。

$$5\,000\,000$$個めのXOR素数を答えよ。







