🤮

グロタンディーク素数っぽい数がどのぐらい素数なのかの正答率(Accuracy)をプロットしてみた

2022/10/09に公開

Python

math

tech

旧題: 「パッと見で素数っぽい数」がどれぐらい素数として当たっているか調べてみた

PVがあまりにもへっぽこすぎたので変更しました。

素数とかの前に。ヒューリスティックとは

ヒューリスティックは、発見的手法とも呼ばれ、「経験則や直感から近似解を得る」という、アルゴリズムに対比する概念です^[1]。人間は、日常生活を比較的ラクに過ごすために、厳密解を頑張って求めようとするのではなく、近似解を求めてそれで暮らすことが多いと言われています（たぶん）。

たとえば、初めて来た百貨店でうんちが急にしたくなりトイレをなるべく短時間で探さなければならなくなったと仮定します。このとき、

まずはトイレのマークを探すために吊り下げ式表示版がないか見上げる
とりあえず全体を見通すためにそのフロアの大きなコンコースに出てみる
化粧品売り場や女性服売り場には、男子トイレはない確率が高いはず。よって1階や2階には所与の条件を満たすトイレが無い可能性がある
ゲーム売り場は混雑していることが多いはずだから仮にトイレがあってもトイレが混雑していて失敗する可能性が高まる
フロアマップはエスカレーターの近くにあるはず
インフォメーションにフロアマップは置いてあるはず
店員さんっぽそうな人に聞く
スマホでフロアマップを調べる

のような処理を行う必要が生じます。つまり、うんちが正しくできるかどうか一生懸命探索することになると思います。

このとき「もっとも混んでないトイレへの最短距離を最小コストで算出できるか」ということは考えていないはずです。そんな暇があったら走ったりキョロキョロするからです。

実際には、もっと切羽詰まっているときは上記のような思考もなかなかできないと思います。

「漏れる！」「トイレマーク！」「フロアマップ！」「え、この階に無いの！？」「店員さんっぽい人…！知らなさそうだな！！！」「混んでる！？？！」「ああああああああああああああああぁあぁあああ」

みたいな感じではないでしょうか。

他にも、「ガチャの確率が1%なのに100回やっても当たらないのはおかしい」と考えるのはある意味ヒューリスティックだと思います。実際は約63%になりますが、63%であると思うためには、確率を正しく理解する必要があるか、「1%の排出率のガチャを100回引いて当たる確率は63%説」を信じる必要があると思います。

まあそんなわけで、今回は「人間には素数っぽく見える数」と「素数」についてどのぐらい合っているのかの正答率を出してみたりしてみました。

「素数っぽく見える数」の定義

「素数っぽい」というのは結構人によって定義が異なると思います。

たとえば、 $169$ は全然素数ではありませんが、これが素数でないのがなぜすぐわかるかというと、 $13\times 13 = 169$ という計算結果を子どものころに覚えたために、事前に知っている人が多いからだと思います。そのため、「いやいや、そんなの覚えたことないよ」「そんなの覚えたりせんがな」という人にとっては、 $169$ はかなり素数っぽく見えるかもしれません。

たとえば $57$ は「ちょっとだけ素数っぽい^[2] 」ですが、実際は $3 \times 19 = 57$ で、素数ではありません。「 $57$ は全然素数なんかじゃないだろ！」と言い切りたい人でも「でも $4$ と比べるとだいぶ素数っぽくない？」というのは「う〜ん？まあ……せやな……」としぶしぶ納得できると思います。

一方で、 $211$ という数字を見てすぐに「これは素数っぽいというか、素数だよ」と言い切れる人もいるかもしれません。 $2 \times 3 \times 5 \times 7 + 1 = 211$ だからです。あんまりいない気がします。

その人の人生経験によってそれぞれの素晴らしさと、それぞれの素数らしさがあるのだと思います。この「素数らしさ」は、実際にその数が素数であるかどうかはあまり関係がないと思います。

統一的な見解もないと思うので、そういうわけで、ぼくが雑に思う「ずぼら計算で素数っぽいと感じるような定義」を今回は使うことにします。

つまり、今回の「素数っぽさ」は、ぼくの独断と偏見によって決まっています。

それから素数っぽく見える数のことを「人素数」と名付けてみたいです（素人と掛けた高度なギャグ。なお、今回はこの造語は一切つかいません）

かえる的、素数っぽさ性の定義

2 3 5 7 11 13 17 19 23 であれば、ただちに素数っぽさ性を持つとする

または、以下をすべて満たすときに「素数っぽさ性をもつ」とする

121 169でない
奇数である
3または5または7で割り切れる
九九の結果ではない

というふうに定義します。定義はぼくの独断と偏見でおこないました。

レギュレーション的には「計算がいわゆる『たいへん』ではなく、平易で妥当な筆算でできる」という感じです。

ちなみにこれは $142$ まで100%正しいですが、以降は $143 = 11\times13$ となってしまって外れてしまいます。かなしいです。

以下は、1〜2000までの「素数っぽい数」のうち、実際には素数じゃない数（合成数）です。体感として「素数じゃ、ない……？」となりそうな数が並んでいるような気がします。なんというか、体がゾワッとする数が並んでいます。でも、 $961, 1133$ あたりとは仲良くできそうな気がします。^[3]

