Q. しんごさんからの疑問
今年は、2011年ですから、11月11日になると、「１」が６つも並ぶことになります。切符でも買いに行こうかなと思っています。
そこで、ふと思ったのですが、20111111は、素数ですか？
順番に割っていけば、約数が見つかるかもしれません。２桁の数はチェックしたのですが、20111111の約数ではありませんでした。
もっと調べるにはパソコンの力を借りればよいのでしょうが、残念ながら、私はそういうのが苦手なんです。
どなたか教えてくださいませんか？
★素数か、素数でないか――ただ、それだけの疑問です。
ぜひ、関連事項を教えていただけると盛り上がります。
ついでに、「2011年11月11日11時11分」、201111111111は素数ですか？（星田）
A. とんとんさんから
「素因数分解プログラム」というのでやってみましたら、
643 * 31277
となるので、素数ではありません。
A. きくちゃんさんから
ＥＸＣＥＬを使って、力技でやってみると、
643×31277＝20111111
でした。
201111111111 の方は、昔取った杵柄、ＣＯＢＯＬでプロラムを組んで試したら……、あっさり解決してしまいました。３の倍数でした。
難しいという思い込みが失敗のもと。「わな」でしたね。
A. あーさんさんさんから
20111111は31277の倍数ですから、素数ではありませんね。
ついでに、201111111111は各桁をばらばらにして足すと、
2＋0＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＝12
ですから、こちらも素数ではないですね。
★各桁の和が３で割り切れる場合は、３の倍数だとすぐに判断できます。
A. YOSHYさんから
もう幾人もの方がこたえられておられると思いますが、残念ながら、素数ではございません。
2011（年）11（月）11（日）は、
643×31277
2011（年）11（月）11（日）11（時）11（分）は、
3×229×292738153
これに関しては、各桁の数字を全部足して３で割り切れれば３の倍数であることが知られております（私は証明はできませんが）。
ついでに、2011（年）11（月）11（日）11（時）11（分）11（秒）は、
281×1283×55783157
となり、素数ではございません。
よくいちばん大きい素数をコンピュータで探すことが一時はやりましたが、なかなか無いものです。
こんな事をする私は暇人か？ 否定しません！
A. れっこいさんから
あっという間に素因数分解できるmaxima等の便利なソフトもありますが、ここはエクセルを使ってはどうでしょう？
方針はしんごさんと同じで、20111111を整数で次々に割って、その余りを求めていきます。割っていくのは20111111のプラスの平方根（以下「プラスの」は省略）までで十分（もし平方根よりも大きな数で割り切れるなら、その商は平方根よりも小さくなるので、平方根に達する前に「その商」で割り切れるはず）。
√20111111=4484.541……
また偶数で割り切れないのは明らかなので、3〜4483の奇数で割ればいいことになります。
A1に20111111を入力し、B1に3を入力します。カーソルをB1に置き、
編集→フィル→連続データの作成
とし、開く窓で「範囲」を列、「増分値」を2、「停止値」を4483とします。
するとB1〜B2241に3,5,7,……,4483と奇数が並びます。
C1に「=mod(A$1,B1)」と入力し、カーソルをC1に位置させて右下の■をダブルクリック（下方にコピー）。これでC1〜C2241に「20111111をＢ列の各数で割った余り」が 表示されます。この中に０が無ければ、20111111は素数となります。
そこでD1あたりに「=MATCH(0,C1:C2241,FALSE)」と入力すると「321」と表示されるので、C321に０があることが分かります。以上から、20111111は素数では有りません。
ついでにD2あたりで「=INDEX(B1:B2241,321)」とすると、643と表示されるので、20111111は643で割り切れることが分かります。
また、20111111を643で割った答え「31277」は、643の２乗よりも小さい（＝31277の平方根は643よりも小さい）ので素数です（素数でなければ、643に達する前にB列が31277の約数になり、Ｃ列が０になったはず）。
このことから20111111は、643×31277と素因数分解できることも分かります。
A. ｋｚｔさんから
残念！ 素数ではありません。素因数分解すると
20111111＝643×31277
と、ふたつの素数の積になります。
ちなみに、
201＝3×67
2011＝2011（素数）
20111＝7×13^2×17
201111＝3×43×1559
2011111＝2011111（素数）
20111111＝643×31277
201111111＝3^2×149×149971
2011111111＝29×59×919×1279
あとは他の人にお任せします。
★13^2 とは、13の２乗という意味です。
A. yositoさんから
「Ｒ」という数値演算や統計解析用のフリーソフトがあります。群馬大の青木先生が、Ｒでの素数判定や約数分解スクリプトを作成・公開してくれています。
それを使うと、以下のように、簡単に計算できます
(0.1 秒くらいです)。
201＝3×67
2011＝2011 →素数
20111＝7×13^2×17
201111＝3×43×1559
2011111＝2011111 →素数
20111111＝643×31277
201111111＝3×2×149×149971
2011111111＝29×59×919×1279
20111111111＝7^3×13×4510229
201111111111＝3×229×292738153
2011111111111＝24223×83024857
20111111111111＝281×1283×55783157
201111111111111＝3×23×127×41203×556999
残念ながら、これ以上のケタでは精度が落ちて正しく計算されません。
★0.1秒ですか！ スゴイですね。
式中の 13^2 などは、13の２乗ということを表しています。
A. 七氏さんから
お答えします。
20111111＝643×31277
201111111111＝3×229×292738153
なのでどちらも素数ではありません。
「素因数分解」「素数判定」でネットを検索すると、計算（または判定）してくれるサイトがいくつか見つかるかと思います。上記の結果はそのサイトで計算して貰ったものです。
そんな便利なサイトがあるのには理由があります。「適当に考えた大きな数が素数か否か」はただの趣味に留まらない、とても実用的な問題なのです。
銀行のサイトにアクセスしてネットで振込み処理をするときのように、盗聴されずに安全な通信を行いたいとき、ＲＳＡ暗号という暗号方式が使われます。すこし極端ですが、ＲＳＡ暗号がなければインターネットでの安全な通信はありえないとも言えます。
このＲＳＡ暗号を使うには「とても大きな素数」を用意する必要があるのです。しかし、「とても大きな素数」を簡単に作り出すことはできませんので、実際には「素数である確率が高い大きな数」を適当に作っておいて「素数判定」をして合格しなかったものを捨てることで「とても大きな素数」を見つけるという手順をとっています。
そういうわけで、「素数である確率がとても高い大きな数の作り方」「素数かそうでないかの判定のしかた」「効率のよい素因数分解のしかた」はよく研究されています。
★とりたかしさん、えんさん、まいたけさんからも、回答をいただきました。
ありがとうございました。
|
