1 / 1

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素数を答えよ。

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*}

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