こういうのを使って「何で割り切れるかゲーム」とかをやると盛り上がるかもしれませんね（盛り上がらない）

 143  187  209  221  247  253  289  299  319  323
 341  361  377  391  403  407  437  451  473  481
 493  517  527  529  533  551  559  583  589  611
 629  649  667  671  689  697  703  713  731  737
 767  779  781  793  799  803  817  841  851  869
 871  893  899  901  913  923  943  949  961  979
 989 1003 1007 1027 1037 1067 1073 1079 1081 1111
1121 1133 1139 1147 1157 1159 1177 1189 1199 1207
1219 1241 1243 1247 1261 1271 1273 1313 1331 1333
1339 1343 1349 1357 1363 1369 1387 1391 1397 1403
1411 1417 1441 1457 1469 1501 1507 1513 1517 1529
1537 1541 1573 1577 1591 1633 1639 1643 1649 1651
1661 1679 1681 1691 1703 1711 1717 1727 1739 1751
1763 1769 1781 1793 1807 1817 1819 1829 1837 1843
1849 1853 1859 1891 1903 1909 1919 1921 1927 1937
1943 1957 1961 1963 1969 1991

実際の素数の洗い出し

素数の洗い出しはエラトステネスのふるいというアルゴリズムを使います。言語はPythonです。

てきとーに実装しましたが、↓のサイトの方と一致していたので「まあ合ってるやろ」と思ってそのまま使っています。

https://2357.aimary.com/download.html

# Nに100を入れると2から100までの素数を表示してくれる
def generate_primes(N):
  primes = [True] * (N + 1)
  primes[0] = False
  primes[1] = False

  results = []
  for p, is_prime in enumerate(primes):
    if not is_prime:
      continue
    results.append(p)

    for xp in range(2 * p, N + 1, p):
      primes[xp] = False
  
  return results

素数っぽさ性の判定

さっき挙げたものをそのまま実装していきます。

nine_nine_but_over_9 = set()
for i in range(2, 10):
  for j in range(2, 10):
    if i * j > 9:
      nine_nine_but_over_9.add(i * j)

instant_ok = set([2, 3, 5, 7, 11, 13, 17, 19, 23])
instant_ng = set([121, 169])
def evaluate(n):
  if n in instant_ok:
    return True

  if n % 2 == 0:
    return False
  
  if str(n)[-1] == '5':
    return False
  
  if n % 3 == 0:
    return False
  
  if n in nine_nine_but_over_9:
    return False

  if n in instant_ng:
    return False
  
  if n % 7 == 0:
    return False

  return True

判定結果

そういうわけで1億のオーダー( $10^8$ )まで測ってみました（本当はもっと計算の最適化できるはずですが、こまけぇこたぁいいんだよ）

こう見ると精度がとても悪いことがわかります。まあ1桁の割り算しかしていないので妥当な感じはしますが、直感的には「えっ、全然当たってないじゃん」という感じがします。

とくに、10万のオーダーになって以降は、ほとんど当たらなくなっています。

----- 100 -----
素数っぽいとみなした個数: 25
外した個数: 0 誤答率: 0.0
素数の個数: 25 正答率: 1.0

----- 1000 -----
素数っぽいとみなした個数: 229
外した個数: 61 誤答率: 0.26637554585152834
素数の個数: 168 正答率: 0.7336244541484717

----- 10000 -----
素数っぽいとみなした個数: 2286
外した個数: 1057 誤答率: 0.46237970253718286
素数の個数: 1229 正答率: 0.5376202974628171

----- 100000 -----
素数っぽいとみなした個数: 22858
外した個数: 13266 誤答率: 0.5803657362848893
素数の個数: 9592 正答率: 0.4196342637151107

----- 1000000 -----
素数っぽいとみなした個数: 228572
外した個数: 150074 誤答率: 0.6565721085697286
素数の個数: 78498 正答率: 0.3434278914302714

----- 10000000 -----
素数っぽいとみなした個数: 2285714
外した個数: 1621135 誤答率: 0.7092466511558314
素数の個数: 664579 正答率: 0.2907533488441686

----- 100000000 -----
素数っぽいとみなした個数: 22857143
外した個数: 17095688 誤答率: 0.7479363453253978
素数の個数: 5761455 正答率: 0.2520636546746022

せっかくなのでプロットしてみました。適切な描画方法を使っていることになっているのかはよくわかりません。

著しく性能劣化していることが目でもうかがえます。

まとめ

体感として、いままで「素数っぽいけど素数じゃない数ってなんか嫌だなあ」というふうに思っていましたが、実際には、数が大きくなるとぼくが「素数っぽい」と感じているものは全然素数ではなくなってしまうというのがわかったのでおもしろかったです（小並感）

それからこうした人間の常識をモデルとする判定と実際の現実との比・差を比較することは、けっこう大切なことのような気がします。

現在見つかっているモデルのような計算を膨大に必要とするモデルを人間がそのまま扱うとか、現在は「常識」とされているモデルを人間が扱うのではなく、もっと人間でも平易で簡単に計算することができて、「あるオーダーまではこれでうまくいく！」というようなモデルを「新しい時代の知識・常識」として人間にインストールできるといいのかもしれません。しらんけど。

理論化はしません。誰かしてくれたら教えてください。

ソースコード

ここにあります。

脚注

ヒューリスティックは心理学用語でもあるみたいですが、今回使うのはその用法ではありません。 ↩︎
ちなみに $57$ は冗談でグロタンディーク素数と言われているみたいです ↩︎
暗算で割れるから ↩︎