Home　～いわゆる窓口，あるいは単にかっこつけたいがために～

お知らせ

  1. twitterやってるよ。テキトにfollow Mishoすると良いよ！mixiは嫌いだけど，個人情報収集目的でつかってるよ！
  2. みしょの2chでのトリップは◆NEE3osS53Q and ◆SmHACKPhYsなんだＺＥ☆ 嘘を嘘(ry

最新の日記 - 2008.08.20

Tags:  数学  Algorithm

Permanent Link: http://www.misho-web.com/diary/200808.html#Diary20

11以下の素因数を持つ携帯電話番号には価値がない。

4日ほど前，朝起きてもごもごしていたら，突然，「僕の携帯電話の番号は素数なのではないか？」という着想が降ってきました。実際，2でも5でも割り切れないし，3でも割り切れない。頑張って暗算した結果，7でも11でも13でも割り切れない。……これは！！

というわけで即興でPerlで素数判定program（'Ερατοσθένης）を作って計算した結果，残念ながら素数ではありませんでした。でも，最小の素因数が113だったので，それなりに「選ばれた」番号だった，ということでうれしかったのです。

ちなみにLakiの番号は偶数らしいです。ｹﾞﾗｹﾞﾗｹﾞﾗｹﾞﾗｹﾞﾗｹﾞﾗ。11以下の素因数を持つ携帯電話番号には興味ありません！！！！！！！

Do Keitai-Numbers Dream of Primes?

さて，そんなわけでボケっとしていたら，ymonさんが興味深い問題を出してきました。

携帯電話で下四桁が自由に選べるけど、８桁の数字で下四桁が選べる場合、一番素数率の高い下四桁は何だろう。

……なんだろう。そう思って調べてみました。

Algorithmはやはり'Ερατοσθένηςの方法。Fermat testで枝刈りしても大して時間は変わらないだろう，と思ったので'Ερατοσθένηςでやったのですが，なんか計算に4～5時間を要したので，やっぱりFermatか何かしたほうがよかったかな，と今では思っています。

そんなことより，結果発表。

  1. 下位8桁に絞って考えた場合
    • 素数となりうる数は4002種類でした。
    • 第1位は，0083でした。1520種あるので，素数になる確率は15.20%です。
    • 以下，9453(15.06%)，2051(15.05%)，9659(15.04%)，7873(15.01%)と続きます。
    • 当たり前ですが，最下位(4001位)は0002および0005(0.01%)です。
    • 2と5を除いた下位5種は，順に0943(13.75%)，3163(13.72%)，8587(13.71%)，8331(13.69%)，2057(13.67%)です。

    • 第4000位は，2057(13.67%)でした。
  2. 11桁すべてについて考えたとき，080から始まる場合
    • 第1位：7697(11.74%)
    • 第2位：4189(11.73%)
    • 第3位：4783および4011(11.71%)
    • 第5位：9671および6051(11.65%)
    • 第3996位：7003(10.27%)
    • 第3997位：1533(10.26%)
    • 第3998位：9351(10.22%)
    • 第3999位：7867(10.15%)
    • 第4000位：3157(10.09%)
  3. 11桁すべてについて考えたとき，090から始まる場合
    • 第1位：8391(11.86%)
    • 第2位：5469(11.69%)
    • 第3位：1703(11.63%)
    • 第4位：6887および6187(11.62%)
    • 第3994位：7141・2951・9453(10.20%)
    • 第3997位：3573(10.18%)
    • 第3998位：3883(10.17%)
    • 第3999位：3973(10.14%)
    • 第4000位：4969(10.08%)

Mystic Primes

というわけでここで僕からも問題です。

まずは数学的な問題。

  • 080および090の場合，素数となりうる下四桁は，4000個でした。これは偶然でしょうか？それとも当然でしょうか？
  • 第1位と第4000位の間には，ほとんど差がありません(1.8%=180個程度）。なぜでしょう。
  • 素数率は，(1) (2) (3)の順に低くなっています。なぜですか。
  • ある数 N の付近の素数率はだいたいどれくらいでしょう？たとえば，9000000000付近では大体11%程度のようです。
  • ある数 N の付近の素数率は，Nに対して単調減少します。これは 0 に収束するのでしょうか？それとも別の値に収束するのでしょうか？

そして，情報科学的な問題。

  • この問題に対して，'Ερατοσθένηςの方法よりも実用上早いalgorithmを構成してください。

最後に，おあそび的な問題。

  • 僕の電話番号は080から始まります。最初に僕は，自分の携帯電話の番号が13以下の素因数を持たないことを暗算で確認し，「これはマジで素数じゃないか？」と考えました。この期待はどれくらい正しかったのでしょうか？すなわち，80で始まる10桁の自然数が13以下の素因数を持たない場合，それが素数である確率はいくらでしょうか？
  • 僕の携帯電話番号は113未満の素因数を持ちません。これはどの程度すばらしい電話番号なのでしょう？つまり，80から始まる10桁の自然数について，113未満の素因数を持たないものはどれくらいあるでしょうか？

3番目の問題については回答を持っていますが，それ以外については答えを知りません。誰か教えてください。

Comments

Commented by keno42  at  2008/08/20(Wed) 17:43:18

【削除】

おあそび問題はこんな方向でどうでしょう。

13より大きい数Nについて、それが13までの素因数を持たない可能性は

1・1/2・2/3・4/5・…・12/13~0.192になります。

N近辺の数の素数の密度(素数である可能性)は漸近的に1/log(N)なので、N=8*10^10とするとNが大きいからだいたい正しかろうとして、これがおよそ0.043。

(素数である可能性)/(13までの素因数を持たない可能性) = およそ22.4%

が、13までの素因数を持たない数N(~8*10^10)が素数である確率であると言えます。

1/log(N)がN=10桁 近辺でどのくらい誤差あるかはわかりません！

あと113うんぬんについては、

1・1/2・2/3・4/5・…・108/109~0.115なので、まあこの割合なのではないでしょうか。

< Commentを書き込む >

[Trackback URL : http://www.misho-web.com/diary/Trackback/20080820]

最近のComment / Trackback

更新履歴

2008.04.29
Twitter Timelineを載っけるなどした。
2008.03.09
Designをちょっと変更などした。
2008.01.14
Contents Management Systemを作った。
2007.09.06
こっそり本棚を作ってみた。
2007.06.16
もうみんないい加減飽きただろうから，Introductonをちょこっとだけ更新したんだＺＥ☆
2007.02.20
Peskin seminarのpageを作ったよ！Résuméとかも載っけてみた。
2007.02.20
物理のpageを久しぶりに更新。
2006.04.01
April fool☆
2006.02.11
物理のpageを作ってみたｗ
2005.04.24
日記に，2005年01月と02月のを追加。それ以前はまだ整形が終わってません……。
2005.04.15
Top pageの一番上の"since"が間違ってた！！！ので訂正！
2005.04.12
日記に，comment機能を実装。Trackback機能を拡張。
2005.03.28
『Cetera』を開設。
2005.03.26
Top pageの『ごあいさつ』を，削除。（特に存在価値が無かったためｗ）
2005.03.21
Designを一新!!

Contents紹介

Homeこのpageです。いわゆるtop pageってやつ。それ以上でもそれ以下でもない。
Introductionこのweb siteの説明とか，あるいは僕の自己紹介とか。「100質」もここに掲載する予定……だった。
Diary最も更新頻度の高いcontent。「美翔の徒然日記」とかいう題名だったはず。
Physicsぶちゅりのぺーじ。Seminarの特設pageだとか……今後はここの更新が多分主だろうなぁ。
TechsTechtalksとか，作ったtoolsなどの置き場。
Bookshelfみしょの本棚。物理，生物情報，語学，……などなど。比較的更新されてる。
Cetera以上のもの以外のもの。OthersだとかAndereだとかいう別名ももつ。
.