うえぽんSW局

昔ながらの日記ブログです。

カテゴリ: 雑記

 2016年も最後となってしまったので、以前のブログで書いた「素数探しの旅」がその後がどうなったか書いておこうと思います。

 まず探していた素数というのは以下のように1234567890123…と続く数列で素数となるものです。
 1
 12
 123
 1234
 12345
 123456
 1234567
 12345678
 123456789
 1234567890
 12345678901
 123456789012
 1234567890123
 :
 :

 以前の記事では以下の桁数において素数(もしくは確率的素数)となることを発見しました。
 171桁
 277桁
 367桁
 561桁
 567桁
 18881桁

 ではこれ以上の桁数で素数は存在するのだろうか?
 というわけで、あれからチマチマと素数を探し続けていました。
 そうして半年かかって21万1761桁までテストしましたが、発見できませんでした
 (もしかしたら自分がミスして見逃している可能性があるかもしれませんので、他の方の検証も欲しい所です)

 長らくチマチマと探していましたが、2016年が終わるのを目途として素数の探索はをこれにて打ち切りにしたいと思います。この挑戦はかなり無茶だったかもしれません。


 以下はもしかしたら素数探索の手助けになるかもしれないメモです。

●一般項
 次の式で求められる(^は乗数、[]は小数点以下切り捨てを意味する)。
 [10^k*1234567890/9999999999]
 for文を使うより一般項で普通に計算した方が速い。

●末尾が1と7だけ探索すれば良い
 2と5の倍数を除外すると末尾が1、3、7、9の4つを探せば良いことが分かるが、3と9も除外することができる。なぜなら各桁の数を合計すると必ず3の倍数になるため(3の倍数を求める方法)。

●最大公約数を求めることでさらに除外
 素因数分解や素数判定は時間がかかるが、最大公約数の計算は比較的高速に求めることができる。
 例えば下の2つの数の最大公約数を求めるとその数は7となり、両方とも素数でないことが分かる。
 123456789012345678901234567890(30桁)
 12345678901234567(17桁)
 この例では桁数が30*k+17の形のときは7の倍数になる(つまり素数ではない)ことを意味するので、その形になるものを素数判定の対象から除外することができる。
 他にも、110*k+87桁、110*k+21桁などが素数の判定から除外できる。
 こういうのをたくさん探しておくことで、素数判定の対象を減らせる。

●素数判定の前に軽く素因数分解した方が速いことも
 桁数が大きくなるとミラー・ラビン素数判定法でもかなりの時間を要する。
 そこで素数判定の前に“軽く”素因数分解をやるやり方も有効になってくる。
 自分はポラード・ロー素因数分解法を使った。


 というわけで2016年はこれでお終いです。
 良いお年を。
このエントリーをはてなブックマークに追加

 写真は今月11日ごろの新聞に挟まっていたトイザらスのカタログタイプのチラシ。こういうのは最近の流行りが分かるので眺めて見たりしますが、ちょっと気になるものが。
トイザらス11月チラシ

 気になる部分を拡大。
トイザらス11月チラシ拡大

 ユーチューバーがサンタになってプレゼントを届けてくれるそうな。ユーチューバーが子供たちに人気があるというのは聞いていたが、トイザらスの仕事をするほどということは本当に人気なんだなと思わずにはいられません。(ネット上ではディスる人が多いですが)


●ブラックフライデーも
 こちらは11月25日(金曜)の新聞に挟まっていたトイザらスのチラシ。
トイザらス_ブラックフライデー
 今年になって「ブラックフライデー」というワードをやたらよく目にするようになったわけですが、トイザらスもブラックフライデーのようだ。元々はアメリカで11月の第4金曜日をブラックフライデーと呼び、この日から年末セールを開催するというもの。
 ここ数日の日本でのブラックフライデーブームには広告代理店あたりがハロウィンの次を狙っているような気がしてならないです。


 余談。
 メガドライブはハローマックで買いました。
