整数の第2素因数の中央値が37になる理由

• 自然数全体から一様に選ぶことは不可能なので、1から Nまで一様選択 したあと N → ∞ の極限を見る方法で「ランダムな整数」を定義する
• Those Fascinating Numbers では、ランダムな整数の第2素因数が37未満である確率がおよそ1/2であることが述べられており、これを密度計算と実験で確認する
• 小さな素数は整数の小さな素因数として頻繁に現れるため、37のような小さな数が中央値になりうるという直感が得られる
• De Koninck と Tenenbaum の方法では、エラトステネスのふるい のように特定の素数で割り切れる条件を組み合わせて λ₂(p) を計算する
• λ₂(p) を素数ごとに足し上げると、37で累積密度が約 0.5002 に達し、N=10⁷ の直接計算値 0.5002501 とも非常に近い

---

37という数の出典

• Those Fascinating Numbers の序文には、37が 整数の第2素因数の中央値 であるという一文がある
  • ランダムに選んだ整数の第2素因数が37より小さい確率がおよそ1/2だという内容である
• 最初は37があまりに小さく、信じがたく見えるが、小さな素数が整数の小さな素因数として頻繁に現れることを考えると納得しやすい
  • たとえば整数の約半分は、最小の素因数として 2 を持つ
• 目標は、この事実を自分で実験し、De Koninck と Tenenbaum の論文をもとに、なぜ37が現れるのかを計算することである

「ランダムな整数」を定義する方法

• 自然数全体には 一様分布 が存在しないため、まず大きな数 N を固定する
• 1からNまでの整数のうち1つをランダムに選び、N → ∞ のときの確率の極限を見る
• N が小さい場合は、各整数の第2素因数を直接求めて 中央値 を確認できる
• N=10⁷ で実行すると、累積確率の近似値は 0.5002501 になる
  • オンラインの SageCell では、この程度の大きさの因数分解は時間がかかりタイムアウトする可能性があるため、ローカル実行が必要である

λ₂(p): p が第2素因数である密度

• De Koninck と Tenenbaum の論文 Sur la loi de répartition du k-ième facteur premier d’un entier では、p が第2素因数となる整数の密度を λ₂(p) と置く
• 計算の核心は、エラトステネスのふるい に似た方法で、特定の素数で割り切れるかどうかを組み合わせて密度を数えることである
• 第2素因数が 5 である場合は、次の2通りしかない
  • 2^a 3^0 5^b ...: 2 と 5 の倍数で、3 の倍数ではない数
  • 2^0 3^a 5^b ...: 3 と 5 の倍数で、2 の倍数ではない数
• 最初の場合の密度は 1/2 × 2/3 × 1/5 = 1/15
• 2番目の場合の密度は (1 - 1/2) × 1/3 × 1/5 = 1/30
• 2つの集合は互いに重ならないので合計でき、第2素因数が 5 である整数の密度は 1/10 になる

一般の素数 p に対する公式

• p が2番目に小さい素因数になるには、p より小さい素数のうち1つ q は含まれ、q と p を除く p より小さい素数 r は含まれてはならない
• この条件は次の形の素因数分解で表せる

[ p^b q^a \prod_{q \neq r \lt p} r^0 ]

• 各 q < p について密度を計算して足し合わせると、次の公式が得られる

[ \lambda_2(p) = \sum_{q \lt p} \frac{1}{p} \frac{1}{q} \prod_{q \neq r \lt p} \left ( 1 - \frac{1}{r} \right ) ]

• 同じ式は次のようにも整理できる

[ \lambda_2(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] \sum_{q \lt p} \frac{1}{q} \left(1 - \frac{1}{q}\right)^{-1} ]

37 が中央値になる計算

• 求めたい素数 (p^) は、第2素因数が (p^) 以下である密度の総和が約 1/2 になる点である

[ \lambda_2(2) + \lambda_2(3) + \lambda_2(5) + \ldots + \lambda_2(p^*) \approx \frac{1}{2} ]

