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

にせいの日記

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

素数大富豪素数問題に挑む -2日目- 方針転換

※この記事は、数字のド素人であるにせーが、素数大富豪素数問題に挑む記録です。

 

素数大富豪素数問題に挑む -予告- 素数大富豪とは? - にせいの日記

素数大富豪素数問題に挑む -1日目- まずはやってみる - にせいの日記

素数大富豪素数問題に挑む -まだ1日目- 場合分けとRuby導入 - にせいの日記

素数大富豪素数問題に挑む -まだまだ1日目- 場合分けという底なし沼 - にせいの日記

 

 

〜前回までの進捗〜

  • 素数大富豪素数問題に挑戦しようと決める
  • 地道に数えるのは大変
  • 最大の数は72桁(実際に出せる数は71桁以下)
  • 場合分けするとちょっと取り組みやすくなる
  • Rubyよく覚えてないけど楽しい
  • 自分の作ったプログラムで出した数字は格別
  • 場合分けするにしても、方針を変えた方が良い気がする

以上

 

<2日目> 2014年12月24日(木)

13:40

札幌駅で買い物をしようとエスカレーターに乗っている時に、ふと思った。「10」という数字は、1と0のカード2枚で表現しようが、10のカード1枚で表現しようが、出来上がる数字は同じものである。

確認だが、素数大富豪素数問題というのは、「トランプのカードを使って表現し得る素数の数を求める」というものだ。

私はここまでなぜか「使うカードの枚数によって分類する」ということにこだわってきたが、実は使うカードの枚数なんて気にする必要はないのだった。

 

この気付きにより、1日目に混乱を極めた場合分けは「できる素数の桁数によって分ける」というシンプルな分け方に落ち着くことになった。

 

また、0の使用に関しても、少し落ち着いて考えることができるようになった。

桁数ごとに考えるとすると、一番上の桁に0は来ない。さらに一の位に0が来ればそれは10の倍数であるので、結局0が入ることができるのは、「桁数-2」枚だけなのである。

ジョーカー2枚を使えば、0は最低でも2回使えるので、ひとまず4桁までの素数については、全て作ることができるということがわかった。

 

さらに5桁の数に関しては、「0が3つ以上含まれている素数」だけが作れない。つまり「x000xという形を取る素数」だけを考えればよい。しかも「1000x」という数字は、10のカードを使えば作ることができるので除外できる。

このくらいなら手動でひとつずつ素数判定しても苦にはならない!

 

やっと希望が見えた気がした。 

金澤翔子風呂敷 二四巾 綿友禅 【箱入】  希望

 
25:30

帰ったらやろー、と思いつつ、何かと忙しくて後回しにしていたら、こんな時間になってしまった。でもこのタイミングでやりたくなってしまったので、やった。

まず4桁までの素数は、1日目に調べたとおり、計1,229個

5桁の素数判定に関しては、Rubyさんに頼った。

指定した範囲の素数判定をしてその個数を表示してくれるプログラムというのはこれまた以前に書いたものがあったので、利用。

 

「x000xという形を取る素数」を探すという作業はほぼ手動でやった。

対象となるのは20001〜20009、30001〜30009、…という数字達なので、自作の素数判定プログラムに軽く手を加えて9個ずつまとめて判定できるようにして、それを8回繰り返した。

結果出た数字は、

(5桁の素数)-(x000xという形の素数=(トランプで作れる5桁の素数

8,383 - 6 = 8,357 

となりましたとさ。

 

ここまでのまとめ

  • 使うカードの枚数は考えず、できる素数の桁数で分けて考える
  • 4桁以下の素数は全て表現可能 →1,229個
  • 5桁の素数は8,357個が表現可能

 

やっと前に進んだ感!