素数大富豪素数問題に挑む -6日目- 9桁その1
※この記事は、数字のド素人であるにせーが、素数大富豪素数問題に挑む記録です。
〜前回までの進捗〜
- 最大の数は72桁（実際に出せる数は71桁以下）
- 使うカードの枚数は考えず、できる素数の桁数で分けて考える
- 4桁以下の素数1,229個は全て表現可能
- 5桁の素数は8,357個が表現可能
- 6桁の素数は68,703個が表現可能
- 70桁くらいの素数判定は大変そうだ
- 7桁の素数は、581,128個が表現可能
- 8桁の素数は、4,976,857個が表現可能
以上
＜6日目＞ 2015年1月12日（月）
9桁をまとめて片付けるのは厳しそうなので、ひとまず100,000,000〜199,999,999の範囲から求めてみることにした。
199,999,999までの素数の個数は、8桁と同じプログラムを回して2時間ほど放置したら、いつの間にか算出されていた。
該当する範囲の素数の個数は、5,317,482個だそうだ。
6桁からほぼ変わっていないプログラムを、さらに9桁用にアレンジする。
- 9桁の数aを各桁ごとに分ける
- 数字ごとに個数をカウントする。0に関しては、0が含まれていたら+1、10が含まれていたら-1とする。2に関しては、2が含まれていたら+1、12が含まれていたら-1とする。
- 2〜9のどれかの数字を5枚（0は3枚）以上使う数（＝トランプでは表現不能）である場合、素数判定
- これを100,000,001 ≦ a ≦ 199,999,999の範囲で実行
- 「トランプでは表現不能な9桁の数」の個数を表示
結果、上記条件に該当する数は119,144個存在することがわかった。これも案外難なく計算できた。
ただ、ここで気を付けなければならないことがある。
これまでは「1」が使われている個数はカウントしていない。
しかし、9桁では「1■1■1■1■1」の形の素数を除外しなければならない。
（■ = 4〜9のどれか、桁ごとに別の数字でもよい）
これは結構面倒な作業になるかと思われたが、よくよく考えてみると、9桁では1が5つ含まれていれば4〜9の数字については5つ以上重複することがないので、別途簡単なプログラムを組むことで解決できそうだ。
- 9桁の数aを各桁ごとに分ける
- 奇数桁目が1で、かつ偶数桁目が4〜9である数字だけを抽出
- 素数判定をし、個数をカウント
しかも、aに入れる数字は141414141〜191919191の範囲で構わない。
結果は172個だそうだ。
つまり、素数大富豪で出すことのできる、1で始まる9桁の素数は
5,317,482 - 119,144 - 172 = 5,198,166個
となった。
これだけで、8桁の個数を軽く越えている。
ここまでのまとめ
- 9桁の素数は、5,198,166個以上が表現可能
9桁の残りの数については、1のことを考えなくてよくなるので、計算方法は8桁までと同様でよいであろう。
あとはPCがどれだけがんばってくれるかにかかっているような気がする。
