こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

は、人名がついた「●●素数（●●は人の名前）」という素数をこれまでも紹介してきました。¹²³⁴その第５弾として、本稿では「プロス素数」と「ピアポイント素数」をご紹介します。

このあとプログラムでそれぞれの素数の列を求める例を示しますが、その前に事前準備として確率的素数を判定する関数を定義しておきます。

確率的素数を判定する関数：probably_prime

ghci> exp_mod a n = iter a (n-1) n where iter a n base | n == 1 = a | even n = (iter a (n `div` 2) base) ^ 2 `mod` base | otherwise = a * (iter a ((n-1) `div` 2) base) ^ 2 `mod` base
ghci> probably_prime n = and $ map (\a -> test n a) $ takeWhile (<n) [2,3,5,7,11,13,17,19] where test n a | gcd n a == 1 = (1 == exp_mod a n) | otherwise = False

プロス素数とピアポイント素数

それぞれの素数の定義は以下のとおりです。

プロス素数の定義

$k\cdot2^{n}+1$（$n$：正の整数、$k$：$2^{n}>k$を満たす正の奇数）で表される素数

ピアポイント素数の定義

$3^{m}\cdot2^{n}+1$（$m,n$：非負の整数）で表される素数

プロス素数

プロス数（Proth number）は、19世紀フランスの数学者フランソワ・プロスにちなんで名付けられた数で、$k\cdot2^{n}+1$（$n$：正の整数、$k$：$2^{n}>k$を満たす正の奇数）で表される数です。このプロス数でかつ素数である数をプロス素数⁵と呼びます。プロス素数は無数にあると予想されていますが未解決問題です。またプロス素数の形式は、次のような名前の付いた素数を含んでいます。

• カレン素数： $n \times 2^n + 1$
• サービト素数： $ 3 \times 2^{n}+1$
• フェルマー素数： $2^{2^{n}}+1$

プロス素数を出力するプログラムを紹介します。折角なので、正の整数$n$と$2^{n}>k$を満たす正の奇数$k$もタプルで出力するようにします。

ghci> import Data.List (sortBy)
ghci> import Data.Function (on)
ghci> proth=[(k,n,p)|  n<-[1..], k<-[1,3..2^n-1], let p=k*2^n+1, probably_prime p]
ghci> sortBy (compare `on` (\(a,b,c)->c)) ( take 100 proth )
[(1,1,3),(1,2,5),(3,2,13),(1,4,17),(5,3,41),(3,5,97),(7,4,113),
(3,6,193),(15,4,241),(1,8,257),(11,5,353),(7,6,449),(9,6,577),
(5,7,641),(21,5,673),(3,8,769),(29,5,929),(9,7,1153),(19,6,1217),
(11,7,1409),(25,6,1601),(33,6,2113),(21,7,2689),(43,6,2753),
(49,6,3137),(13,8,3329),(27,7,3457),(35,7,4481),(39,7,4993),
(51,7,6529),(57,7,7297),(15,9,7681),(31,8,7937),(37,8,9473),
(75,7,9601),(77,7,9857),(81,7,10369),(21,9,10753),(89,7,11393),
(23,9,11777),(95,7,12161),(105,7,13441),(107,7,13697),
(55,8,14081),(57,8,14593),(119,7,15233),(125,7,16001),
(35,9,17921),(87,8,22273),(45,9,23041),(91,8,23297),(51,9,26113),
(105,8,26881),(121,8,30977),(123,8,31489),(63,9,32257),
(141,8,36097),(71,9,36353),(147,8,37633),(157,8,40193),
(163,8,41729),(171,8,43777),(89,9,45569),(181,8,46337),
(193,8,49409),(195,8,49921),(101,9,51713),(223,8,57089),
(225,8,57601),(235,8,60161),(131,9,67073),(149,9,76289),
(159,9,81409),(165,9,84481),(171,9,87553),(189,9,96769),
(201,9,102913),(219,9,112129),(221,9,113153),(225,9,115201),
(231,9,118273),(233,9,119297),(245,9,125441),(261,9,133633),
(281,9,143873),(299,9,153089),(303,9,155137),(309,9,158209),
(311,9,159233),(315,9,161281),(329,9,168449),(333,9,170497),
(345,9,176641),(359,9,183809),(413,9,211457),(423,9,216577),
(429,9,219649),(431,9,220673),(443,9,226817),(455,9,232961)]

