アジマティクス

ここをこうするとおもしろい

1111…1という数(レピュニット)の素因数分解を納得する

11/11はポッキーの日! よっしゃー! ポッキーゲームするぞ! うるせえ! そんな相手いるかい!! そんなことより素因数分解だ!!!

レピュニット

1111や11111111などのように、1がいくつも並んだ数をrepeated unit、略してrepunit(レピュニット)と呼び、例によって「あるレピュニットが素数であるか?」という問題はその筋の人達の関心を引いています。素数であるようなレピュニットのことをレピュニット素数と言い、うんまあそりゃそう呼ぶだろうなって感じです。

1が並んでる数とかいかにも素数っぽいのですが、レピュニット素数は意外にまれで、11の次のレピュニット素数は1が19個並ぶまで現れません。その次は23個。その次は飛んで317個。その次はさらに飛んで1031個。

レピュニット素数がどんなタイミングで現れるのか、あるいは、無限に存在するかどうかというのは未解決問題となっており、好事家たちの関心を引くのもわかります。

レピュニットの素因数分解

さて、素数かどうかが関心を引いていることは確かなのですが、「そのレピュニットを素因数分解してみるとおもしろい」というタイプのものもゴロゴロ転がっています。

例えば1111は素因数分解すると11 * 101。まあこちらに関しては「ああ、そりゃ言われてみれば当たり前だよね」って感じであまり感慨はありません。

1がn個並んだ数をレピュニットの頭文字をとってR_nと呼ぶことにすると、1が5個並んだR_5なんか結構よくて、これは11111 = 41 * 271と分解されます。

1だけでできてた数からは想像もつかないような素因数が出てきてる! 41とか! なんなん! ていうかR_3である111の時点で3 * 37なのでけっこう予想だにできない感じは出ています。

私のオススメはR_7です。書き下すと1111111ということになりますが、これの素因数分解は239 * 4649となります。「兄さん君よろしく!」と覚えるとよいでしょう。

f:id:motcho:20171111152142p:plain
兄さん君よろしく!

R_{13}は53 * 79 * 265371653。「古参、泣く。風呂越さない婿さん」ですね。

f:id:motcho:20171111154602p:plain
古参、泣く。風呂越さない婿さん

R_9は3 * 3 * 37 * 333667。こちらもなかなかいい感じのヤバい数が出てきてます。

え? でもちょっとまって? 最後の「333667」ってさ、いかにも「1を引いてから3で割ってください感」が出てない?

他も見てみます。

R_{10}は11 * 41 * 271 * 9091

R_{14}は11 * 239 *4649 * 909091

ん?

R_{38} = 11 * 909090909090909091 * 1111111111111111111

いや明らかに規則性あるやつ! 909090909090909091って!

しかも41 * 271とか239 *4649とか、中に既出のやつが出てきてる!

……そうなんです。素因数分解できるレピュニットの中には「納得できるような理由でもって、その素因数が出てきてる」ものが多くあります(まあ53 * 79 * 265371653とかも別に納得できると言われてしまえばそれまでですが)。

今回はそのへんをちゃんと納得してみたいと思います。

レピュニットの素因数分解を納得する

まずR_9の111111111 = 3 * 3 * 37 * 333667。これを、納得できるような形にすることを目的に式変形していきます。手書きで失礼します。

f:id:motcho:20171111123857j:plain

あっ、ここがメインなのに手書き一枚で済んじゃった。ラクでいいですね!

どうでしょう。奔放に出てきてたかのように見えた333667という素因数、なにも伊達や酔狂で出てきているわけではなくて「いかにも1引いて3で割るっぽい数」として出てきてた理由がお分かりいただけたかと思います。

90909090...91タイプのものも見ておきましょう。例えばR_{14} = 11 * 239 * 4649 * 909091。

f:id:motcho:20171111142203j:plain

見どころはもちろん「909091 * 11」が「繰り上がりが発生しまくって」ちょうど10000001になるところでしょう。91,9091,909091,90909091...という数は、11をかけるとうまいこと繰り上がりによって1001,100001,10000001,1000000001...になる。それによって、レピュニットが実現される、と。こういうわけだったのです。納得納得!

すべてそうとは限らない

しかし、すべてのレピュニットの素因数分解がこのようなわかりやすい構造を持っているとは限りません。

まずそもそも一般に、R_nnが合成数ならR_nも合成数となることが知られています。

