パスワードを忘れた? アカウント作成
94427 story
数学

素数の分布は「ベンフォードの法則」に従っている 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」あたりに詳しい説明が載っているので興味があれば是非。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • # 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 × 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倍近いくらいになるような、明確な違いは出ないですねえ。というより、比は均等に近くなっているような?

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

    • by Anonymous Coward on 2009年05月13日 17時18分 (#1564500)
      本家に、素数詰め合わせ [utm.edu]と 分布の表とグラフ [google.com]がありましたので、自分で検証したい人たちはお使い下さい。
      親コメント
    • 詳細までは突っ込めませんが、ベンフォードの法則についての理解が間違っていると思います。

      タレコミ文にあるリンク先を見てみれば分かりますが、1から10nまでの数字を対象としたとき、nが整数であれば各数字の出現頻度はほぼ均一になります。ですので、素数がベンフォードの法則にしたがっているのであれば、nが整数の時、ほぼ均一です。しかし、上限に10の乗数以外の数字を取ると、振動して、収束しません。例えば、上限を2×10nとすれば、1の出現率が極端に上昇します。

      ベンフォードの法則が対象としている数字には特定の上限がないわけで、必ずしも10の乗数といった上限が存在しない自然発生的な数字に当てはまることが多いわけです。

      親コメント
      • 詳細までは突っ込めませんが、ベンフォードの法則についての理解が間違っていると思います。

        どうもそこが「なにか勘違いしているのでしょうか」の源だったようです。

        ようワカランのに証明のほうばかり読もうとして、タレコミで親切にも日本語コンテンツがリンクされているのにそこまで読んでいなかったというオチでした。
        (最初のコメントに書いた素数の分布自体が間違いなのではなくて、法則の理解のほうの問題)

        # リーマンらしく、金融危機に乗じて玉砕してきます…。λ ...

        親コメント
      • by kawa-t (37052) on 2009年05月14日 1時19分 (#1564756) 日記
        「10の乗数」は「10のべき乗」と読み替えてください。

        すみません。
        親コメント
    • by Anonymous Coward

      「9桁の数」とか値の範囲を制限したらそうなるに決まってます。
      たとえば100 000 000~199 999 999までの範囲に含まれる素数の分布を調べたら1で始まるものが100%になります。

    • by Anonymous Coward
      > (199 999 999 / ln(199 999 999)) - (100 000 000 / ln(100 000 000))
      これだと10 000 000台の数は減算されちゃってるような。
      • 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%になる、というのがベンフォードの法則の直感的な説明です。

        親コメント
        • それ以外のいかなる上限を選んでも、1で始まる数の出現率が他の数で始まる数より低くなることはありません。

          素数は無限にあるので、この証明ではそもそも「上限」を設定せず、素数全体の集合を相手に「無作為に数をとってくる」ような操作をしているのではないのか、とまあ、そのあたりが疑問だったわけです。

          論文の後半(Appendix)にそのあたりのことが書かれているのですが、前提知識が足りてなくて理解がいま一つ。

          親コメント
          • by Anonymous Coward

            はい、ですから(証明ではなく)直感的説明だと申し上げました。#1564457 [srad.jp]のように、恣意的に範囲を設定すればいくらでも不適切な結論を導けるということを示すのが目的です。

            > 「上限」を設定せず、素数全体の集合を相手に
            無限の数の集合に対していきなり性質を述べたりするのが困難な場合、数学的帰納法や極限操作によって結論を導いたりするのはごく普通のやり方です。

            もう少し単純化した例を挙げてみます。{1, -1, 1, -1,

    • by Anonymous Coward
      "The first-digit frequencies of prime numbers and Riemann zeta zeros" でググるとそのもののPDFが出てくるね
    • by Anonymous Coward

      これは、しがない リーマン [wikipedia.org]ってのが笑うところ?

  • #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, 興味深い)

    by Anonymous Coward on 2009年05月13日 16時20分 (#1564458)

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

    • Re:当然? (スコア:2, 参考になる)

      by Anonymous Coward on 2009年05月13日 18時42分 (#1564543)

      門外漢ですが、素数というのは数そのものを構成する特別な数ですけど
      出現頻度はランダムに数字を取ってきたのと変わらないようだぞ?
      ということが分かった、というのが収穫なんじゃないですかね。
      特別らしいことを期待させる性質の1つが消えた、という意味で。

      親コメント
      • by Anonymous Coward

        出現頻度はランダムに数字を取ってきたのと変わらないようだぞ?

        数については門外漢ですが、「ランダム」ってことが
        対数軸に対してモンテカルロシミュレーション(←変な表現)ってのが納得いかないです。

        なぜ、普通の軸に対してモンテカルロじゃないの?
        10の対数なのはなぜ?(まあ、十進数を選んだ人間の体の構造のせいでしょうけど)

    • by yousuke78jp (32474) on 2009年05月13日 17時13分 (#1564492)
      ベンフォード則は値の範囲が制限されていない時に成立するので、最後が存在しないからこそ成り立ちます。
      親コメント
    • by Anonymous Coward

      なんで当然なんですか?
      本気でわかりません。
      宜しければ追加の説明をして下さい。

      • Re:当然? (スコア:1, 参考になる)

        by Anonymous Coward on 2009年05月13日 20時34分 (#1564608)

        別ACだけど、素数の出現には周期性その他の法則がまだ見つかっていないし
        今のところ整数から一様に出現しているように見えるので
        だとすれば、元の整数列と同じようにベンフォードの法則に従うのは当然……と考えても不思議はない

        ただ、法則性は見つかっていないけれど、法則性が無いという事も明らかになってるわけではないので
        「今のとこ、一様っぽいね。ベンフォードで見てもそうなった」
        というのは、当然以上の価値があるんじゃないかな。

        親コメント
    • by Anonymous Coward
      10のべき乗の列(10, 100, 1000, 10000, …)には最後が存在しませんが、ベンフォードの法則には従いません。
  • by Anonymous Coward on 2009年05月13日 16時35分 (#1564469)

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

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

    • by prankster (12979) on 2009年05月13日 17時16分 (#1564498)
      素人ですが。

      これ(注、PDF) [izumi-math.jp]によると同じ現象の別の説明法のように思えます。
      親コメント
    • by Anonymous Coward
      E系列を思い出すなぁ。
    • by Anonymous Coward

      ひさびさに「微積分の意味」を読んでみた。

      ●なぜ数の最初は1や2が多いか
      対数を使ったおもしろい例がフェラーの本に書いてある。都市の人口とか、国家の財政とか、数字が並んでいることがよくあるが、最初には1や2が出てくることが多く、8や9はめったに出ないのはなぜか。
      <中略>
      これには、ポアンカレのルーレット定理を使う。

      ということで
      > すくなくとも1930年代とかの話題ではなかったよ。
      とか書きましたがフェラー(1906-1970)の本(たぶん「確率論とその応用」でしょう)いうことで年代的に、ベンフォードの法則のほうが遅いという明確な証拠ではないことがわかりました。

      ベンフォードさん疑ってごめんね。

  • by tomokine (37450) on 2009年05月14日 1時28分 (#1564761)
    arXiv で全文が読めますよ.
    読みたい方はどうぞ.
    http://arxiv.org/abs/0811.3302 [arxiv.org]
  • by Anonymous Coward on 2009年05月13日 16時06分 (#1564451)

    こんな法則があったことすら知らなかった。

    • by Anonymous Coward on 2009年05月13日 16時48分 (#1564480)

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

      親コメント
      • by Anonymous Coward
        古来から嘘の五三八と言って…

        うえのリンク先にはルーレット定理による説明もでてますね。
    • 地図帳を開いて、国の面積や人口の数字の一番上の桁を見ると、
      なぜか1や2が多くて6,7,8,9は少ないというアレですね。
      親コメント
    • by Anonymous Coward
      俺も知らんのだが、大きい数は(その数の大きさに比べて)なんとなく少ないということけ?
      • by Anonymous Coward
        計算機科学的には、計算機内で浮動小数を扱う際に、基数が2である事が他の基数(16とか)よりも有利な理由の一つですね。
        ケチ表現(economized form)で桁を稼げるのは超重要だけど。

        # 使い込まれた対数表は最初の方の頁が汚れるらすぃ(Newcombせんせーによれば)。
      • by Anonymous Coward
        計算尺をじーっと見つめていたら、なんとなくわかったつもりになった
  • by Anonymous Coward on 2009年05月13日 17時54分 (#1564513)
    これほどコンピュータ向きの題材は無いんでは?

    みんな、すぐに手元のコンピュータで確認してみるんだ

    エラトステネスの篩をアレンジしたプログラムなんかは簡単に作れるよね
    • by TarZ (28055) on 2009年05月13日 18時03分 (#1564517) 日記

      とりあえず、手計算で出来る範囲(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秒という結果になりました。

      親コメント
    • by Anonymous Coward
      誰もやっていない様なので、簡単なのやってみた。

      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%

      ちなみに、素数の出現率ではなく、素数の出現率の和です、念のため。
      • by Anonymous Coward
        × 出現率の和
        ○ 出現数の和の割合

        あと、9の割合って減って行く様な気がするが、
        桁を上げて行くと増えて行くんですよね。不思議。
typodupeerror

普通のやつらの下を行け -- バッドノウハウ専門家

読み込み中...