素数大富豪素数問題に挑む -4日目- いけるところまでいく
※この記事は、数字のド素人であるにせーが、素数大富豪素数問題に挑む記録です。
〜前回までの進捗〜
- 最大の数は72桁（実際に出せる数は71桁以下）
- 使うカードの枚数は考えず、できる素数の桁数で分けて考える
- 4桁以下の素数1,229個は全て表現可能
- 5桁の素数は8,357個が表現可能
- 6桁の素数は68,703個が表現可能
- 70桁くらいの素数判定は大変そうだ
以上
＜4日目＞ 2015年1月7日（水）
前回（挑戦3日目）の記事を公開したところ、読者の@tsujimotterさんから
「無理かもしれないとは言ったけど、無理とは言ってないよ！」
と連絡が入った。
「どの程度の桁まで現実的な時間で計算できるか試してほしい」とのこと。
わかりました。やります。
ということで、年明けの仕事で疲れ果てた体に鞭打ってまたRubyを立ち上げた。
次に挑むのは7桁。
これまでと違って、いよいよカードの枚数が問題になってくる。
ていうかここからが素数大富豪素数問題の核となる部分なのではと気付く。
考えてみたら、これまではほぼ各桁の素数の個数を求めてただけだもんね。
確かに諦めるのは早すぎたな、と反省。
でも準備運動はばっちりなので、怖くはない。
枚数は増えても、この程度ならまだ「すべての素数の個数から、トランプでは表現不可能な素数の個数を差し引く」という方針で突き進めるはずだ。
6桁では0の個数だけをカウントしたが、7桁ではそれを他の数字にまで拡げればいいだけである。
しかも8桁までなら、1の個数は気にする必要がない。
11では補えない形で1が出現する場合が
1■1■1■1 （■は1以外の数字）
という形でしかありえないので、1はいくつあろうが表現可能なのだ。
これが9桁になるとまたややこしくなりそうなのだが…それについてはまたあとで悩もう。
さらに7桁なら、0（10の形を除いて、上限2枚）と他の数（12の形の2を除いて、上限4枚）が同時に重複してしまうこともない。
6桁からの変更点と言えば、0だけ数えていた場合は下から1桁目と6桁目は無視できたのだが（下の桁が0なら偶数なので素数にはならないし、上の桁が0では5桁以下になってしまう）、0以外の数については全ての桁を調べる必要があることくらいか。
でもこのくらいなら、なんだかすぐにできそうな気がする。
6桁で使用したプログラムを、7桁用にアレンジする。
- 7桁の数を各桁ごとに分ける（b～hとする）
- 0に関しては、0が含まれていたら+1、10が含まれていたら-1とする。2に関しては、2が含まれていたら+1、12が含まれていたら-1とする。
- 数字ごとに個数をカウントする。2〜9のどれかの数字を5枚（0は3枚）以上使う数（＝トランプでは表現不能）である場合、素数判定
- 「トランプでは表現不能な7桁の数」の個数を表示
結果、上記条件に該当する数は4,341個4,953個存在することがわかった。（※追記：プログラムに一部誤りがあったため1/10に修正）
これを7桁の素数の個数から引けば7桁は楽々クリアだ！
意気揚々と「7桁の素数の個数を求めるプログラム」を回した。
6桁までは自作の素数判定プログラムを使っていたが、さすがにRubyのprimeライブラリ（前回は勝手に素数判定コードと呼んだけどこの名前が正しい？らしい）を使うようにした。
require 'prime'
n = 0
for a in 1000000..9999999
if Prime.prime? a
n = n + 1
end
end
puts n
…
…
…え、なんか間違えた？動いてる？これ大丈夫？
うろたえながら放置すること11分、不意に「586,081」という数字が表示された。
…あ、いま終わったのね！それが君の答えなのね！
と驚いてしまうほどにその11分間は長く感じた。
そして理解した。
これが@tsujimotterさんの言っていたやつか…！
桁数が増えると素数判定は大変になる。
また、対象となる個数も当然のことながら10倍になっていく。
「1桁の増え方」は、1 桁上がるごとにどんどん大きくなっていくのだ。
たかが1桁、されど1桁。
このブログを読んだ時の@tsujimotterさんのドヤ顔が浮かんだのでそろそろやめておくが、とにかくまぁそういうことであるらしい。
たしかに7桁でこれというのは、先が思いやられるかもしれない…。
とはいえ、今日の目標だった7桁はクリアした！
586,081 - 4,953 = 581,128個
これが、素数大富豪で出すことのできる7桁の素数の個数である。
…え、そんなに？ (°ロ°;;)
ここまでのまとめ
ちなみに今日の記事の一番のポイントは、Rubyのインデントが半角スペース3つになっているところである。
日々成長。
