スラッシュドット・ジャパン

# 2進数ネタは本家で書かれてしまったので、まじめに書く。

素数は、大きな数の領域になるほどに分布が疎らになっていきます。ということで、ある桁数の数についてみれば、1xxxxx の素数よりは、9xxxxx の素数のほうが少ないだろう、という見込みはなんとなくありそうに思えます。で、問題は

最高桁が「1」である数値は全体の約30%、「2」であるものは約18%、「3」であるもの約12%･･･「9」であるものは約5%という割合になっている

という法則に従うかどうか。

大まかな素数の分布を知るための式（素数定理）の簡単なものに、π(n) ≒ n/ln(n) があります。ここでいう"π(x)"は、円周率ではなく素数計数関数です。（x以下の個数の数を表す。ex. π(10) = 4 {2,3,5,7} ≒ 10/ln(10) [google.co.jp]）

この式を使って、小さな（google電卓で届くような）数の領域について、素数の数をみてみると…

- 9桁の数の場合:
1で始まる (199 999 999 / ln(199 999 999)) - (100 000 000 / ln(100 000 000)) = 5 034 947.71 [google.co.jp]
2で始まる (299 999 999 / ln(299 999 999)) - (200 000 000 / ln(200 000 000)) = 4 905 780.27 [google.co.jp]
        :
9で始まる (999 999 999 / ln(999 999 999)) - (900 000 000 / ln(900 000 000)) = 4 603 563.36 [google.co.jp]

# 1のケタで誤差がある計算式だけど気にしないでください。
# （もともと正確な近似式ではありません）

うーん、いまいち「法則」に合致しません。数が小さすぎるかな？　ようし、某コミック並みに戦闘力インフレさせて界王拳1000倍だ！

- 12桁の数の場合:
1で始まる (199 999 999 999 / ln(199 999 999 999)) - (100 000 000 000 / ln(100 000 000 000)) = 3.73779577 × 10⁹ [google.co.jp]
2で始まる (299 999 999 999 / ln(299 999 999 999)) - (200 000 000 000 / ln(200 000 000 000)) = 3.66607816 × 10⁹ [google.co.jp]
        :
9で始まる (999 999 999 999 / ln(999 999 999 999)) - (900 000 000 000 / ln(900 000 000 000)) = 3.49444386 × 10⁹ [google.co.jp]

すごく…大きいです。でもやっぱり、1xxxが2xxxの2倍近いくらいになるような、明確な違いは出ないですねえ。というより、比は均等に近くなっているような？

もっと巨大な数の領域になると法則に従うのでしょうか。（なんだか、もっと均等になりそうなヨカン）
それとも、私がなにか勘違いしているのでしょうか。数論詳しい方ツッコミお願いします。

#1564761 [slashdot.jp] の人が紹介してくれている arXiv 版の一部を読みました。ジャーナル版では内容が異なる可能性があります。

論文では、素数の先頭桁の分布がある意味で generalized Benford's law という法則に従っていることを示しているようです。 generalized Benford's law は Benford's law の一般化であり、 Benford's law そのものではありません。 generalized Benford's law とは何かとか、「ある意味で」とはどういう意味かとかは、僕には説明できません。知りたければ論文を読んでください。

証明でない実験的証拠がいろいろ並んでいて、「proof」と書かれた部分がないので自信がないのですが、 4 節 (b) が証明なのではないかと思います。

数学はまったくの門外漢で、タレコミにある「ベンフォードの法則」の解説だけ読みましたが……
素数の最後の数がわかっていない（最後が存在しない）以上、現時点で把握している数字が「ベンフォードの法則」っぽい割合になるのは当然なんじゃないですか？

この「法則」ってルーレット定理とどう違うの？

うろ覚えでもうしわけないが、学生時分に読んだ森毅「微積分の意味」にこの最高桁の数の話が出ていて、すくなくとも1930年代とかの話題ではなかったよ。帰宅して覚えていたら補足を書きます。

(PDF注意)
ベンフォードの法則って、不正経理の発見 [izumi-math.jp]などにも役立つんだな。

とりあえず、手計算で出来る範囲（10以下）で試してみたところ、1で始まる素数は1つもありませんでした。

# 心が落ち着きました。

試しにプログラムを書かれる方がいるかと思いますので参考まで

以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。

フルイの分割というのは、フルイの対象とする範囲を、例えば

2～10^8
10^8～2*10^8
2*10^8～3*10^8
  ....
99*10^8～100*10^8

とか分割します。分割したそれぞれに対してフルイを実行します。

（分割の単位は例です。分割の単位はベンチ行って最適化してください。）

途中の数からフルイを計算をはじめるためには、素数の表を持っておく必要があります。10^10までフルイを実行するには10^5までの素数表を持っておけばいいです。これはあらかじめ作る必要はなく、最初の2～10^8のフルイ実行時の結果を記憶しておけばいいです。

というような工夫をすれば、AMD Opteron 1216で10^10までのフルイは3分7秒、10^11までは34分7秒で実行出来ました。

なおメモリ節約のため上記のような分割ではなく、bit単位でのアクセス、2/3/5の倍数を例外扱いなどをしてメモリ節約される方もいるかもしれませんが、かなりペナルティが高いです。10^10までのフルイで24分57秒、10^11までのフルイで230分16秒という結果になりました。