- 100^99と99^100の大小比較を、対数変換を使ってCommon Lispで解きました。
- 整数の格子点を三色で可視化すると、境界曲線がe（約2.718）付近を通ることが見えてきます。
- f(t) = log t / t という関数の増減を調べると、eで極大を持つ構造からこの境界が必然的に導かれます。
1. まず直接計算してみると
100^99 と 99^100 はどちらが大きいでしょうか。
パッと見ても、よくわかりません。
この問いをCommon Lispで探索していきましょう。
100^99 を素直に計算しようとすると、天文学的な桁数になります。
こういうときに役立つのが対数。
x と y がともに正のとき、x^y > y^x と y log x > x log y は同値です。
そこで、両辺の対数を比べれば十分です1。
(defun compare-powers (x y)
"x^y と y^x を比較して、x^y<y^x なら -1、等しければ 0、大きければ 1 を返す。"
(cond
((and (zerop x) (zerop y)) 0)
((zerop x) -1)
((zerop y) 1)
(t
(let ((a (* y (log x)))
(b (* x (log y))))
(cond ((< a b) -1)
((> a b) 1)
(t 0))))))
Code language: Lisp (lisp)(compare-powers 100 99) ; => 1 つまり 100^99 > 99^100Code language: Lisp (lisp)比較だけが目的なので、対数の底は何でも構いません。
Common Lispの log が返す自然対数をそのまま使っています。
1.1. 具体例で試すと答えがばらつく
では、一般的に x^y と y^x の大小は何で決まるのでしょうか。
まずは、小さな数字で確認してみます。
2^3 < 3^2
2^5 > 5^2
3^5 > 5^3
2^4 = 4^2Code language: HTML, XML (xml)(2, 3) では y^x が大きく2、(2, 5) では x^y が大きい。(2, 4) に至っては等しくなります。
小さな数の組み合わせだけでこれだけばらつくなら、全体的にはどうなっているのでしょうか。
2. 格子点を三色で塗る
そこで、整数の格子点 (x, y) 全体を一度に見てしまいましょう。x^y > y^x なら青、等しければ黒、x^y < y^x なら赤に塗ります。
ここでは vgplot を使います。
vgplot はgnuplotをバックエンドにしてCommon LispからグラフMを描くライブラリで、Quicklispから入手できます3。
(ql:quickload :vgplot)
(defun write-sign-matrix-file (n pathname)
"gnuplot の matrix 用データファイルを書き出す。"
(with-open-file (out pathname
:direction :output
:if-exists :supersede
:if-does-not-exist :create)
(dolist (row (sign-matrix n))
(format out "~{~A~^ ~}~%" row))))
(defun plot-sign (n &optional (file "/tmp/sign-matrix.dat"))
"1..n の格子点を、画像風の三色プロットで描く。"
(write-sign-matrix-file n file)
(vgplot:close-all-plots)
(vgplot:format-plot t "unset key")
(vgplot:format-plot t "set size ratio -1")
(vgplot:format-plot t "set view map")
(vgplot:format-plot t "set xrange [0.5:~A.5]" n)
;; 環境によって上下が逆に見える場合は次の行を使う:
;; (vgplot:format-plot t "set yrange [~A.5:0.5]" n)
(vgplot:format-plot t "set yrange [0.5:~A.5]" n)
(vgplot:format-plot t "set xtics 1,20,~A" n)
(vgplot:format-plot t "set ytics 1,20,~A" n)
(vgplot:format-plot t "set cbrange [-1:1]")
;; -1=red, 0=black, 1=blue
(vgplot:format-plot
t
"set palette defined (-1 'red', 0 'black', 1 'blue')")
;; 見た目調整
(vgplot:format-plot t "set tics out")
(vgplot:format-plot t "set border lw 1")
(vgplot:format-plot t "plot '~A' matrix with image" file)
(vgplot:title (format nil "sign(x^y - y^x) for 1 <= x, y <= ~A" n))
(vgplot:xlabel "x")
(vgplot:ylabel "y"))
;; 実行例
(plot-sign 120)Code language: Lisp (lisp)予想と違って、青と赤の領域は対角線 y = x を境にきれいに分かれています。
大部分は規則的で 底が大きい方が全体も大きくなっています。
ただ、小さい数のあたり（特に x=1 と x=2 の列）だけ色が入り乱れています。
2.1. ステップを細かくして見ると
全体としては規則がありますが、なぜ小さい数だけ乱れるのでしょう。
整数だけ見ていると「1と2が特殊」としかわかりません。
そこで、x と y を実数に広げて0.1刻みで同じ図を描いてみます。
(defun sign-matrix-fine (n step)
"y=1..n, x=1..n を step 刻みで走査し、(x y sign) のリストを返す。"
(loop for y from 0.0 to n by step append
(loop for x from 0.0 to n by step
collect (list x y (compare-powers x y)))))
(defun write-sign-data-file-fine (n step pathname)
"gnuplot 用の x y z 形式データファイルを書き出す。"
(with-open-file (out pathname
:direction :output
:if-exists :supersede
:if-does-not-exist :create)
(let ((current-y nil))
(dolist (triple (sign-matrix-fine n step))
(destructuring-bind (x y z) triple
(when (and current-y (/= y current-y))
(terpri out))
(format out "~F ~F ~D~%" x y z)
(setf current-y y))))))
(defun plot-sign-fine (n step &optional (file "/tmp/sign-matrix-fine.dat"))
"1..n の領域を step 刻みで三色プロットする。"
(write-sign-data-file-fine n step file)
(vgplot:close-all-plots)
(vgplot:format-plot t "unset key")
(vgplot:format-plot t "set size ratio -1")
(vgplot:format-plot t "set view map")
(vgplot:format-plot t "set xrange [0:~A]" n)
(vgplot:format-plot t "set yrange [0:~A]" n)
(vgplot:format-plot t "set xtics 1,1,~A" n)
(vgplot:format-plot t "set ytics 1,1,~A" n)
(vgplot:format-plot t "set cbrange [-1:1]")
(vgplot:format-plot
t
"set palette defined (-1 'red', 0 'black', 1 'blue')")
(vgplot:format-plot t "set tics out")
(vgplot:format-plot t "set border lw 1")
;; 各点を step × step の画素として描く
(vgplot:format-plot
t
"plot '~A' using 1:2:3 with image" file)
(vgplot:title
(format nil "sign(x^y - y^x) for 1 <= x,y <= ~A, step=~A" n step))
(vgplot:xlabel "x")
(vgplot:ylabel "y"))
;; 実行例
(plot-sign-fine 10 0.1)
Code language: Lisp (lisp)この図では、青と赤の境界線が浮かびあがりました。
境界は y = x の直線だけでなく、もう一本の曲線が存在します。
その曲線が x 軸と交わる点を見ると、だいたい 2.7 あたりです。
ここで思い出すのは、自然対数の底 e 。
e ≒ 2.718なので、これに近い値です4。
3. e が現れる理由
実は、境界に e が現れるのは、必然性があります。
x^y と y^x の比較を対数に直すと
y log x と x log yの比較になります。
ここで、両辺を xy で割ると
(log x)/x と (log y)/yつまり、比較しているのは f(t) = (log t) / t という関数の値です。x^y > y^x となるのは f(x) > f(y) と同じ意味になります。
この関数を微分すると
f'(t) = (1 - log t) / t^2つまり、f'(t) = 0 となるのは log t = 1。
すなわち t = e のときです。
t < e では増加し、t > e では減少する。e でちょうど山を作る関数でした5。
;; f(t) = log(t) / t の値を確認する
(defun f (t-val) (/ (log t-val) t-val))
(f 1) ; => 0.0
(f 2) ; => 0.3466...
(f 3) ; => 0.3662...
(f 4) ; => 0.3466... ← f(2) と等しい
(f 5) ; => 0.3219...Code language: Lisp (lisp)f(2) = f(4) だから 2^4 = 4^2 になります。f(2) < f(3) だから 2^3 < 3^2 になる。
整数で見えた例外はすべてここから来ています6。
3 以降はすべて減少域なので f(3) > f(4) > f(5) > ... となり、x < y のとき f(x) > f(y)、つまり x^y > y^x が基本形です。1 と 2 だけが増加域に入るため、この基本形から外れます。
3.1. 疑問を掘り下げると自然対数が見えてくる
出発点は「どちらが大きいか」という単純な問いでした。
直接計算が難しいので対数に変換し、全体像を見るためにグラフにした。
グラフの境界を細かく調べたら 2.7 が現れ、そこから e に気づき、f(t) = log t / t の増減という構造が見えてきました。
自然対数を後から持ち込んだわけではなく、問いを整理しようとしたら自然に出てきた。
数学の面白さのひとつは、こういう必然的な登場の仕方をするところにあると思います。
- この変換は x > 0 かつ y > 0 の範囲でのみ成り立ちます。対数の底は任意で構わず、底を変えても大小関係は変わりません。 – Derivatives of Logarithmic Functions – Math LibreTexts
2^3 = 8、3^2 = 9なので3^2のほうが大きくなります。この (2, 3) の例は、指数の大小比較の直感を裏切る有名な例として数学の教科書でよく取り上げられます。 – The Common Lisp Cookbook – Numbers- vgplotはVolker Sarodnick氏が作成し、GPLv3で公開されているCommon Lispライブラリです。OctaveやMATLABのプロットコマンドに近いAPIを持っています。 – GitHub – volkers/vgplot
eはネイピア数とも呼ばれ、e = lim_{n→∞} (1 + 1/n)^nで定義されます。自然対数の底として、微積分をはじめとする数学の至る所に現れます。 – Derivatives of Logs – Drexel Universityf(t) = log t / tがt = eで最大値1/eをとることは微積分の標準的な問題として知られており、導関数(1 - log t) / t^2がt = eでゼロになることから示されます。 – Misc 1 – Show that f(x) = log x / x has maximum at x = e – Teachoo- 正整数の範囲で
x^y = y^xかつx ≠ yとなる解は(2, 4)と(4, 2)だけです。これはWikipediaの “Equation x^y = y^x” の記事にもあります。 – Equation xy = yx – Wikipedia