• λ₂(p) を実装して素数ごとに足し上げると、37 で累積密度がおよそ 1/2 に達する
• 計算された実際の期待密度は約 0.5002 である
• 直接の因数分解にもとづく実験で N=10⁷ のときに得られた値 0.5002501 も、この値に非常に近い

第k素因数への拡張

• 第k素因数が p である密度 λₖ(p) の一般公式は次のとおりである

[ \lambda_k(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] s_{k-1}(p) ]

• ここで (s_j(p) = \sum \frac{1}{m}) であり、この和は、素因数をちょうど j 個持ち、それらの素因数がすべて p より小さい m について取る
• 第k素因数の中央値 (p_k^*) の漸近式は次のようになる

[ \log \log p_k^* = k - b + O\left(\frac{1}{\sqrt{k}}\right) ]

• ここで b は次の値である

[ b = \frac{1}{3} + \gamma - \sum_p \left( \log((1-1/p)^{-1}) - 1/p \right) ]

• (\gamma) は Euler-Mascheroni Constant である

[GN⁺]

Hacker News のコメント

• ここで 37そのもの に特別に面白い点がある、という意味ではない
  むしろ興味深いのは、ここで 有限の中央値 が存在すること自体だ。それが成り立つなら、中央値はリストの要素として定義されている以上、どれか 1 つの素数になるしかない。このリストではたまたま 37 だっただけで、別の値でもよかった
  37 が本当に面白くなるのは、中央値が集合の外の値も取れるように定義を緩めても、極限がなお 37 に収束する場合だろう。そうならかなり驚きだったはず

  • N → ∞ の極限を取るとリストは伸び続ける。したがって 37 の出現回数 も増え続け、全体の値のうち漸近的に一定の割合、約 0.963% を占める
    37 より小さい値は約 49.061% しかなく、37 より大きい値も約 49.975% しかない。ある時点以降、偶数の N では 50% 地点の両側に常に 37 が 2 つあるので、中央値は別の値ではなく正確に 37 になる。詳しい説明は別のコメントに書いてある [0]
    [0] https://news.ycombinator.com/item?id=38245162
  • N 以下の整数の第 2 素因数の中央値が 特定の数 になるのは自明なのか？ この中央値がずっと大きくなっていくと考えるのも同じくらいもっともらしくないか？
  • 何の面白い話も付けられない 最初の数 が何なのか気になる
  • 中央値は単なる特定の パーセンタイル にすぎず、魔法のように特別な値ではない
    中央値の存在は、他のすべてのパーセンタイルにも極限がある可能性を示唆している。さらに言えば、どんな数についても、第 2 素因数がその数より大きい整数の極限比率が存在しうるし、37 ではその比率がたまたま 0.5 になっているだけだ
  • ここで「このリスト」とは何を指しているんだ？ 結果を誤解しているように見える

• 記事を読んで最初に浮かんだ「いったい これをどう証明するんだ？」という疑問への答えが、これほど明快に説明されていてよかった

• 面白いことに、37 は 最適停止問題 / 秘書問題 にも現れる

  • その問題は知らないし検索する気もないが、たぶん理由は 1/e ≈ 0.36787944 だからだろうと推測できる
  • 人に 1 から 100 のあいだの ランダムな数字 を思い浮かべさせると、37 が最も多く選ばれるとも言われている

• 偶然にも 37 は最初の 非正則素数 でもある。フェルマーの最終定理が難しい理由とも関係している
  https://en.wikipedia.org/wiki/Regular_prime

