Wolstenholme Prime の探索

$10^9 < p < 2 \cdot 10^{9}$ の範囲について、Wolstenholme Prime を探す。

Wolstenholme Prime

Wolstenholme Prime とは、
$$
\binom{2p-1}{p-1} \equiv 1 \pmod{p^4}
$$
を満たす素数のことである。現在、報告されている限りでは、$2 \le p < 10^9$ の範囲まで探索が完了しており、$16843$, $2124679$ の 2 つのみが発見されている。

(論文 pdf: A search for Fibonacci-Wieferich and Wolstenholme primes

探索方法と探索時間

前記事の判定式
$$
\sum_{p/6 < i < p/4} \frac{1}{i^3} \equiv 0 \pmod{p}
$$
を用いる。実装をしたところ、$p < 2^{30}$ については 0.055 秒程度、$p < 2^{31}$ については 0.110 秒程度で Wolstenholme 素数判定を行うことができた。よって、$10^9 < p < 2 \cdot 10^{9}$ の範囲で判定を行うと、$5 \cdot 10^6$ 秒程度必要となり、これは 72 コアで分散すると 19.5 時間程になる。

なお、次で定義する $c_{p}$ が $0 \le c_p < p$ で一様に分布するという仮定の元では、$10^9 < p < 2 \cdot 10^{9}$ の範囲に存在する Wolstenholme Prime の個数の期待値は 0.03 個ほどでしかない。

探索結果

Wolstenholme Prime は $10^9 < p < 2 \cdot 10^9$ の範囲に存在しない。

$ c_{p} := [x] \prod\limits_{p/6 < i < p/4} (x + i^3) \pmod{p} $ [ここでの mod は剰余の意味] と定義すると、$p \ge 11$ では $c_p = 0$ を満たす $p$ が Wolstenholme Prime となるが、そのような $p$ は存在しなかった。

$c_p < 1000$ となるような $10^9 < p < 2 \cdot 10^{9}$ としては以下のものがあった。

$p$ $c_p$
$1020492353$ $732$
$1050502561$ $454$
$1053243911$ $604$
$1062419179$ $722$
$1072515181$ $187$
$1089787877$ $99$
$1097943281$ $644$
$1119013061$ $417$
$1143919109$ $283$
$1233376043$ $384$
$1246457479$ $73$
$1282249217$ $682$
$1306090453$ $332$
$1349383549$ $797$
$1367979161$ $303$
$1390154221$ $971$
$1446687937$ $339$
$1486822913$ $974$
$1516888027$ $799$
$1574573563$ $339$
$1585053389$ $872$
$1590983567$ $477$
$1622875871$ $480$
$1661177107$ $143$
$1698462973$ $206$
$1715173583$ $97$
$1738139191$ $41$
$1739094887$ $660$
$1808304521$ $294$
$1872906487$ $985$
$1911075059$ $896$

より高速な探索法

Wilson Prime の探索で使われた方法(多倍長 + remainder tree) (論文 pdf: A Search for Wilson prime) のように、多数の素数について同時に判定し、ならし計算量を抑える方法を取ると、$1 < p \le n$ の範囲の判定にかかる計算量を $O(n^{3/2})$ 未満に改善できるのかもしれない。