3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-04-14

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

はじめに

本稿は、「回文素数(palindromic prime)」を出力する処理を、Haskellを使ってワンライナーで実装するネタ的1な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$ 以下を指定していますが、5桁の最大の回文素数をあらかじめ知っているから具体的に指定できております。ここを(100000>)と指定すれば、5桁の回文素数の最大値を知らなくても動作します。この実装では、$100000$ を超えた値が確定すると処理が終了します。しかし、$11$以降の偶数桁の回文素数は存在しないためさらに1桁多い7桁の回文素数まで処理が進まないと、プロセスが終了しません。この点は注意する必要があります。

おわりに

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

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

本稿の環境

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

(●)(●) Happy Hacking!
/"" __""\

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

3
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?