ここでは $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$ である：

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

Rand48はいくつかのプログラミング言語で使われる疑似乱数生成器である。これは任意に与えられた整数$a_0$から数列を $a_n = ( 25214903917 \cdot a_{n-1} + 11 ) \bmod 2^{48}$という規則に従い生成する。

$b_n = \lfloor a_n / 2^{16} \rfloor \bmod 52$とする。数列 $b_0, b_1, \dots$ は$0 \to \textrm{a},$$1 \to \textrm{b},$$\dots,$$25 \to \textrm{z},$$26 \to \textrm{A},$$27 \to \textrm{B},$$\dots,$$51 \to \textrm{Z}$という規則を介して​無限文字列 $c=c_0c_1c_2\dots$ に変換される。

例えば、$a_0 = \textbf{123456}$と選ぶと $c$ の冒頭は "bQYicNGCY..." となる。 さらに、100文字めからの位置に "RxqLBfWzv" という部分文字列の最初の出現がある。

あるいは、$c$ の冒頭が "EULERcats..." ならば、$a_0 = 78580612777175$ に違いない。

今、$c$ が "PuzzleOne..." で始まっていると仮定する。 $c$ の部分列として最初に "LuckyText" が出現する位置を求めよ。

(原題 Reversible prime squares)

169と961はどちらも素数の平方数である。961を後ろから読むと169になる。

ここで、以下を満たす数をリバーシブル素数平方数と呼ぶことにする。

1. 回文数でない。

2. 素数の平方数である。

3. 後ろから読んだ数も、素数の平方数である。

169と961は回文数でないので、いずれもリバーシブル素数平方数である。

リバーシブル素数平方数の最初の50個の和を求めよ。