回文素数の出力（Haskellのほぼワンライナー実装）

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

はじめに

本稿は、「回文素数（palindromic prime）」を出力する処理を、Haskellを使ってワンライナーで実装するネタ的¹なShortエントリーです。

回文素数とは

『回文数』とは、上から読んでも下から読んでも同じ数字のことを言います。その中で素数のものを『回文素数』と呼びます。なお、回文素数が無数に存在するかどうかは未解決問題です。現在見つかっている最大の回文素数は最近でも更新されており、Top20を紹介しているサイトのPalindromeのページに掲載されております。2024年1月に更新された数は、$2000007$ 桁の素数

$10^{2000007} - 10^{1127194} - 10^{872812} - 1 $

だそうです。また、ベルフェゴール素数（Belphegor's prime）

$1000000000000066600000000000001$ $(= 10^{30} + 666 × 10^{14} + 1)$

という特別な名称をもつ少し悪魔っぽい回文素数もあります。

回文素数を生成する

素数列を生成する

さて、テーマとしては素数を扱いますので、Haskellで素数列の生成をワンライナーで生成します。GHCiのプロンプトから対話形式で試していきましょう。

ghci> p=2:3:5:5#p;m#(a:b:x)=[n|n<-[a^2..b^2-2],(mod (n+1) 6)*(mod (n-1) 6)==0,gcd n m<2]++(m*b)#(b:x)

回文素数を出力する

pが素数列ですのでpを使って、その中から回文素数の条件をもつものを次のようにfilter関数を使ってリストppを記述します。

ghci> pp = filter (((==) <*> reverse) . show) p

回文素数列ppは、次のようにすればインタラクティブに表示できます。

ghci> pp
[2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,...,98689,...

遅延評価で次々と表示されますので、適当なところで、Ctrl-Cで処理を止めましょう。また、$98689$ 以下の範囲で出力するには、次のように指定すると良いでしょう。

ghci> takeWhile (98689>=) pp
[2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689]

ここで $98689$ 以下を指定していますが、５桁の最大の回文素数をあらかじめ知っているから具体的に指定できております。ここを(100000>)と指定すれば、５桁の回文素数の最大値を知らなくても動作します。この実装では、$100000$ を超えた値が確定すると処理が終了します。しかし、$11$以降の偶数桁の回文素数は存在しないためさらに１桁多い７桁の回文素数まで処理が進まないと、プロセスが終了しません。この点は注意する必要があります。

おわりに

ご一読いただきまして有り難うございます。

最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に動作が異なる場合などは、参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。
macOS: Sonoma 14.4 (chip: Apple M1)
GHCup: 0.1.22.0
GHC: 9.6.4

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

1. 「ネタ的」とは、多くの方にほとんど役には立たないであろうという意図です。 ↩