のだなのだ

ほげ〜

レピュニット素数

10進で1を並べて作った数のうち、素数になるものです。

超レアです。

2、19、23、317、1031、、、、というふうになるらしいです。

ミラーラビンで1から判定してみたのですが、確かにめちゃくちゃレアです。

1031の次は5万弱というのだから笑えませんね

 メルセンヌ素数みたいに専用のアルゴリズムがあるわけではないでしょうし劇的な高速化も不可能な気がします。実際Wikipediaに載っているものもprobably primeなので私どうようミラーラビン判定法が使われていると考えられます。私が探したとき1031まで程度ならばそこまで時間はかかりませんでした

 

 それと、ノートパソコンに入っていたWindows10を消してlinux mintを入れました。この先数カ月は動画を作る用事がなさそうなので持ち運びに便利なノートパソコンで開発をおこなえるようにしたかったのが理由です。 デスクトップのほうが使いやすいっちゃ使いやすいのですが、たまにはノートでやるのも悪くないですね。(ちなみにデスクトップのドライブの容量は128GBでノートが240なのでノートパソコンの方がでかい)

 ただ、3月中旬から下旬にかけて動画をつくる用事が出てきそうなのでそれまでに500GB程度のSSDを買いたいなと思っています。

パソコン甲子園について

 当方今高校1年で、ぱそこんをいじる部活の部長をしています。部活で先日(9月上旬だったかな?)会津大学主催のパソコン甲子園に出場しました。私を含め、出場者全員(4人)人生初の競プロだったのですが、私ともう一人の古参のチームがブロックの新人賞をいただきました。(予選落ちしましたが)

 当初の予定としては、前半(1〜4までぐらい)をそいつが考えてる間に私が5番以降のアルゴリズムを考えるというイメージで行こうと思っていたのですが、案外6番以降が難しくて1番から5番までしか解けませんでした。(9番が解けそうだったらしいですがなんかコンパイラがへんな挙動を見せたらしい)

 1から5番程度ならどちらか片方だけしかいなくても余裕で解けていたと思うのでちょっと不甲斐ない結果でした。

 また、パートナーの実装力にとても助けられたと感じたコンテストでもありました。9番がおしいところまで行ったのはひとえに彼のおかげです。

 来年はぜひ会津で本選に臨みたいです。

リュカレーマーテストとミラーラビンテスト

※リュカレーマーテストもミラーラビンテストもWiki見ればわかるので説明は省略します。

 少し前にリュカレーマーテストを使って下から順にメルセンヌ素数を探すプログラムを組んだのですが、7~8時間かかって28番目が出ないという感じでした。

 リュカレーマーテストは指数の二乗に比例して実行時間が伸びる気がするので、「リュカレーマーテストで全部の候補をテストするの効率悪すぎやろ」ってなって「これ確率的な方法である程度目星つけてからやってんのとちゃうか?」と思い、確率的素数判定アルゴリズムとして非常に有名なミラーラビンテストを実装して試しにサクッと組んで実装してみました。

 

2の9941乗-1を判定した(擬素数対策に100回判定)(乱数は64bit)

f:id:coilgunrailgun:20161028051804p:plain

ちなみにリュカレーマー

f:id:coilgunrailgun:20161028052213p:plain

ミラーラビンで一回しか判定しなくても0.4秒かかるのでリュカレーマーテストの方が速い

 

 やはり任意の数を判定できるアルゴリズムなのでメルセンヌ素数に特化したアルゴリズムにはかなわないようです。

 それにしても離散演算するとは言えGIMPSはどうやって49番目とか見つけたんでしょうね