うえぽんSW局

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

タグ:数学

 今日の日付20170831は素数日です。
 そして明日の日付20170901も素数日です。
 このように2日連続で素数日になるのは珍しく、前回は20020531と20020601だったので15年ぶりとなります。
 ちなみに、次回はおよそ1年後の20180731と20180801なります。2日連続する素数日が1年以内に2回もあるというのはそれはまた珍しいかもしれません。

 (このエントリーは1年前の今日に予約投稿したものです。詳しくはちょうど一年前の今日のエントリーをご覧ください)
このエントリーをはてなブックマークに追加

 ここ一ヶ月ブログを更新していませんでしたが実はパソコンが壊れてました。
 結局新しいパソコンを買うことになりましたが、さて、新マシンになったらまずすることといえば処理に時間の掛かりそうな計算プログラムの実行です。以前よりも速くなったことを確認します。
 そんなわけで素数を探すプログラムを組んでみたわけですが、以下のような3249桁の回文素数を発見しました(分かりやすく57桁ごとに改行してます)。

111111111111111111111111111111111111111111111111111111111
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000303000000000000000000000000001
100000000000000000000000000030000000000000000000000000001
100000000000000000000000000303000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
111111111111111111111111111111111111111111111111111111111


 表示ズレしている環境もあるかもしれないので画像にもしてみました(ついでに色も付けてます)。
 ただの回文素数ではなく、57x57の正方形にすると左右や上下にも対称という面白い形になっていることが分かります(残念ながらすべての行と列も素数とまではなっていません)。

prime57x57


 ただし、この素数の判定に用いたのはpythonの拡張モジュールgmpy2にあるis_prime関数(中身はGMPのmpz_probab_prime_p関数)のため、確率的素数ということになります。
 とはいえ乱数で8192回のテストにパスしているのでほぼ間違いなく素数だと思いますが……。
このエントリーをはてなブックマークに追加

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

 年末年始は難解な素数と遊ぼう 回文素数、レピュニット素数、数素 | 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年後の今日! というわけで、当初の目的である雑学の披露を忘れないよう、さっそくブログに予約投稿しておこうと思う。
このエントリーをはてなブックマークに追加

↑このページのトップヘ