思垢メモ
経験したこと、感じたこと





【思考実験】受験番号を素数のみにして合否発表を合成数で提示する案


素数を使った合否発表システム

先日、ツイッターでおもしろそうな理論を発見しました。

ネタのようにつぶやかれていましたが、個人的に結構使えるのでは?と思ったので試しに遊んでみました。

仕組みの簡単な説明

素数とは

1 より大きい自然数で正の約数が 1 と自分自身のみであるもののこと。

です。

例えば、「7」とか。「6」は「2や3」で割り切れるから素数ではない。

素数素数を掛け算すると素数ではなくなりますが、その合成数素数素数に一意に分解できます。これが素因数分解
素数である7と素数である11は、かけると77。これを分解すると7と11。

逆に素数じゃない6と素数である11は、かけると66。これを素数で分解すると 2と3と11。6が消えてしまいます。

つまり、素数は掛け合わせても、分解すれば一意に戻すことができるので、「受験番号をあらかじめ素数だけにしておけば、合否発表は1つの巨大な合成数掲示するだけで済み、受験生はその合成数を自分の受験番号で割りきれるか否かで合否を知れる」ってなわけです。

受験生が10人の場合

2,3,5,7,11,13,17,19,23,29

各位は上記の番号を振られます。

で、その中で「2」「13」「23」の3人が合格なのだとすればそれらの積「598」を合否発表として提示します。

すると受験生は自分の番号で割り算をします。

例えば受験番号11の人は「54.36363...」と割り切れないので不合格。受験番号13の人は「46」と割り切れるので合格。

実際に運用するとして

素因数分解が試験の出題範囲に入ってそうな、IPAの「応用情報技術者」の合格発表に使うと仮定します。

受験者は約5万人。

そのためには計5万の素数が必要ですが、素数は飛び飛びになっているので2から約60万までの間にある素数が必要です。
例えば「599999」は素数なので受験番号になりえます。ちなみにこのあたりは結構間が空いてしまいます。

...
599959
599983
599993
599999
...

6桁の受験番号はざらなので、運用上は問題なさそう。

やばいのはこの合成数

応用情報技術者は約1万人が合格するので例えば2から60万までの素数の中央値である「281381」あたりが1万回掛け算になるとすると10の「54492」乗になります。ちなみに無量大数は68乗です。

割り算を電卓に入力するのも一苦労(5万桁を間違えずに入力する必要あり)ですし、そもそもそこまでの桁数を入力できるマシーンなさそう。合成数素数ではないので、5万桁(1万の素数の積)から特定の素数が割り切れるか否かのチェックって簡単にできるんでしょうか?専門家の方教えてください。

所感

素因数分解を理解できていて、参加者が20人以下くらいであればなんとか使えそう。
他の人の合否が分かりづらいというメリットがある、おもしろい発想なので気になって調べてみました。

5分くらいで書いた記事なので、おかしなところがあればお知らせください。