素数大富豪素数問題に挑む -5日目- コツコツ8桁
※この記事は、数字のド素人であるにせーが、素数大富豪素数問題に挑む記録です。
〜前回までの進捗〜
- 最大の数は72桁（実際に出せる数は71桁以下）
- 使うカードの枚数は考えず、できる素数の桁数で分けて考える
- 4桁以下の素数1,229個は全て表現可能
- 5桁の素数は8,357個が表現可能
- 6桁の素数は68,703個が表現可能
- 70桁くらいの素数判定は大変そうだ
- 7桁の素数は、581,128個が表現可能
以上
＜5日目＞ 2015年1月10日（土）
怒濤の新年勤務1週目が終わり、やっと休日。家からは一歩も出たくない。よし、素数大富豪素数問題をやろう。
次は8桁。
素数大富豪で8桁といえば、アレコレ考えるのが面倒になった時やピンチの時の起死回生の策として、手元の札を一気になくそうとした場合に現れる。
この辺りの数字を勉強しておくといざという時に役に立つかもしれない。
考え方としては7桁と同じで「すべての素数の個数から、トランプでは表現不可能な素数の個数を差し引く」という方針でいいとは思うのだけど、処理する個数や数字の桁数が大きくなるに従って、徐々に素数判定が困難になっている。
とはいえ他の方法も思いつかないので、7桁で使用したプログラムを、さらに8桁用にアレンジする。
- 8桁の数aを各桁ごとに分ける
- 数字ごとに個数をカウントする。0に関しては、0が含まれていたら+1、10が含まれていたら-1とする。2に関しては、2が含まれていたら+1、12が含まれていたら-1とする。
- 2〜9のどれかの数字を5枚（0は3枚）以上使う数（＝トランプでは表現不能）である場合、素数判定
- これを10,000,001 ≦ a ≦ 99,999,999の範囲で実行
- 「トランプでは表現不能な8桁の数」の個数を表示
結果、上記条件に該当する数は120,019個存在することがわかった。
初めは8桁の数を10個程度に小分けして実行した方がいいかとも思ったのだが、実際に回してみると案外さくっと答えが出たので、最終的には8桁すべてをまとめて数えた。かかった時間は、約8分。
一方で、8桁のすべての素数の個数を求めるにあたっては、実は前日の夜に一度、7桁と同じプログラムで回してみていた。
…が、一晩経ってもターミナルさんは無言のままだった。もはや動いているのかどうかすら怪しかったので、そのプログラムは諦めることにして、またしても@tsujimotterさんに助言を求めた。
教えてもらったのは下記のライブラリ。
require 'prime'
n = 100000000
num = Prime.each(n).count
puts num
そのままずばり「100,000,000までの素数の個数を求めるライブラリ」らしい。なんと便利な。
約33分後、5,761,455という回答が表示された。
ここから、7桁までの素数の個数（664,579）を差し引いて、8桁の素数の個数は5,096,876個である。
5,096,876 - 120,019 = 4,976,857個
ホントにこんなにあるの!?と信じ難くなったので、範囲を狭めて結果をprintしてみたりもしたが、数字の並びだけを見れば確かにトランプの数字で作れるものばかりだった。
この調子でいくと、9桁になったらさらに扱う個数は増えるのだろう。
どう挑んだらいいものか…今のところ全く策はない。
ここまでのまとめ
- 8桁の素数は、4,976,857個が表現可能
- 9桁どうしよう…
今日の8桁の作業の中で、7桁のプログラムの一部の誤りと、さらにRubyさんが出した答えからブログに転記する際に数字を写し間違えていたのを発見したので、前回の記事を少々修正した。
素数大富豪素数問題に挑んでいると、しみじみと「答え合わせができる問題っていいな」と感じさせられる。
ところでトランプってスポーツ用品なの？
