素数大富豪素数問題に挑む -3日目- Ruby活用

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

  

〜前回までの進捗〜

• 最大の数は72桁（実際に出せる数は71桁以下）
• 使うカードの枚数は考えず、できる素数の桁数で分けて考える
• 4桁以下の素数1,229個は全て表現可能
• 5桁の素数は8,357個が表現可能 

以上

＜3日目＞ 2014年12月29日（月）

しばらく寝かせていたら、あっという間に年末。

「素数大富豪素数問題」提唱者(?)の@tsujimotterさんとお酒を飲みつつ、次のステップについて相談させてもらった。

2日目までで、5桁までの素数に関しては答えが得られたので、6桁についても同じ調子で調べることができる。

またここで、@tsujimotterさんに新しい技を教えてもらった。Rubyの素数判定コードである。

require 'prime'

Prime.prime? a

これだけでaの素数判定ができてしまうそうな。。便利！

これを活用して、ざっくり言うと下記のような内容のプログラムを書いた。

1. 6桁の数を各桁ごとに分ける
2. 0が含まれていたら+1、10が含まれていたら-1として、「0のカードを使う必要のある数」をピックアップ
3. 3枚以上使う（=トランプでは表現不能）数について、素数判定
4. 「0を3枚以上使う素数」の数を表示

結果、上記条件に該当する数は203個存在することがわかった。

これを6桁の素数の数（68,906個）から差し引いて、6桁で表現可能な素数は68,703個ということになった。

それからこれは余談だが、議論をしながらRubyのコードを打っていて、インデントのスペースの数のことで@tsujimotterさんとケンカした。

たまーにしかプログラムをいじらない人間からしたらどうでもよいことに見えるのだが、大事なことらしい。一応覚えておこうと思う…。

さて7桁より先については、いよいよ0以外の数字が重複して出てくる可能性を排除しなければいけなくなってくるが、基本的には今回使ったものを応用していけばある程度まではいけるだろうと思われる。

ただ、ほぼ全てのカードを使用した場合の約70桁という数字は、さすがに素数判定をすることが困難らしい。

「この問題を全部解くのは無理じゃないかなぁ」と発案者に言われたところで、3日目は終了となった。

ここまでのまとめ

• 6桁の素数は68,703個が表現可能
• Rubyのコードを書く時のインデントはスペース3つ
• 70桁くらいの素数判定は大変そうだ

「最後まで行けない」とわかってしまい一気にやる気が失われた感があるので、この先に進むのがいつになるかはわからない。

ただ、6桁までで計78,289個の素数が表現できることがわかった時点で、「素数大富豪で使えそうな素数を全部覚えよう」という想いは打ち砕かれたので、ひとまず十分と言えるかもしれない。