すべての正の有理数を産み出す式のレシピ(日曜数学会)
はじめに
この記事は 第２５回日曜数学会(2022.10.15) で発表した内容に加筆したものです。
Twitter で話題になった、すべての有理数を産み出す式について、いろいろ遊んでいたところ、作り方のレシピがわかったのですが、そのレシピがとても面白かったので記事にしました。
(話題になった @TamasGorbe さんのツイート)
Consider the function
— Tamás Görbe (@TamasGorbe) September 18, 2022
f(x) = 1 / ( ⌊x⌋ + 1 − {x} )
and the sequence of numbers
0, f(0), −f(0), f(f(0)), −f(f(0)), f(f(f(0))), −f(f(f(0))), ...
Congratulations, you've just listed every rational number exactly once! pic.twitter.com/NRlNnx49Ql
なお、この記事では原則として有理数は既約分数で表すこととします。また、説明を簡単にするため、自然数は分母が $1$ の分数とみなすことにします。
元ネタのツイートではプラスとマイナスを交互に並べて「すべての有理数」を作る式としていましたが、この記事では簡単のためプラスの場合だけ考え、「すべての正の有理数」を作る式として考えることにします。
「整数部分」を $\lfloor \cdot\rfloor$ 、「小数部分」を $\{ \cdot\}$ の記号であらわすことにします。
(整数部分)
$\lfloor 1.618\rfloor=1$
(小数部分)
$\{ 1.618\}=0.618$
定義より、 $\{x\}=x-\lfloor x\rfloor$ が成り立ちます。この関係は最後の方で使います。
レシピ
まず、例の式を作るためのレシピを確認しましょう。
方針
$1$ 正の有理数をもれなくダブりなく、いい感じに一列に並べて数列を作る
$2$ できあがった数列の第 $(n+1)$ 項を、第 $n$ 項で表す
$3$ できあがり!
先にいい感じの数列を作ってから、漸化式をつくる方針で作ることができます。
道具
○ ユークリッドの互除法(最大公約数を求めるやつ)
○ 二進数
これだけ知っていればこの記事の内容が理解できると思います。
なお、この記事では二進数を $1011_{(2)}$ のように書いて十進数と区別することにします。
$1_{(2)}=1$
$10_{(2)}=2$
$11_{(2)}=3$
$100_{(2)}=4$
$101_{(2)}=5$
$110_{(2)}=6$
$\vdots$
正の有理数から自然数への写像を作る
では、さっそくいい感じの数列を作りましょう。
次のような操作を考えます。
$1$ 任意の正の有理数を既約分数で表す。ただし整数の場合は分母が $1$ の分数とみなす。
$2$ 「分母と分子を比較して大きい方から小さい方を引く」という操作を、分母と分子の数が一致するまで繰り返す。
この操作をすると、どんな正の有理数から始めても、必ず最後は$\dfrac{1}{1}$ になって終わります。
なぜなら、この操作はユークリッドの互除法で分母と分子の最大公約数を求める操作と本質的に同じであり、既約分数の分母と分子の最大公約数は $1$ ですから、最後は$\dfrac{1}{1}$ になります。
(例1)
$\dfrac{16}{10}
\rightarrow\dfrac{6}{10}
\rightarrow\dfrac{6}{4}
\rightarrow\dfrac{2}{4}
\rightarrow\dfrac{2}{2}
$
一般の分数では分母と分子が最大公約数になったところで止まる
(例2)
$\dfrac{13}{10}
\rightarrow\dfrac{3}{10}
\rightarrow\dfrac{3}{7}
\rightarrow\dfrac{3}{4}
\rightarrow\dfrac{3}{1}
\rightarrow\dfrac{2}{1}
\rightarrow\dfrac{1}{1}
$
既約分数の場合は $\dfrac{1}{1}$ になって終わる
この操作を逆にみると、「 $\dfrac{1}{1}$ からスタートして、分子の数を分母に足す、または分母の数を分子に足す、という操作を繰り返すと任意の正の有理数を作ることができる」ことがわかります。
$\dfrac{1}{1} \rightarrow\dfrac{2}{1} \rightarrow\dfrac{3}{1} \rightarrow\dfrac{3}{4} \rightarrow\dfrac{3}{7} \rightarrow\dfrac{3}{10} \rightarrow\dfrac{13}{10} $
ここでちょっと面白いことを考えます。
「$\frac{1}{1}$ からスタートして任意の正の有理数を作る」という操作に、次のような文字列操作を対応させてみましょう。
・ $\frac{1}{1}$ に対応する文字列を $"1"$ とする。
・ 「分子の数を分母に加える」ときは文字列に $"0"$ を付け加える。
・ 「分母の数を分子に加える」ときは文字列に $"1"$ を付け加える。
$\underbrace{\dfrac{1}{1}}_{"1"} \rightarrow\underbrace{\dfrac{2}{1}}_{"11"} \rightarrow\underbrace{\dfrac{3}{1}}_{"111"} \rightarrow\underbrace{\dfrac{3}{4}}_{"1110"} \rightarrow\underbrace{\dfrac{3}{7}}_{"11100"} \rightarrow\underbrace{\dfrac{3}{10}}_{"111000"} \rightarrow\underbrace{\dfrac{13}{10}}_{"1110001"} $
できあがった文字列を二進数と解釈することで、それぞれの有理数に対応する自然数を作ることができます。
一対一対応ですから、自然数を引数にして有理数を返す関数をつくることができます。
ここからは、こうやって作った自然数に対応する有理数を返す関数を $a(n)$ とします。
$a(1),a(2),a(3),\cdots$ を並べると、全ての正の有理数が１回ずつでてくる数列になります。
この数列は、( 英語版Wikipedia によれば)カルキン・ウィルフ数列と呼ばれています。
これで、「正の有理数をもれなくダブりなく、いい感じに一列に並べた数列」を作ることができました!
「分母の数を分子に足す」などの操作を式で表す
次は「 $a(n+1)$ を $a(n)$ で表す」ための準備を始めます。
$a(n)=\dfrac{q}{p}$ とします。
$\dfrac{p+q}{p}=\dfrac{q}{p}+1$ ですから、「分母の数を分子に加える」という計算は「$1$ を足す」という計算と同じです。
また、$\dfrac{q}{p+q}=\left(\left(\dfrac{q}{p}\right)^{-1}+1\right)^{-1}$ ですから、「分母の数を分子に加える」という計算は「逆数に$1$ を足したものの逆数」の計算と同じです。
つまり $a(n)$ の引数の二進数表記の末尾に $"1"$ や $"0"$ を付け加えると、 $a(n)$ は次のように変化します。
$a\left(\underbrace{\cdots 1}_{末尾に1を付加}{}_{(2)}\right)=a(\cdots_{(2)})+1$
$a\left(\underbrace{\cdots 0}_{末尾に0を付加}{}_{(2)}\right)=\left(a(\cdots_{(2)})^{-1}+1\right)^{-1}$
この操作を繰り返すことで、次のように拡張できます。
$a\left(\cdots\underbrace{11\cdots11_{(2)}}_{末尾に1をk個付加}\right)=a(\cdots _{(2)})+k$
$a\left(\cdots\underbrace{00\cdots00_{(2)}}_{末尾に0をk個付加}\right)=\left(a(\cdots _{(2)})^{-1}+k\right)^{-1}$
引数の二進数表記の末尾で $a(n)$ の大きさを評価する
ここでちょっと話が変わり、$a(n)$ の整数部分について考えます。
「分子の数を分母に足した数」は必ず $1$ 未満になります。
また、「分母の数を分子に足した数」は元の数より $1$ 大きくなります。
つまりこう評価できます。
$0< a\left(\underbrace{\cdots0_{(2)}}_{\text{末尾が0}}\right)<1$
$k\leq a\left(\cdots0\underbrace{11\cdots11_{(2)}}_{末尾に1がk個}\right)< k+1$
したがって、 $a(n)$ の整数部分は引数の二進数表記の末尾に $"1"$ が連続何個続いているか数えることでわかります。
$\left\lfloor a\left(\cdots0\underbrace{11\cdots11_{(2)}}_{1がk個}\right) \right\rfloor=k$
二進数で $1$ を足す操作を文字列操作として解釈する
漸化式を作る準備が整うまであともう一息です!
二進数で $1$ を足すことを文字列操作のように考えると、右側の$1$を削れるだけ削り、その後、一番右にある $0$ を$1$ に変え、それから削った分だけ下位に$0$ を追加する操作に対応します。
全部の桁が $1$ の場合は場合分けがいりそうに思えますが、一番左に $0$ を付加したものとみなせば場合分けせずにすみます。
・ 二進数で $1$を足す
$11010111+1=11011000$
・ 文字列操作として解釈
$"11010111" \rightarrow "11010" \rightarrow "11011" \rightarrow "11011000"$
右側の $"1"$ を $3$ 個削り、右端の $"0"$ を $"1"$ に変え、右側に $"0"$ を $3$ 個付加する
漸化式を作る
ようやく漸化式を作る準備が整いました!
$a(n+1)$ を $a(n)$ で表す式を作りましょう。
$k=\left\lfloor a(n) \right\rfloor$
とおきます。
${\displaystyle \begin{align} &s=a(n)-k&&\text{(末尾の連続k個の"1"を削除)}\\ &t=\left(s^{-1}-1\right)^{-1}&&\text{(末尾の"0"を削除)}\\ &u=t+1&&\text{(末尾に"1"を付加)}\\ &a(n+1)=\left(u^{-1}+k\right)^{-1}&&\text{(末尾に連続k個の"0"を付加)}\\ \end{align} }$
順に代入して
${\displaystyle \begin{align} a(n+1)&=\left(\left(\left(\left(a(n)-k\right)^{-1}-1\right)^{-1}+1\right)^{-1}+k\right)^{-1}\\ &=\left(\left(\frac{a(n)-k}{1-a_n+k}+1\right)^{-1}+k\right)^{-1}\\ &=\left(\left(1-a(n)+k\right)+k\right)^{-1}\\ &=\left(2k+1-a(n)\right)^{-1}\\ \end{align} }$
${\displaystyle \begin{align} a(n+1) &=\left(2k+1-a(n)\right)^{-1}\\ \end{align} }$
ここで
$k=\lfloor a(n)\rfloor$
$\{a(n)\}=a(n)-k$
なので
${\displaystyle \begin{align} a(n+1) &=\frac{1}{\lfloor a(n)\rfloor+1-\{a(n)\}}\\ \end{align} }$
できました!
これが「すべての正の有理数を作る式」です!
${\displaystyle a(1)=1\\ a(n+1) =\frac{1}{\left\lfloor a(n)\right\rfloor+1-\{a(n)\}}\\ }$
練習問題
問題 $1$ ～ $3$
さて、日曜数学会のスライドの最後に $3$ つの練習問題を出しました。ここに再掲します。
「分子の数を分母に足す」「分母の数を分子に足す」と、$”0”$ , $”1”$ の対応関係を逆にしたらどんな漸化式ができるだろう?
$a\left(\left\lfloor\dfrac{4}{3}\cdot2^{n-1} \right\rfloor\right)$ 及び $a\left(\left\lfloor\dfrac{5}{3}\cdot2^{n-1} \right\rfloor\right)$ の分母と分子がともにフィボナッチ数であることを証明できる?
第 $n$ 項の分母と第 $n+1$ 項の分子の関係は? それを漸化式で証明できる?
このすぐ下に解答を置きますので、自分で考えたい人のために少しスキマをあけておきます。
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
解答 $1$ ～ $3$
解答1
(問題 $1$)
「分子の数を分母に足す」「分母の数を分子に足す」と、$”0”$ , $”1”$ の対応関係を逆にしたらどんな漸化式ができるだろう?
これは記事中の計算を単純に入れ替えるだけでOKです。
実際にやってみると
${\displaystyle \begin{align} &s=\left(a(n)^{-1}-k\right)^{-1}&&\text{(末尾の連続k個の"1"を削除)}\\ &t=s-1&&\text{(末尾の"0"を削除)}\\ &u=\left(t^{-1}+1\right)^{-1}&&\text{(末尾に"1"を付加)}\\ &a(n+1)=u+k&&\text{(末尾に連続k個の"0"を付加)}\\ \end{align} }$
順に代入して
${\displaystyle \begin{align} a(n+1)&=\left(\left(\left(a(n)^{-1}-k\right)^{-1}-1\right)^{-1}+1\right)^{-1}+k\\ &=\left(\frac{a(n)^{-1}-k}{1-a(n)^{-1}+k}+1\right)^{-1}+k\\ &=2k+1-a(n)^{-1}\\ \end{align} }$
${\displaystyle \begin{align} a(n+1) &=2k+1-a(n)^{-1}\\ \end{align} }$
ここで
$k=\lfloor a(n)^{-1}\rfloor$
$\{a(n)^{-1}\}=a(n)^{-1}-k$
なので
${\displaystyle \begin{align} a(n+1) &=\lfloor a(n)^{-1}\rfloor+1-\{a(n)^{-1}\}\\ \end{align} }$
この式もまた、全ての正の有理数をもれなくダブりなく１回ずつ産み出す式となっています!
$2$つの式からできる数列を比較してみましょう。
双対らしさを感じていただけますでしょうか。
この$2$つの式は、実に美しい関係だと思います。
解答2
(問題 $2$)
$a\left(\left\lfloor\dfrac{4}{3}\cdot2^{n-1} \right\rfloor\right)$ 及び $a\left(\left\lfloor\dfrac{5}{3}\cdot2^{n-1} \right\rfloor\right)$ の分母と分子がともにフィボナッチ数であることを証明できる?
まずは本当にそうなるのか確かめてみましょう。
${\displaystyle a\left(\left\lfloor\frac{4}{3}\cdot2^{n-1}\right\rfloor\right) }$
の方は $\dfrac{1}{1},\dfrac{1}{2},\dfrac{3}{2},\dfrac{3}{5},\dfrac{8}{5},\cdots$
${\displaystyle a\left(\left\lfloor\frac{5}{3}\cdot2^{n-1}\right\rfloor\right) }$
の方は $\dfrac{1}{1},\dfrac{2}{1},\dfrac{2}{3},\dfrac{5}{3},\dfrac{5}{8},\cdots$
となり、確かに分子・分母ともにフィボナッチ数になっています。
実は、カッコの中にある $\dfrac{4}{3},\dfrac{5}{3}$ をそれぞれ二進数の小数で表すと
$\dfrac{4}{3}=1.0101010101\cdots_{(2)}$
$\dfrac{5}{3}=1.1010101010\cdots_{(2)}$
となります。
見てのとおり、$0$ と $1$ が交互に並んでいますから、これに$2$のべき乗をかけた整数部分部分も
$1_{(2)},10_{(2)},101_{(2)},1010_{(2)},10101_{(2)},101010_{(2)},1010101_{(2)},\cdots$
$1_{(2)},11_{(2)},110_{(2)},1101_{(2)},11010_{(2)},110101_{(2)},1101010_{(2)},\cdots$
と、$0$ と $1$ が交互に並ぶことになります。
その結果、$n$ が増えるたびに分母・分子を交互に足すことになるので、フィボナッチ数の漸化式と同じになるというカラクリでした。
(余談)
日曜数学会のニコニコ生放送では、@tsujimotter さんがこの問題を休憩時間で解いてしまいましたね!
しかも紙を使わず、休憩時間ほぼピッタリで解くというカッコよさ。
カッコよく解いてもらって作問者冥利につきました。
解答3
(問題 $3$)
第 $n$ 項の分母と第 $n+1$ 項の分子の関係は? それを漸化式で証明できる?
まずは第 $n$ 項の分母と、第 $n+1$ 項の分子を見比べてみましょう。
お気づきいただけましたでしょうか。どの位置を見ても
第 $n$ 項の分母 $=$ 第 $n+1$ 項の分子
となっていますね!
それでは、第 $n$ 項の分母 $=$ 第 $n+1$ 項の分子が必ず成り立つことを証明しましょう。
$a(n)=\dfrac{Q}{P}$ とします。($P,Q$は互いに素)
$Q$ を $P$ で割った商を $s$ 、あまりを $q$ とおくと
$\left\lfloor \frac{Q}{P}\right\rfloor=s,\left\lfloor \frac{Q}{P}\right\rfloor=\frac{q}{P}$
となります。
したがって
${\displaystyle \begin{align} a(n+1)&=\frac{1}{\left\lfloor \frac{Q}{P}\right\rfloor+1-\left\{\frac{Q}{P}\right\}}\\ &=\frac{1}{s+1-\frac{q}{P}}\\ &=\frac{P}{P(s+1)-q} \end{align} }$
ですから、
${\displaystyle
R=P(n+1)-q
}$
とおくと
${\displaystyle a(n+1) =\frac{P}{R} }$
となります。
$P$ と $q$ は互いに素なので $P$ と $R$ も互いに素。
つまり、$a(n+1)$ の 分子は $a_{n}$ の分母と同じ $P$となります。
この式を作ったのは誰?
最初にこの「すべての正の有理数を産み出す式」を作った人は誰でしょうか。
冒頭で紹介した、@TamasGorbe さんのツイートによれば、ケプラーが$1619$年に出版した Harmonices Mundi なる書籍に カルキン・ウィルフ・ツリーと同じ樹形図が掲載されているということで、少なくともこの時代にツリーは知られていたようですが、例の式は載っていないようです。
なお、「カルキン」と「ウィルフ」はどちらも$20$世紀生まれの数学者の名前で、$2000$ 年にカルキン・ウィルフ・ツリーを発表したということですが、それ以前にも Jean Berstel や Aldo de Luca、 George N. Raney なども同様のツリーを発表していたということで、なぜ「カルキン・ウィルフ・ツリー」の名前がポピュラーになったのかはよくわかりませんでした。
英語版 Wikipedia の Calkin–Wilf tree の項目の注釈 によれば、この式とほぼ同じ式が 2003 年の The American Mathematical Monthly に掲載されているようですが、私には読むことができませんでした。
……というわけで、誰がどうやってこの式を作ったのかは実は私は知らないのですが、たぶん、この記事の内容と同じような方法で作ったのではないかと想像しています。
おわりに
今回は、試行錯誤してるうちに例の式の導出方法に自然にたどりついて、これほど自然にこんなシンプルな式にたどりつくとは！と、感動した体験をもとに記事を書きました。
この感動が少しでも伝えられていたら幸いです。
また、今回の記事では触れませんでしたが、カルキン・ウィルフ数列は、スターンの二原子数列や、連分数とも関連していて、実に遊びがいのある数列だと思います。
スターンの二原子数列との関係については、@tb_lb さんのこちらの記事が詳しくて読みごたえがあります。
ほにゃらら実験室：スターンの2原子数列に関する記事群の目次
みなさんもいろいろ遊んでみてください。
そして、何か情報がありましたらコメント等で教えてください。