うえぽんSW局

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

 PS1SSタイトル

 1987年12月10日の発売なので、今年で30周年だそうです。
 これを機会に12月10日までには再プレイしてみたいなと思っています。

 ちなみに「ファイナルファンタジー」や「ロックマン」、「イース」、「ソーサリアン」なども30周年らしいです。
 あと国鉄からJRになったのも1987年なのでこれも30周年になるはず。



 余談。
 節目の年の素数率が高いようです。
 1987 ← 素数
 1997 ← 素数
 2007 ← 素数じゃない (3^2 * 223)
 2017 ← 素数
 2027 ← 素数

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

 年末年始は難解な素数と遊ぼう 回文素数、レピュニット素数、数素 | 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回ものミラーラビン素数判定をパスしているから、間違いということはないと思うのであるが……。
このエントリーをはてなブックマークに追加

 あけましておめでとうございます。
 西暦の2017、平成の29、皇紀の2677、どれも素数なので今年はきっと良い年になると思います。
 ちなみに酉年のトリとはニワトリのことだそうです。鳥類なら何でもいいと思っていました……。

【4コマ漫画】2017年

 クリスマスに引き続き、ニワトリに災厄が続く。

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

 時期が少し過ぎてしまった4コマ漫画です。

【4コマ漫画】郷に従う


 アイデアメモを残していたりしますが、その中の「サンタが枕元に立つ」というメモから作って見ました。

↑このページのトップヘ