これは考えてみると当然のことで、例えばa_6 = 111111は「11 * 10101」または「111 * 1001」とかけ算で表すことができます。それぞれ「2 *3」「3 * 2」に相当します。a_{25}だと「11111 * 100001000010000100001」。このように、nが合成数のときは必ずかけ算で表す方法が存在するわけです。

なんていうんですかね、「ちょうどハマるような隙間に1を置いていってる」感じがします。形を合わせる幼児用知育玩具みたいな。

(↓こういうやつ)

nが合成数のときのレピュニットはわかりやすい構造を持っていて当然ということがわかりました。しかし、nが合成数であっても、パッと見ではわかりやすい構造を持っているように見えないものもあります。

R_{20}くらいまでのレピュニットの素因数分解を一覧で見てみましょう。

 R_1 = 1

 R_2 = 11

 R_3 = 3 * 37

 R_4 = 11 * 101

 R_5 = 41 * 271

 R_6 = 3 * 7 * 11 * 13 * 37

 R_7 = 239 *4649

 R_8 = 11 * 73 * 101 * 137

 R_9 = 3 * 3 * 37 * 333667

 R_{10} = 11 * 41 * 271 * 9091

 R_{11} = 21649 * 513239

 R_{12} = 3 * 7 * 11 * 13 * 37 * 101 * 9901

 R_{13} = 53 * 79 * 265371653

 R_{14} = 11 * 239 * 4649 * 909091

 R_{15} = 3 * 31 * 37 * 41 * 271 * 2906161

 R_{16} = 11 * 17 * 73 * 101 * 137 * 5882353

 R_{17} = 2071723 * 5363222357

 R_{18} = 3 * 3 * 7 * 11 * 13 * 19 * 37 * 52579 * 333667

 R_{19} = 1111111111111111111(素数)

 R_{20} = 11 * 41 * 101 * 271 * 3541 * 9091 * 27961

nが合成数だからといって、パッと見でわかる構造をしているとは限らないことが見て取れます。特にR_{15}とかR_{18}とか。

これは「1000001」や「9090909091」などの数が素数だったり合成数だったりすることによります。これらが合成数だった場合に、その素因数分解を最後まで進めてしまっては、その構造は隠れてしまう。ということです。

例えばa_{18}の111111111111111111なんかは、素因数分解された表記からちょっと計算を進めて整理すると、111 * 1001001 * 999001 * 1001となり、容易にその構造を見て取れるようになります。この中の例えば999001は素因数分解すると19 *52579ですが、これをそのままの表記にしておいたのでは、見た目からはその構造はわからなくなってしまいます。

ぶっちゃけWikipediaなんかのレピュニットの一覧は、この素因数分解が最後まで計算されてしまっているため、逆に構造がわかりにくくなっているんですよね。一覧としてはそうするのが妥当なので仕方ないのですが、構造を見失わない程度で素因数分解を止めておいた一覧も欲しいところです。以下になります(赤くて太いのが素数)。

 R_1 = 1
 R_2 = 11
 R_3 = 3 * 37
 R_4 = 11 * 101
 R_5 = 41 * 271
 R_6 = 111 * 1001
 R_7 = 239 *4649
 R_8 = 11 * 101 * 10001
 R_9 = 111 * 1001001
 R_{10} = 11 * 9091 * 11111
 R_{11} = 21649 * 513239
 R_{12} = 111 * 1001 * 101 * 9901
 R_{13} = 53 * 79 * 265371653
 R_{14} = 11 * 909091 * 1111111
 R_{15} = 111 * 11111 * 90090991
 R_{16} = 11 * 101 * 10001 * 100000001
 R_{17} = 2071723 * 5363222357
 R_{18} = 111 * 1001001 * 999001 * 1001
 R_{19} = 1111111111111111111(素数)
 R_{20} = 11111 * 9091 * 11 * 99009901 * 101

さっきも言いましたがR_{15}R_{18}の構造の隠れっぷりがすごいですね。やはりR15とR18は隠されることが必然のようです。

この表からもう一つわかることとして、「nが合成数のとき」はレピュニットも合成数で確定なのですが、「nが素数のとき」のレピュニットは素数だったりそうじゃなかったりするんですよ。こっちの方の素因数は分かりやすい構造があらわれているなんてことは一ッッッッ切ありません。でも、もしかしたら、そこに何らかのルールがあるかもしれない。そこにルールを探すクッソ地道な努力を、人は数学と呼んでいるわけです。ロマン。

11/11です

さて11/11はポッキーの日です。 ポッキーゲーム? うるせえ! 知るか! 素因数分解こそが俺たちのポッキーゲームじゃ!!

ではまた。