1223は素数だけど20161223は素数じゃなかった～素数秒の提案～
この記事はkmc-id tetsu(id:tetsutalow)によるKMC Advent Calender 2016の23日目の記事です。
www.adventar.org
昨日はkmc-id base64(id:basemusi)さんの記事「いい感じのメドレーを自動生成したい」でした。素晴らしい。きっと自作で特定のアニメの主題歌挿入歌などなどメドレー、なんてのを気軽に作ってカラオケとかできますね。
ごあいさつ
あらためましてこんにちは、京大マイコンクラブ(KMC)部員のtetsuです。KMC的には10期生です。30回生です*1。OBではないのかと思われるかもしれませんが、今でも部費を払い続けているので*2身分は部員なのです*3。京大で教員してた頃は顧問をしていた気がしますが、今は京大を離れたのでまたヒラ部員をしています。ヒラ部員らしく、たまにはAdvent Calendarにも参加してみようかなと思い立ってエントリを立てた次第です。
そのKMC Advent Calender 2016もあと残すところ3日、これまで他の部員たちによる楽しいエントリが並んでおり、とても役に立ったり勉強になったりするものも少なくないのですが、私は全く役にも立たず毒にも薬にもならないエントリで参加しようと思います。よろしくお願いします。
今年の素数と素数日あれこれ
年も押し迫ってテレビ等で10大ニュースなども流れるようになりましたが、今年初めの大きなニュースといえばなんといっても、現時点で最大のメルセンヌ素数が見つかったことでしょう。新聞などでも数学に関する記事にしては大きく取り上げられましたね。
本当は発見されたのは去年の9月だったんですけどね。
それに比べれば小さなニュースですが、今年は北米での素数蝉（17年ゼミ）の大発生*4も話題になりましたね。
米国のセミはちゃんと数学がわかるようで羨ましいですね。日本のセミは個別には7年とか地中にいるようですが、我々にとっては毎年鳴くので節操がなく思えます。それとももしかして、日本のセミは1を素数に復活させよと主張しているのでしょうか。
さて、素数愛好家界隈でメジャーな遊びに「素数日」を探したり愛でたりすることがありますよね。素数日の定義は本来いろいろ考えられますが、最も一般的な定義は西暦表記の年月日を8桁の数字で表したときに素数になる日のことを言うようです。例えば今日の日付である1223は素数ですが、これを素数日と呼ぶ人はあまりいないんじゃないでしょうか。一方20161223は残念ながら素数日ではないのですね。思わずテンション下がりますね。
そもそも2015年は例年になく素数日が少なく、13日しかありませんでした。その余波か、今年のはじめ頃には2ヶ月ほど素数日がないという日々を過ごさねばなりませんでした。そして、12月にも素数日がないのですよね。まとめると2016年の素数日はこんな感じでした。
2016年は19日と、年あたりの素数日としては平均的日数が確保できた年でした（しかも19も素数）が、1月2月12月になると素数日がなくなるという、寒さと素数欠乏症のダブルパンチに耐えねばならない年でした。しかし、双子素数日(ここでは単純に2つの素数日が双子素数を構成している日と定義します)が2組もあって、それに救われた感があります。ついでに双子素数日を探すプログラムをJavaScriptで書いておきましたので、おいておきますね。
では来年はどうでしょうか。2017年、6年ぶりの素数年には、今年と同じく19日の素数日があります。
20170121
20170219
20170223
20170301
20170303
20170331
20170421
20170511
20170519
20170607
20170627
20170807
20170831
20170901
20170903
20171017
20171101
20171201
20171219
来年も双子素数日が2組ありますね…それに加えて、来年8月末から9月頭にかけて、なんと2日続けて素数日という日があるではないですか。これは2002年5～6月以来、実に15年ぶりの出来事です。連続素数日を探すプログラムも置いておきますね。
そういえば2016年は素数年ではありませんが4で割り切れる年ですから、夏季オリンピックの年でしたね。次の2020年の東京オリンピックパラリンピックを楽しみにしている方も多いと思いますが、2020年は素数日にとっても記念すべき年です。
20200109
20200111
20200121
20200123
20200223
20200309
20200429
20200511
20200529
20200613
20200619
20200703
20200711
20200721
20200723
20200729
20200801
20200813
20200903
20201021
20201029
20201101
20201113
20201227
20201231
20210101
特別に2021年元旦まで加えておきました。御覧のとおり2020年は「毎月素数日がある」「双子素数日が2組３組ある*5」そしてなんといっても「年またぎの連続素数日がある」という大変素数日的には充実した1年になる予定なのです。年またぎ連続素数日は1987年末以来33年ぶりの出来事であり、この次は2029年末とすぐに訪れますが、さらに次となると2161年末までない、そのころにはドラえもんが生まれてる*6というほどの珍事です。さらにその次は2383年末なので、それまでに我々はガミラス*7とクリンゴン*8と奇居子*9を迎え撃たねばなりません。話が脱線しましたが、このように2020年は特別な年なので、とても楽しみになってきましたね。
素数不足解消のための素数秒の提案
しかし、いくら素数日を愛でていても少し物足りなくなることはないでしょうか。素数は無限にあるのに、なぜ月に1～2度あるかないかの素数日をこんなに待ち焦がれないといけないのでしょうか。そこでそんな素数不足を解消したい人のために、新たな概念を持ち込みましょう。それは「素数秒」です。
素数秒はここでは、年月日時分秒を14桁の数字で表した時に素数となるものとします*10。例えば2016年12月23日0時0分53秒を20161223000053とすると素数になりますので、これが素数秒です。ちなみにこれが本日最初の素数秒ということになります。2017年最初の素数秒は元旦の0時0分1秒、つまり20170101000001です。ちなみにこの日はIT業界の敵、うるう秒がありますね（日本時間で8時59分60秒）。素数秒は幸い、うるう秒対応する必要がありません（うるう秒は必ず非素数秒です）。
この素数秒、1日にどれくらいあるでしょうか。ちょっとプログラムを書いてみました。
素数秒を探す（試し割り版）
…遅い！さすがに14桁は8桁とはわけが違います。私の環境*11では30秒くらいかかりました。しかしその甲斐あって、本日12月23日は素数秒が2871回あることが分かりました。平均的には30秒に1回程度、我々は素数秒を楽しめることになります。
しかし遅いですね。残念ながらこのプログラム、単純に各素数秒候補を素数で試し割りしてるだけ（まで列挙なら
）なので、計算量的にはエラトステネスの篩（
まで列挙なら
）のほうが有利のはず。実際には区間で求めてるので単純じゃないしどうかなと思いながら、区間エラトステネスのふるい（ナイーブな方法）でも実装してみました。
…せいぜい倍にしかなりませんね。エラトステネスのふるいの速度は計算量もありますが、コアのループの計算の単純さでも効いてくるので、60秒の区間ずつふるうのではあまり速度効果が出ないのでしょう。実はこの後、John Moyerに倣って11や13以下の素数でふるった後のビット列を使ってやれば少しは速くなるかなと試していたのですが、やはりJavaScriptでは複雑さが効くのか大して高速化できない上に、途中でOrionHubのバグを踏んでしまったらしくソースコードをゴミデータで上書きされてしまいメゲたので、これはもうここまでにしておきます*12。
さて、この素数秒を愛でるにはどうすればいいでしょう。まさか時計と素数秒の表を見比べながら次の素数秒を今か今かと待ちわびる、というのはバカバカしいので、こんな時計を作ってみました。名付けて「素数秒時計」です。
…デザインセンスがない点についてはご容赦下さい。機能としては、現在の時刻と共に、次に訪れる素数秒を表示します。素数秒ではない現在時刻については、その非素数秒を素因数分解したものを下に表示するようにしてみました。こうすることにより、素数秒以外の各秒でも、さまざまな素数との出会いが目を愉しませてくれます。これで素数欠乏症も怖くありません。きっと舘ひろしさんも喜んでくれると思います。
この素数秒時計をデスクトップに表示してじっと眺めていると、あたかも素数階段を一歩一歩登るような喜びが味わえます。平均的には30秒に1度とはいえ、やはり素数らしくその間隔には不思議なばらつきがあります。不意に訪れる、次の素数秒との長い空白を息を潜めて待つも良いですし、突然目に入る「双子素数秒」との出会いも楽しいものです。皆さんもぜひこの「素数秒時計」で、充実の素数ライフを！！
さて、明日はいよいよクリスマスイブ。KMC Advent Calender 2016の明日の担当は、kmc-id hakurin(id:hakurin070706)さんです。明後日のKMCお絵かき Advent Calendar 2016ともども、頑張ってください！
*1:つまりKMCは来年40周年を迎えます。
*2:現時点でKMCの歴史の75%の期間部費を払っています。その間、部費の値上げはなんと1度しかありませんでした。
*3:KMCは入部に際し所属身分年齢性別国籍宗教その他何の制限もありません。実際、最近はネット部員的な人も増えてきています。まだ人類以外が入部申請してきたことはないようですが、規約上は宇宙人でも大丈夫だと思いますので、個人的には、ツノがあってトラジマビキニを着ていて空を飛べる女性の入部をお待ちしています。
*4:実はWikipediaをよく読むと今年の年次集団はそれほど大きくない群らしいです。ニュースを見かけたので書いちゃいましたがよく調べるべきでしたね。
*5:最初見落としてましたAKさんありがとう
*6:ドラえもんは2112年9月3日生まれ。この日は素数日ではありません。
*7:ガミラスは2192年来襲、2199年には地球防衛軍が敗北しヤマトがイスカンダルへ向かう予定です。
*8:U.S.S.エンタープライズ就航は2245年ですが、2293年にはクリンゴン帝国とキトマー条約を締結します。2383年はボーグとの戦いの最中ですね。
*9:奇居子の地球侵攻は2371年。
*10:コンピュータ屋としてはUNIX timeで定義することもちょっと頭を過ったのですが、2進法の美しさと素数の美しさはベクトルが違うように感じたので止めました。
*11:VAIO S11(Core i5-6200U 2.3GHz)にWindows 10 64bitとChromeバージョン 55.0.2883.87 m (64-bit)
*12:ようやく、Advent Callendarのお題の「KMC」らしい話題になりました。