• 「第 2 の素数が 2 である数は 0.000000000000000」とあったが、記事タイトルは 重複なし という表現を明示しなくても正しいのか？

  • 数学を読むときは、用語の「正しい」解釈を頭の中で補うことが重要な部分だ。適切な詳細さの量はたいてい想定読者によって変わる
    英語で表記を完全に明示すると、たいてい冗長になってしまうからだ。「第 2 の重複のない素数」と書いたら、誰かが「第 2 に小さい」とか「昇順」も書くべきではないかと言うかもしれない。論文ではこうした用語は通常、より正確だが完全に厳密ではない数学記法とともに形式的に定義される
    揚げ足を取ろうという話ではなく、数学では「見えない」部分を人間がいちいち明示せず推論できることが、定理証明器の使い勝手を大きく高めるからだ。Andrej Bauer の関連講演が良い: https://www.youtube.com/watch?v=wZSvuCJBaFU
  • いい指摘だ。重複素数 を許すなら、第 2 の素数が 2 である数は 4 の倍数になる。すると全体の 1/4 だ
  • 第 2 の素数が 2 である数は アレフ 0 個 ある
  • 12 の約数は 1, 2, 3, 4, 6, 12 で、12 の 素因数 は 2 と 3 だ

• この結果を包摂するような L 関数 や モジュラー形式 の側の面白い定理や結果があるのか気になる
  最近学び始めたところで、この分野は魅力的だ
  https://www.peakmath.org/quest-for-f1 の動画で知って、http://lmfdb.org も探索してみる価値がある

• この事実は 37 をかなり面白い数にしていると思う
  少なくとも 31 よりは確実に面白い
  31 も素数なのでそれなりに面白いが、いま知ったように整数の第 2 素因数の中央値である 37 ほどではない
  もっと面白い整数の候補はあるだろうか？ そして「最も面白い整数」と呼べる数は存在するのだろうか？

  • 数学者たちは、加法単位元 0 こそ真の基盤であり最も面白い整数だと信じる Zeroastrian と、乗法単位元を重視して 1 を擁護する Unitarian との激しい闘争に囚われている。この二つの陣営の衝突で、数え切れないほどの魂が失われてきた
  • 「最も面白い整数」なら、664571016291591957042161991109590159107314773607 と 590488317782859198927092718316232684864014739572 が該当すると思う
    それぞれ ASCII 文字列 “the most interesting” のビッグエンディアン版とリトルエンディアン版だ
  • https://en.wikipedia.org/wiki/Interesting_number_paradox
  • 素数が持ちうるもう 1 つの特別な性質は 非正則性 だ。最初の非正則素数が何か当ててみると 37 だ
    非正則素数は全素数の約 41% を占めるのに、最初の出現がこんなに遅いのは面白い。参考: https://encyclopediaofmath.org/wiki/Irregular_prime_number#:~:text=An%20odd%20prime%20number%20p,prime%20numbers%20are%20called%20regular
    最も面白い素数が何かは、何をより面白いと感じるかによる。第 2 素因数の中央値が好きなら 37 が最高だし、最初の非正則素数が好きでも 37 が最高だ。結局は観点の問題だ
    37 が良いもう 1 つの理由は 7 で終わるので、誰かに数字を 1 つ言えと言われたとき「ランダムっぽく聞こえる」ことだ。27 より良いのは素数だからでもある。7 は低すぎるし、17 には不吉なニュアンスがある。ただし 37 もかなり怖い数だ。ただの素数というだけでもかなり不規則なのに、非正則素数でもあるのだから
  • 歴史的には 60 を挙げたい。大きさの割に約数が多く（12 個）、その中に 2, 3, 4, 5, 10 のような便利な約数が多いからだ
    だから時間体系や三角法はたぶん 60 を基準にしたのだろう。360 = 6*60 で、360 の約数は 24 個ある

• 証明がこんなに単純だとは驚きだ。37 が新しい 推し素数 になった

• 第 2 素因数の 平均値の増加率 はどうなるのか気になる。無限に大きくなりそうではあるが、かなりゆっくり増えるのかもしれない

• 一生この数字に取り憑かれてきた。時計を見るたび、前の車のナンバープレートを見るたびに 37 が目に入る気がする
  Channel 37 みたいに、ほかにもいろいろランダムに関連するものがある: https://en.wikipedia.org/wiki/Channel_37