（注意）この処理は小さい順に並ぶとは限りません。何故なら、nを小さい方から計算する処理となっており、take 100 prothと配列の最初の100個をとったとしてもn=9あたりまでのリストが計算されますが、$3\times2^{12}=12289$(3,12,12289)や$13\times2^{10}=13313$(13,10,13313)は5桁のプロス素数にも関わらず、計算の順番では少しあとに計算されるため、飛ばされて上の結果には含まれなくなってしまっています。

プロスの定理

プロス数が素数であるか否かの判定を行うことができる「プロスの定理」という素数判定方法があります。

プロスの定理

プロス数が素数であるかの判定をする方法で$p$をプロス数としたとき、

$\displaystyle a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

を満たす$a$があれば、$p$は素数である。

この素数判定は比較的高速に計算できるとされております。

ピアポイント素数

ピアポイント素数、またはピアポン素数（Pierpont prime）は、数学者のジェームズ・ピアポントにちなんで名付けられた素数です。$2^{n}\gt 3^{m}$の場合は、プロス素数でもあります。

ピアポイント素数を出力するプログラムを紹介します。

ghci> pierpont x =[(m,n,p)|let u=floor(logBase 3 x), let v=floor(logBase 2 x), m<-[0..u], n<-[0..v], let p=3^m*2^n+1, p<x, probably_prime p]
ghci> sortBy (compare `on` (\(a,b,c)->c)) $ pierpont 1000000
[(0,0,2),(0,1,3),(0,2,5),(1,1,7),(1,2,13),(0,4,17),(2,1,19),
(2,2,37),(2,3,73),(1,5,97),(3,2,109),(4,1,163),(1,6,193),
(0,8,257),(3,4,433),(5,1,487),(2,6,577),(1,8,769),(2,7,1153),
(4,4,1297),(6,1,1459),(4,5,2593),(6,2,2917),(3,7,3457),
(5,4,3889),(4,7,10369),(1,12,12289),(7,3,17497),(2,11,18433),
(9,1,39367),(8,3,52489),(0,16,65537),(7,6,139969),(2,14,147457),
(8,5,209953),(4,12,331777),(10,3,472393),(9,5,629857),
(6,10,746497),(1,18,786433),(8,7,839809),(5,12,995329)]

ギルブレス予想

数学者フランソワ・プロスに関しては、未解決問題に対してもう一つのエピソードがあります。
素数を小さい順に並べ、隣り合う２数の差の絶対値をその下に書くことを繰り返します。すると、左端に1が並びます。これが何段繰り返しても成立するというのが ギルブレス（Gilbreath）予想 ⁶です。数式で表すと次のようになります。

ギルブレスの予想

$d_{n}^{1}$を$n$番目の素数と$n+1$番目の素数の差とします． $d_{n}^{k+1}=|d_{n+1}^{k}-d_{n}^{k}|$としたとき，すべての$k$に対して$d_{1}^{k}=1$となる．

フランソワ・プロスは、このギルブレスの予想を証明したと発表したが、誤りであることが判明しています。なお、2017年には、$3.4×10^{11}$段目までは正しいことが計算で確かめられています。

おわりに

ご一読いただきまして有り難うございます。
最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

• macOS: Sonoma 14.4 (chip: Apple M1)
• GHCup: 0.1.22.0 GHC: 9.6.4

（●）（●） Happy Hacking!
/""　＿＿""＼

1. ウォルステンホルム素数 ↩

2. カレン素数とウッダル素数 ↩

3. ヴィーフェリッヒ素数 ↩

4. キネア素数とキャロル素数 ↩

5. プロス素数の参考サイト： https://googology.fandom.com/ja/wiki/%E3%83%97%E3%83%AD%E3%82%B9%E7%B4%A0%E6%95%B0 ↩

6. ギルブレス予想の参考サイト：https://fibonacci-freak.hatenablog.com/entry/2017/08/31/222850 ↩