読者です 読者をやめる 読者になる 読者になる

にせいの日記

「自分の好きなものってなんだろう?」という疑問を解決するために、気が向いた時に好きなことを書いてみて、「自分の好きなもの」をあぶり出そうと試みています。

素数大富豪素数問題に挑む -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桁用にアレンジする。

  1. 9桁の数aを各桁ごとに分ける
  2. 数字ごとに個数をカウントする。0に関しては、0が含まれていたら+1、10が含まれていたら-1とする。2に関しては、2が含まれていたら+1、12が含まれていたら-1とする。
  3. 2〜9のどれかの数字を5枚(0は3枚)以上使う数(=トランプでは表現不能)である場合、素数判定
  4. これを100,000,001 ≦ a ≦ 199,999,999の範囲で実行
  5. 「トランプでは表現不能な9桁の数」の個数を表示 

結果、上記条件に該当する数は119,144個存在することがわかった。これも案外難なく計算できた。

 

ただ、ここで気を付けなければならないことがある。

これまでは「1」が使われている個数はカウントしていない。

しかし、9桁では「1■1■1■1■1」の形の素数を除外しなければならない。

(■ = 4〜9のどれか、桁ごとに別の数字でもよい)

 

これは結構面倒な作業になるかと思われたが、よくよく考えてみると、9桁では1が5つ含まれていれば4〜9の数字については5つ以上重複することがないので、別途簡単なプログラムを組むことで解決できそうだ。

  1. 9桁の数aを各桁ごとに分ける
  2. 奇数桁目が1で、かつ偶数桁目が4〜9である数字だけを抽出
  3. 素数判定をし、個数をカウント

しかも、aに入れる数字は141414141〜191919191の範囲で構わない。

結果は172個だそうだ。

 

つまり、素数大富豪で出すことのできる、1で始まる9桁の素数

 5,317,482 - 119,144 - 172 = 5,198,166個

となった。

これだけで、8桁の個数を軽く越えている。

 

ここまでのまとめ

  • 9桁の素数は、5,198,166個以上が表現可能

 

9桁の残りの数については、1のことを考えなくてよくなるので、計算方法は8桁までと同様でよいであろう。

あとはPCがどれだけがんばってくれるかにかかっているような気がする。