うえぽんSW局

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

タグ:数学

 年末年始のことになりますが、次のような記事を見つけたので、素数遊びをしてみました。

 年末年始は難解な素数と遊ぼう 回文素数、レピュニット素数、数素 | JBpress(日本ビジネスプレス)
 (現在、この記事の2ページ目以降は会員登録していないとみられないようです)

 上のページによると、ホネカーという人によって次のような回文素数のピラミッドが発見されているとのこと。

2
30203
133020331
1713302033171
12171330203317121
151217133020331712151
1815121713302033171215181
16181512171330203317121518161
331618151217133020331712151816133
9333161815121713302033171215181613339
11933316181512171330203317121518161333911


 これに興味をそそられたので、これより大きなピラミッドがないかと自分も探してみることにした。
 プログラムを組んで探すだけなので手軽なものだと思っていたが、しかし、最初に見つけた回文素数ピラミッドは次のようなものだった。

2
929
39293
3392933
733929337


 ホネカーのものよりも小さなピラミッドになってしまった。
 自分が組んだプログラムにミスがあったのだろうか? と一瞬思ったものの、ホネカーのピラミッドを見返してみると、ホネカーのものは1段ごとに左右2桁ずつ(合計4桁ずつ)増えていることに気付いた。
 自分が探していたのは左右1桁ずつだった。
 左右1桁ずつだとこの程度の高さのピラミッドにしかならないらしい。

 気を取り直して左右2桁ずつ増えるようにして探索。
 すると次のような回文素数のピラミッドを発見した。これはホネカーのものよりずっと大きい。

5
97579
389757983
3138975798313
15313897579831351
741531389757983135147
9074153138975798313514709
73907415313897579831351470937
907390741531389757983135147093709
3690739074153138975798313514709370963
38369073907415313897579831351470937096383
393836907390741531389757983135147093709638393
7039383690739074153138975798313514709370963839307
71703938369073907415313897579831351470937096383930717
347170393836907390741531389757983135147093709638393071743
9534717039383690739074153138975798313514709370963839307174359
93953471703938369073907415313897579831351470937096383930717435939
799395347170393836907390741531389757983135147093709638393071743593997
3679939534717039383690739074153138975798313514709370963839307174359399763
14367993953471703938369073907415313897579831351470937096383930717435939976341
761436799395347170393836907390741531389757983135147093709638393071743593997634167
1776143679939534717039383690739074153138975798313514709370963839307174359399763416771
70177614367993953471703938369073907415313897579831351470937096383930717435939976341677107
787017761436799395347170393836907390741531389757983135147093709638393071743593997634167710787
3878701776143679939534717039383690739074153138975798313514709370963839307174359399763416771078783
94387870177614367993953471703938369073907415313897579831351470937096383930717435939976341677107878349
149438787017761436799395347170393836907390741531389757983135147093709638393071743593997634167710787834941
3314943878701776143679939534717039383690739074153138975798313514709370963839307174359399763416771078783494133
99331494387870177614367993953471703938369073907415313897579831351470937096383930717435939976341677107878349413399


 当ブログの横幅の関係でうまく表示できていないかもしれないので、画像にしたものも用意してみました。クリックすると見られます。
 回文素数のピラミッド

 同じものを発見した人がいないかとGoogle検索してみたところ、次の2件だけ発見。

 ・number theory - Origins of the conjecture on the existence of infinitely many palindromic primes - Mathematics Stack Exchange
 ・burde_27_analytic_nt_course.pdf(PDF注意)

 このどちらもが自分が発見したものより少し低いピラミッドとなっている。最後の6段ほどがない。
 これは最後まで探索できなかったのか、それとも自分の方が間違っている可能性がある。
 しかし自分のはGNU Multi-Precision Library(GMP)の関数mpz_probab_prime_p()で65536回ものミラーラビン素数判定をパスしているから、間違いということはないと思うのであるが……。
このエントリーをはてなブックマークに追加

 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年はこれでお終いです。
 良いお年を。
このエントリーをはてなブックマークに追加

 日付を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に置き換えただけである。それも回文素数になるというのは少し驚きだ。

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

↑このページのトップヘ