素数の分布は「ベンフォードの法則」に従っている 48
ストーリー by hylom
初耳 部門より
初耳 部門より
あるAnonymous Coward 曰く、
素数の出現パターンは「ベンフォードの法則」に従っていることが分かったそうだ（本家記事）。
「ベンフォードの法則」とは、ある数値群をみたとき、最高桁が「1」である数値は（15や189や1088など）は全体の約30%、「2」であるものは約18%、「3」であるもの約12%･･･「9」であるものは約5%という割合になっているという法則である。この法則は物理学者フランク・ベンフォードが1938年に発見した分布法則であり、市場分析や不正検出アルゴリズムなどにも応用されているものである。
スペインの数学者がBartolo LuqueとLucas Lacasaは素数にもこの法則が当てはまることをこの度解明したそうだ（論文要旨）。
ベンフォードの法則って何？という方もいらっしゃるかと思うが、日本語であれば「はまぐりの数学」、英語であればWikipediaの項目「Benford's law」あたりに詳しい説明が載っているので興味があれば是非。
【新ジャンル】しがないリーマンのオレが、ヘタレな数の領域で【計算してみた】 (スコア:4, 参考になる)
# 2進数ネタは本家で書かれてしまったので、まじめに書く。
素数は、大きな数の領域になるほどに分布が疎らになっていきます。ということで、ある桁数の数についてみれば、1xxxxx の素数よりは、9xxxxx の素数のほうが少ないだろう、という見込みはなんとなくありそうに思えます。で、問題は
という法則に従うかどうか。
大まかな素数の分布を知るための式（素数定理）の簡単なものに、π(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 × 109 [google.co.jp]
2で始まる (299 999 999 999 / ln(299 999 999 999)) - (200 000 000 000 / ln(200 000 000 000)) = 3.66607816 × 109 [google.co.jp]
:
9で始まる (999 999 999 999 / ln(999 999 999 999)) - (900 000 000 000 / ln(900 000 000 000)) = 3.49444386 × 109 [google.co.jp]
すごく…大きいです。でもやっぱり、1xxxが2xxxの2倍近いくらいになるような、明確な違いは出ないですねえ。というより、比は均等に近くなっているような？
もっと巨大な数の領域になると法則に従うのでしょうか。（なんだか、もっと均等になりそうなヨカン）
それとも、私がなにか勘違いしているのでしょうか。数論詳しい方ツッコミお願いします。
計算に必要な材料 (スコア:2, 参考になる)
Re:【新ジャンル】しがないリーマンのオレが、ヘタレな数の領域で【計算してみた】 (スコア:1)
詳細までは突っ込めませんが、ベンフォードの法則についての理解が間違っていると思います。
タレコミ文にあるリンク先を見てみれば分かりますが、1から10nまでの数字を対象としたとき、nが整数であれば各数字の出現頻度はほぼ均一になります。ですので、素数がベンフォードの法則にしたがっているのであれば、nが整数の時、ほぼ均一です。しかし、上限に10の乗数以外の数字を取ると、振動して、収束しません。例えば、上限を2×10nとすれば、1の出現率が極端に上昇します。
ベンフォードの法則が対象としている数字には特定の上限がないわけで、必ずしも10の乗数といった上限が存在しない自然発生的な数字に当てはまることが多いわけです。
タレコミのリンク先は、最後のものから先に読めの法則 (スコア:2)
どうもそこが「なにか勘違いしているのでしょうか」の源だったようです。
ようワカランのに証明のほうばかり読もうとして、タレコミで親切にも日本語コンテンツがリンクされているのにそこまで読んでいなかったというオチでした。
（最初のコメントに書いた素数の分布自体が間違いなのではなくて、法則の理解のほうの問題）
# リーマンらしく、金融危機に乗じて玉砕してきます…。λ ...
自己レス (スコア:1)
すみません。
Re: (スコア:0)
「9桁の数」とか値の範囲を制限したらそうなるに決まってます。
たとえば100 000 000～199 999 999までの範囲に含まれる素数の分布を調べたら1で始まるものが100%になります。
Re: (スコア:0)
これだと10 000 000台の数は減算されちゃってるような。
Re:【新ジャンル】しがないリーマンのオレが、ヘタレな数の領域で【計算してみた】 (スコア:3, 参考になる)
9桁の数について調べているのですから、10 000 000台は除外する必要があるに決まっています。問題はそこではありません。
(n桁以下の数の分布)=(n桁の数の分布)+(n-1桁の数の分布)+...+(1桁の数の分布)ですから(2例しか計算してませんけど)どの数で始まる素数の出現率もだいたい同じなんじゃね? と言いたいのでしょう。
この論法の最大の問題は、1で始まる数にとってもっとも不利な、出現率が均等になるような上限(99,999,9999,...)ばかりを(おそらく自覚なしに)恣意的に選んでいることです。1で始まる数にとってもっとも有利な上限(19,199,1999,...)ばかりを選べば「1で始まる素数の出現率はだいたい50%」という結論になります。
1で始まる数の出現率は、もっとも不利な場合ですら他の数字で始まる数と均等であるることに注意してください。それ以外のいかなる上限を選んでも、1で始まる数の出現率が他の数で始まる数より低くなることはありません。もっとも有利な場合には50%を超えます。それらをならした場合に1で始まる数の出現率がだいたい30%になる、というのがベンフォードの法則の直感的な説明です。
Re:【新ジャンル】しがないリーマンのオレが、ヘタレな数の領域で【計算してみた】 (スコア:2)
素数は無限にあるので、この証明ではそもそも「上限」を設定せず、素数全体の集合を相手に「無作為に数をとってくる」ような操作をしているのではないのか、とまあ、そのあたりが疑問だったわけです。
論文の後半(Appendix)にそのあたりのことが書かれているのですが、前提知識が足りてなくて理解がいま一つ。
Re: (スコア:0)
はい、ですから(証明ではなく)直感的説明だと申し上げました。#1564457 [srad.jp]のように、恣意的に範囲を設定すればいくらでも不適切な結論を導けるということを示すのが目的です。
> 「上限」を設定せず、素数全体の集合を相手に
無限の数の集合に対していきなり性質を述べたりするのが困難な場合、数学的帰納法や極限操作によって結論を導いたりするのはごく普通のやり方です。
もう少し単純化した例を挙げてみます。{1, -1, 1, -1,
Re: (スコア:0)
Re: (スコア:0)
これは、しがない リーマン [wikipedia.org]ってのが笑うところ?
ベンフォードの法則そのものではない (スコア:2)
#1564761 [srad.jp] の人が紹介してくれている arXiv 版の一部を読みました。ジャーナル版では内容が異なる可能性があります。
論文では、素数の先頭桁の分布がある意味で generalized Benford's law という法則に従っていることを示しているようです。 generalized Benford's law は Benford's law の一般化であり、 Benford's law そのものではありません。 generalized Benford's law とは何かとか、「ある意味で」とはどういう意味かとかは、僕には説明できません。知りたければ論文を読んでください。
証明でない実験的証拠がいろいろ並んでいて、「proof」と書かれた部分がないので自信がないのですが、 4 節 (b) が証明なのではないかと思います。
当然？ (スコア:1, 興味深い)
数学はまったくの門外漢で、タレコミにある「ベンフォードの法則」の解説だけ読みましたが……
素数の最後の数がわかっていない（最後が存在しない）以上、現時点で把握している数字が「ベンフォードの法則」っぽい割合になるのは当然なんじゃないですか？
Re:当然？ (スコア:2, 参考になる)
門外漢ですが、素数というのは数そのものを構成する特別な数ですけど
出現頻度はランダムに数字を取ってきたのと変わらないようだぞ？
ということが分かった、というのが収穫なんじゃないですかね。
特別らしいことを期待させる性質の1つが消えた、という意味で。
Re: (スコア:0)
出現頻度はランダムに数字を取ってきたのと変わらないようだぞ？
数については門外漢ですが、「ランダム」ってことが
対数軸に対してモンテカルロシミュレーション（←変な表現）ってのが納得いかないです。
なぜ、普通の軸に対してモンテカルロじゃないの？
10の対数なのはなぜ？（まあ、十進数を選んだ人間の体の構造のせいでしょうけど）
Re:当然？ (スコア:1)
Re: (スコア:0)
なんで当然なんですか？
本気でわかりません。
宜しければ追加の説明をして下さい。
Re:当然？ (スコア:1, 参考になる)
別ACだけど、素数の出現には周期性その他の法則がまだ見つかっていないし
今のところ整数から一様に出現しているように見えるので
だとすれば、元の整数列と同じようにベンフォードの法則に従うのは当然……と考えても不思議はない
ただ、法則性は見つかっていないけれど、法則性が無いという事も明らかになってるわけではないので
「今のとこ、一様っぽいね。ベンフォードで見てもそうなった」
というのは、当然以上の価値があるんじゃないかな。
Re: (スコア:0)
法則って言われても・・・ (スコア:1, 興味深い)
この「法則」ってルーレット定理とどう違うの？
うろ覚えでもうしわけないが、学生時分に読んだ森毅「微積分の意味」にこの最高桁の数の話が出ていて、すくなくとも1930年代とかの話題ではなかったよ。帰宅して覚えていたら補足を書きます。
Re:法則って言われても・・・ (スコア:3, 興味深い)
これ(注、PDF) [izumi-math.jp]によると同じ現象の別の説明法のように思えます。
電気屋的には (スコア:0)
Re: (スコア:0)
ひさびさに「微積分の意味」を読んでみた。
ということで
> すくなくとも1930年代とかの話題ではなかったよ。
とか書きましたがフェラー(1906-1970)の本(たぶん「確率論とその応用」でしょう)いうことで年代的に、ベンフォードの法則のほうが遅いという明確な証拠ではないことがわかりました。
ベンフォードさん疑ってごめんね。
FullText (スコア:1)
読みたい方はどうぞ.
http://arxiv.org/abs/0811.3302 [arxiv.org]
ベンフォードの法則 (スコア:0)
こんな法則があったことすら知らなかった。
Re:ベンフォードの法則 (スコア:1, 興味深い)
(PDF注意)
ベンフォードの法則って、不正経理の発見 [izumi-math.jp]などにも役立つんだな。
Re: (スコア:0)
うえのリンク先にはルーレット定理による説明もでてますね。
Re:ベンフォードの法則 (スコア:1)
なぜか1や2が多くて6,7,8,9は少ないというアレですね。
Re: (スコア:0)
Re: (スコア:0)
ケチ表現(economized form)で桁を稼げるのは超重要だけど。
# 使い込まれた対数表は最初の方の頁が汚れるらすぃ(Newcombせんせーによれば)。
Re: (スコア:0)
こ、これは (スコア:0)
みんな、すぐに手元のコンピュータで確認してみるんだ
エラトステネスの篩をアレンジしたプログラムなんかは簡単に作れるよね
落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:5, おもしろおかしい)
とりあえず、手計算で出来る範囲（10以下）で試してみたところ、1で始まる素数は1つもありませんでした。
# 心が落ち着きました。
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:3, 興味深い)
もうちょっと頑張って20以下まで調べてみたところ、1で始まる素数の出現率は50%でした。
# だんだんわかってきました?
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:4, おもしろおかしい)
自分の限界に挑戦すべく30以下まで調べてみたところ、1で始まる素数の出現率は40%でした。
// むむっなにか掴みかけてきたぞっ(:>^
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:2)
直感的には桁の限界までの範囲で全部数えれば、どれも1/9、つまり11％になりそうな気がした。素数は違うか。
999までの範囲で数えてみた。
1：25 （0.149）
2：19 （0.113）
3：19 （0.113）
4：20 （0.119）
5：17 （0.101）
6：18 （0.107）
7：18 （0.107）
8：17 （0.101）
9：15 （0.089）
次に9999までの範囲で数えてみた。
1：160 （0.130）
2：146 （0.119）
3：139 （0.113）
4：139 （0.113）
5：131 （0.106）
6：135 （0.109）
7：125 （0.101）
8：127 （0.103）
9：127 （0.103）
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:1)
> ##ベストエフォートより、リーストエフォット
ベンフォードより... と空目した。
Re: (スコア:0)
# 末尾が2の素数なんて
Re:落ち着け！ 素数を数えて落ち着くんだ！ 2, 3, 5... (スコア:2)
＞ 末尾が2の素数なんて
お前は1個あるだけマシじゃないかと、4,6,8は声をそろえて言いました。
可哀そうな、0 はどちらからも相手にされませんでした・・・
エラトステネスの篩で参考 (スコア:5, 参考になる)
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、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秒という結果になりました。
Re:エラトステネスの篩で参考 (スコア:2, おもしろおかしい)
Re:エラトステネスの篩で参考 (スコア:1)
言語は何で書きましたか？
Re:エラトステネスの篩で参考 (スコア:2)
Re: (スコア:0)
3や5でペナルティが大きいのはなんとなく分かる気がします。
しかし2は単純な論理積演算で検証が可能ですが、それでも
ペナルティは大きいんですか？
Re:エラトステネスの篩で参考 (スコア:2)
2/3/5でそれぞれ比較は行っていませんが、10^9までの計算で
次のような結果になっています。(10^10までは行ってません)
bit単位のアクセスでメモリ節約: 2分20秒
bit単位のアクセスに加えて2/3/5の例外扱いでメモリ節約: 2分59秒
したがって2/3/5の例外扱いでペナルティが高いは大げさでした。
bit単位でのアクセスはペナルティが高いに修正します。
なお、2/3/5の例外扱いのために次のような読み替えテーブル
を使ってます。説明は省きますが2/3/5の最小公倍数は30です
ので、大体意味わかると思います。
static const int_fast32_t yomikae_table[30]=
{-1, 0,-1,-1,-1,-1,-1, 1,-1,-1,
-1, 2,-1, 3,-1,-1,-1, 4,-1, 5,
-1,-1,-1, 6,-1,-1,-1,-1,-1, 7};
Re: (スコア:0)
100万は64ビットでも桁あふれしたので、10万まで。
1 20.54%
2 17.45%
3 15.01%
4 12.78%
5 10.70%
6 8.61%
7 6.79%
8 4.94%
9 3.18%
ちなみに、素数の出現率ではなく、素数の出現率の和です、念のため。
Re: (スコア:0)
○ 出現数の和の割合
あと、9の割合って減って行く様な気がするが、
桁を上げて行くと増えて行くんですよね。不思議。