みしょのねこごや

Tags:  数学  Algorithm

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

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

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

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

---

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番目の問題については回答を持っていますが，それ以外については答えを知りません。誰か教えてください。