うえぽんSW局

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

2016年12月

 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コマ漫画】郷に従う


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

 ネット上の偽ニュース(フェイク・ニュース)を信じた男がピザ店に押し入って銃を発砲する事件がアメリカで発生したそうな。なんでもネット上にはそのピザ店を名指しして「児童売春組織の拠点だ」とする偽ニュースが拡散していたとのこと。

 ニュースソース
 ネットデマ信じピザ店で発砲… 偽ニュースの危険性、米で懸念増大:AFPBB News

 さて、この事件から想像(妄想)したことを1ページ漫画にしてみました。

【1ページ漫画】フェイクニュース

 フェイク・ニュースを報じるニュースもフェイクだったなんてことはなかろうか。

↑このページのトップヘ