本記事は2012年5月10日に、当時のtsujimotterが骨折で入院中に暇を持て余して執筆し、旧ブログで公開していた記事の再掲です。
久しぶりに読んで面白かったのと、旧ブログは将来無くなる可能性があることから、tsujimotterのノートブックにも載せておこう思います。よろしければご覧いただければと思います。
できるだけ当時の雰囲気を残しておきたいので、文章には原則手を入れていません。
(1) 問題提起
が流行っているようなので、暇つぶしにこのパターンの式をどれだけ作ることが出来るのか考えて見ます。本記事はfacebookに投稿していたものをブログ用にまとめたものです。
まずこの問題は、下記の二式を満たす4つの整数 を求める問題として定式化されます。
ここで、式2つに対して、変数4つなので、自由度は2です。2つ変数を決めれば、残りは決まります。注意すべきは、整数という制限がつくため、2つ決めてもそれを満たす解がない場合があることです。
式変形して議論しやすい形に持って行きます。
式の両辺に を掛けて、とする。 として、
戦略としては、これで が消えたので、 と を適当に決めて を求める。
得られた を に代入して を求める。
を決めても がないかもしれないことに注意。
さて、ここからどう攻めるかですが…
まずは、基本問題の から行きましょう。
に代入すると
この式に を適当に代入して評価して行きましょう。 からいきます。
のとき。
に代入して、
したがって、
当然これは元の式で自明です。どんどん行きましょう。
のとき、
よって、
だんだん がちいさくなってますね。下限があるのでしょう。
のとき。
より…って右辺が で割れないから無理!よって解なし。だんだん面白くなってきた。
のとき。
したがって、
そろそろ打ち止めの予感。
のとき。
さあここで、
は が1以上の整数であることから不成立。打ち止めです。
つまり のとき、 から
より、 と合わせて、
を満たす だけが解であることがわかったわけです。
これより、
つまり、 の上界が ということがわかります。それ以上の は打ち止め。
これでずいぶんと話が楽になりそうです。
ここで、話を飛躍させて、 の場合をかんがえてみましょう。
よって、 の条件は、
となって、
ちょっと確認したくないぐらいの数になってきました…
まてよ、これ一般の に対してもおんなじ用*1に考えられるな。
一般に、
これを計算すると
したがって、
おー、すごく簡単な式になった!式番号つけちゃえ
そうか、さっき感じた「これ計算するのかったるそうだ」というのは を押さえる不等式の右辺が階乗で爆発するからなんだ。
さあ、いくらかこの問題の性質がわかってきた。しかし、まだまだ謎は残っている。果たして はいくらでも大きく出来るのか、そして が決まったとき、解なしという例外はいつ発生するのか。次節に続く(笑)
(2) の条件
まだもう少し続けられそうなので、解なしの部分に関してもう少し考えて見ます。
のとき、
を満たす解はありませんでした。
は で割れませんから、 を が割り切るか考えればよいのですが、 の素因数分解は なので、当然割れませんね。
同様に のいかなる に対しても、
は成り立ちません。
ここで
したがって
が成り立つかどうか判定できればよいことがわかります。
ここからが、大きな問題。 の約数なんてどうやって考えたらいいんだと。
は
のように因数分解される。
ややこしいな。つまり、 が か の約数だったらいいわけだ。
をためしにいくつか計算してみよう。
あれ、もしかして全部素数?!
※注:この記述には誤りが含まれます。
つまり、 が素数と仮定すると、 が存在するような は、 が の約数であるか、または、 そのものであるときに限られるということだ!これはすごいかもしれない!
ここで、前に計算した の条件を思い出そう。
である。さっきの素数そのものである
は、
であるから、条件を照らし合わせてギリギリアウト!
よって、 の存在する の条件は、 が の約数であること、つまり
ずいぶんとシンプルになった。
確認のために、 のときを考える。
の約数は 。つまり、 すなわち、 のときのみに解が存在することが分かればいい。確かにそうなってる!
ってことは、 のときは、約数は だけだから、 のときだけ探せばいいね!あら簡単!
こうやって考えると、任意の に対する解の個数は、約数の個数関数 で表せるということ。
※2012/05/12修正: をオイラー関数と言っていましたが、これは違いましたね。
これで、結論は出ました。
「40-32÷2=4! に類似する問題はいくつ見つけることが出来るのか」という疑問でしたが、かなりシンプルにまとまったと思います。
結論:
解はそれぞれの に対して 個とることができる。
は対応する の約数+1。
はそれぞれ に対して下式の通り一意に求められる。
おっと、そうは問屋がおろさねえ!ウィキペディアの階乗素数の項目によると、
の形の素数は確かに存在するけれど、全部が素数ではないらしい…オーノー。やっぱりそう簡単にはいかないか。
まぁ、 が合成数なら、素因数分解してしまって、
の条件
を満たすような を、 の素因数と の素因数の組から適当に作って、 と を計算すれば求める解が得られます、と言うこともできます。
次節以降で、これを実際に計算して、馬鹿でかい数の等式を作ってみましょう。
(3) 階乗素数との関係
さて、前節までに分かったことを一旦まとめてみましょう。
まず問題ですが、
を満たすような 以上の正整数 を求めよという問題でした。
これに対し、これまでの議論から、適当な を選ぶと
と解が得られることがわかっています。
ただし、 に対する において、解が得られるための下記の制約条件がありました。
条件 は 式 に対し から得られます。一方、条件 は式 の が整数であることから導かれました。
ここで を考えた時に、もし仮に が素数だとすると、
がすべての の候補の集合となります。
「 のそれぞれの約数 × の集合」は条件 を満たしませんから、
結果 の候補は 「 の約数+1」に限られます。
としたとき、 と表されるわけですが、このような形で表される素数は階乗素数と呼ばれます。実際計算してみるとわかりますがすべての が階乗素数となるわけではありません。
4!-1 = 23
6!-1 = 719
7!-1 = 5039
12!-1 = 479001599
14!-1 = 87178291199
は階乗素数ですが、下記は合成数となります。
8!-1 = 23 * 1753
9!-1 = 11^2 * 2999
10!-1 = 29 * 125131
11!-1 = 13 * 17 * 23 * 7853
13!-1 = 1733 * 3593203
15!-1 = 17 * 31^2 * 53 * 1510259
16!-1 = 3041 * 6880233439
17!-1 = 19 * 73 * 256443711677
18!-1 = 59 * 226663 * 478749547
19!-1 = 653 * 2383907 * 78143369
20!-1 = 124769 * 19499250680671
21!-1 = 23 * 89 * 5171 * 4826713612027
22!-1 = 109 * 60656047 * 170006681813
23!-1 = 51871 * 498390560021687969
翻って、階乗素数となる、本問題の解を列挙してみると、たとえば のときは、
30 – 18 / 3 = 4!
25 – 5 / 5 = 4!
230 – 220 / 2 = 5!
138 – 108 / 6 = 5!
10066 – 10052 / 2 = 7!
5752 – 5696 / 8 = 7!
80624 – 80608 / 2 = 8!
60468 – 60444 / 3 = 8!
50390 – 50350 / 5 = 8!
45351 – 45279 / 9 = 8!
となって確かに「 の約数+1」の のときに解が得られることがわかります。
同様に、もっと大きな数の階乗素数を考えれば、いくらでも問題を作ることができます。
Wikipediaによると、現在知られている階乗素数は、 がそれぞれ
のときであるから、 として問題を作ることも原理的には可能です。 が正確に計算できれば、ですが(笑)。
が階乗素数であることは、2010年12月14日にJ. Winskillによって発見されたそうです(MathWorld “Factorial Prime” 記事より)。*2
次は、 が合成数の場合について考えてみましょう。
(4) 巨大因数の探索
前節から続いて、 が合成数である場合を考えましょう。
基本的な考え方は素数の場合と同じです。
解を持つ の条件は、
です。
より、 の素因数と、 の素因数をそれぞれ求めて、 その組合せから のすべての約数を求めればよいでしょう。そのときは、 の条件も考慮して不必要な要素を省いていきます。
さて、ここまで、最初の問題の解のパターンを、すべて導出するという目的で議論してきましたが、これらの問題はある種のパターンの合成数に対する素因数分解の問題に深くかかわっていることがわかってきました。
とても残念ですが、素因数分解の問題を一般性を残したまま扱うのは、そろそろ限界かもしれません。
そこで、視点を変えて、大きな の値に対して、 を計算するということにチャレンジしてみます。
大きいといっても を計算するわけですからあまり大きくし過ぎると、数値が爆発してしまいます。
また の素因数分解も困難になりますので、適度なところをとって としてみましょう。このとき、 は合成数となります。
また を素因数分解すると、
となります。
の候補はそれぞれの積の約数ですから、
から 、 から の約数をそれぞれとって
を選んでみます。すると
これを、 の式に代入して計算します。
したがって、求める式は、
私はこれをJavaのプログラムで計算しましたが、
どうやらWindowsの関数電卓でも桁落ちなしで計算できるようです。(Windows意外とできる子です笑)
ちなみにgoogleさんの電卓は浮動小数点になってだめでした。
それぐらい大きな数の計算ができるようになったわけです。
ひとまずここまで。
追記[2012/11/29]
Rubyでのソースコードを追加してみました。
Javaと違ってBigintなどの型に自動で変換されるようですね。ソースコードが非常に簡潔です。
# 階乗を計算する関数 def fact(n) if n==0 then return 1 else return fact(n-1)*n end end # 数値の定義 w = 24 z = 622453 x = z * w * (fact(w-1)-1)/(z-1) y = x - z * w # 解の表示 puts "# x - y / z = w!" puts "# (x - y)/ z = w" puts "x = "+x.to_s puts "y = "+y.to_s puts "z = "+z.to_s puts "w = "+w.to_s
追記[2024/08/22]
時代も変わっているので、Pythonでのソースコードを追加してみました。
# 階乗を計算する関数 def fact(n): if n == 0: return 1 else: return fact(n-1)*n # 数値の定義 w = 24 z = 622453 x = z * w * (fact(w-1)-1) // (z-1) y = x - z * w # 解の表示 print(f"# x - y / z = w!") print(f"# (x - y)/ z = w") print(f"x = {x}") print(f"y = {y}") print(f"z = {z}") print(f"w = {w}")
感想(未来の自分より)
久しぶりに過去の記事(今から12年前)を読んでみて、(自分で言うのもなんですが)大変面白かったです。
文章は荒くて読みづらいですが、楽しそうに数学をしている感じが出ているのが良いですね。
最近のtsujimotterのノートブックは、専門的な内容を解説する系の記事が多いのですが、こんなふうに自由研究的に考えるのも楽しいかもしれません。
今読んでみると、文体が今の自分のものと異なることに気づきます。
この頃の文章はEMANの物理学さん(https://eman-physics.net)に大いに影響を受けている気がします。
(EMANの物理学さんは、私が学生時代に大変お世話になったサイトです。このサイトがあったからこそ、数学の発信をしようと思ったと言っても過言ではありません。)
佐野さんという方が以前(私の影響を受けて)ブログを始めたときに、「辻さんの文体に影響を受けすぎて僕らしさがない」みたいなことをおっしゃっていたのを思い出しました。私自身も、ブログを書いていくうちに自分らしい文章を獲得していったということなのですかね(?)。
注釈にも書きましたが、久しぶりにMathWorldの階乗素数の記事を見てみたら新しい素数が発見されていて、大変驚きました。
そういえば、世の中には同じようなことを考える人がいて、たとえばこちらのブログ記事があります。
yumulog.hatenablog.com
この記事をきっかけに、著者の方をTwitterでフォローしたのですが、10年以上経って今この湯村先生と一緒の職場で働いています。
不思議な縁ってあるものですね。笑
ここまで読んでくださってありがとうございます。
それでは今日はこの辺で!