このエントリーをはてなブックマークに追加

 日付をyyyymmdd形式の8桁の値とみなしたとき、その値が素数であるのを素数日と呼んでいるそうな。
 例えば、2016年4月1日は20160401となり、この値を判定すると素数であることが分るので、素数日ということになる。

 それならばと、こんな雑学を作ってみたいと思った。

 「今日の日付(A)は素数日です。そして明日の日付(B)も素数日です。このように2日連続で素数日になるのは珍しく、前回は(C)と(D)だったので実に(E)年ぶりとなります」

 さて、(A)~(E)にはどのような数字が入るのか?
 この雑学を披露できるのはいつになるのか?
 という探索をしてみた。


 まず素数日となる候補だが、偶数日は2の倍数になるためこれはまず候補から外れる。
 そして、奇数日が2日連続するのは限られていて、月末の31日と翌月の1日というパターンが候補となる。
 このとき、うるう日の2月29日も月末で奇数日になるなので忘れないようにする。(ついでに年越しの12月31日から1月1日も忘れやすいので注意)
 調べるのは次のようになる。

 1月31日 → 2月1日
 2月29日 → 3月1日(うるう年のみ)
 3月31日 → 4月1日
 5月31日 → 6月1日
 7月31日 → 8月1日
 8月31日 → 9月1日
 10月31日 → 11月1日
 12月31日 → 1月1日

 ここでさらに注意が必要なのが、うるう年(うるう日)について。
 実は4年に1回あるのではなく、400年に97回(100回ではない)になるように設けられているということだ。
 うるう年の規則はこのようになっている。

 (1)4で割り切れる年はうるう年
 (2)ただし100で割り切れる年は平年
 (3)ただし400で割り切れる年はうるう年


 以上を踏まえて、前世紀(20世紀)と今世紀(21世紀)の範囲で2日連続の素数日を探索したところ、以下が該当することが分かった。

 20世紀
 19130731, 19130801
 19210531, 19210601
 19240229, 19240301
 19250131, 19250201
 19301231, 19310101
 19500331, 19500401
 19721231, 19730101
 19781231, 19790101
 19790131, 19790201
 19830331, 19830401
 19871231, 19880101
 19900831, 19900901
 19971031, 19971101

 21世紀
 20020531, 20020601
 20170831, 20170901
 20180731, 20180801
 20201231, 20210101
 20280229, 20280301
 20291231, 20300101
 20361031, 20361101
 20640331, 20640401
 20680831, 20680901
 20750131, 20750201
 20800229, 20800301
 20800531, 20800601
 20811031, 20811101
 20930731, 20930801

 今から一番近いのは20170831と20170901のパターン。
 これはちょうど1年後の今日! というわけで、当初の目的である雑学の披露を忘れないよう、さっそくブログに予約投稿しておこうと思う。
このエントリーをはてなブックマークに追加

 あのコピペの素数にはかなわないが、こんな素数を発見した。

71 ← 素数
701 ← 素数
7001 ← 素数
70001 ← 素数
700001 ← 素数
7000001 ← 素数じゃない (197 * 35533)
70000001 ← 素数じゃない (43 * 61 * 26687)
700000001 ← 素数
7000000001 ← 素数
70000000001 ← 素数じゃない (53 * 1320754717)
700000000001 ← 素数じゃない (41149 * 17011349)
 :
(ずっと素数じゃない)
 :
7000000000000000000000000000000000000000000001 ←たぶん素数


 あのコピペの素数は、ツイッターを検索するといまだに披露しているbotがいくつもあるようだ。
このエントリーをはてなブックマークに追加

 1000000000000066600000000000001は素数だそうな。
 真ん中にある666は獣の数字と呼ばれる不吉な数。
 さらに、両サイドに並ぶ0の数はそれぞれ13個と、これまた不吉な数。
 そして回文になっているので回文素数である。
 このよくできた素数はベルフェゴール素数(Belphegor's prime)と呼ばれているそうな。

 参考:Belphegor's prime - Wikipedia

 ちなみに、666は最初の7つの素数の2乗の総和である。
 2*2 + 3*3 + 5*5 + 7*7 + 11*11 + 13*13 + 17*17 = 666


 以上だとwikipediaからのただの受け売りなので、独自に発見したのを一つ。
 似たような素数がないかと色々素数判定してみたところ、どうやら以下の回文数も素数らしいことが分かった。(「らしい」とするのは素数判定に使ったミラーラビン素数判定法が確率的素数判定法のため。しかし512個の素数でテストしたのでほぼ間違いなく素数だと思う)

 1000000000000077700000000000001

 これはベルフェゴール素数の666を777に置き換えただけである。それも回文素数になるというのは少し驚きだ。

 しかし、自分だけの発見かと思ったら、この数字で検索するとすでに発見した人がいるのが少し悔しい……。それでも、検索件数は少ないし、日本語のサイトはないので、今なら知っている人は少なく自慢できるかもしれない。
このエントリーをはてなブックマークに追加

↑このページのトップヘ