すべての正の有理数を産み出す式のレシピ(日曜数学会)

はじめに

　この記事は 第２５回日曜数学会(2022.10.15) で発表した内容に加筆したものです。

　Twitter で話題になった、すべての有理数を産み出す式について、いろいろ遊んでいたところ、作り方のレシピがわかったのですが、そのレシピがとても面白かったので記事にしました。

(話題になった @TamasGorbe さんのツイート)

Consider the function

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

— Tamás Görbe (@TamasGorbe) September 18, 2022

　なお、この記事では原則として有理数は既約分数で表すこととします。また、説明を簡単にするため、自然数は分母が $1$ の分数とみなすことにします。

　元ネタのツイートではプラスとマイナスを交互に並べて「すべての有理数」を作る式としていましたが、この記事では簡単のためプラスの場合だけ考え、「すべての正の有理数」を作る式として考えることにします。

　「整数部分」を $\lfloor \cdot \rfloor$ 、「小数部分」を $\{\cdot \}$ の記号であらわすことにします。

　定義より、 $\{x\}=x-\lfloor x\rfloor$ が成り立ちます。この関係は最後の方で使います。

レシピ

　まず、例の式を作るためのレシピを確認しましょう。

方針

　先にいい感じの数列を作ってから、漸化式をつくる方針で作ることができます。

道具

これだけ知っていればこの記事の内容が理解できると思います。

なお、この記事では二進数を ${1011}_{(2)}$ のように書いて十進数と区別することにします。

正の有理数から自然数への写像を作る

では、さっそくいい感じの数列を作りましょう。

次のような操作を考えます。

　この操作をすると、どんな正の有理数から始めても、必ず最後は${\displaystyle \frac{1}{1}}$ になって終わります。
　なぜなら、この操作はユークリッドの互除法で分母と分子の最大公約数を求める操作と本質的に同じであり、既約分数の分母と分子の最大公約数は $1$ ですから、最後は${\displaystyle \frac{1}{1}}$ になります。

この操作を逆にみると、「 ${\displaystyle \frac{1}{1}}$ からスタートして、分子の数を分母に足す、または分母の数を分子に足す、という操作を繰り返すと任意の正の有理数を作ることができる」ことがわかります。

ここでちょっと面白いことを考えます。
「$\frac{1}{1}$ からスタートして任意の正の有理数を作る」という操作に、次のような文字列操作を対応させてみましょう。

　できあがった文字列を二進数と解釈することで、それぞれの有理数に対応する自然数を作ることができます。

　一対一対応ですから、自然数を引数にして有理数を返す関数をつくることができます。

　ここからは、こうやって作った自然数に対応する有理数を返す関数を $a(n)$ とします。

$a(1),a(2),a(3),\cdots$ を並べると、全ての正の有理数が１回ずつでてくる数列になります。

全ての正の有理数が現れる数列の冒頭部

この数列は、( 英語版Wikipedia によれば)カルキン・ウィルフ数列と呼ばれています。

これで、「正の有理数をもれなくダブりなく、いい感じに一列に並べた数列」を作ることができました!

「分母の数を分子に足す」などの操作を式で表す

次は「 $a(n+1)$ を $a(n)$ で表す」ための準備を始めます。

$a(n)={\displaystyle \frac{q}{p}}$ とします。

${\displaystyle \frac{p+q}{p}}={\displaystyle \frac{q}{p}}+1$ ですから、「分母の数を分子に加える」という計算は「$1$ を足す」という計算と同じです。

また、${\displaystyle \frac{q}{p+q}}={({\left({\displaystyle \frac{q}{p}}\right)}^{-1}+1)}^{-1}$ ですから、「分母の数を分子に加える」という計算は「逆数に$1$ を足したものの逆数」の計算と同じです。

つまり $a(n)$ の引数の二進数表記の末尾に　$"1"$ や $"0"$ を付け加えると、 $a(n)$ は次のように変化します。

$a\left(\underset{末尾に1を付加}{\underbrace{\cdots 1}}{}_{(2)}\right)=a({\cdots }_{(2)})+1$

$a\left(\underset{末尾に0を付加}{\underbrace{\cdots 0}}{}_{(2)}\right)={(a({\cdots }_{(2)}{)}^{-1}+1)}^{-1}$

この操作を繰り返すことで、次のように拡張できます。

引数の二進数表記の末尾で $a(n)$ の大きさを評価する

　ここでちょっと話が変わり、$a(n)$ の整数部分について考えます。

「分子の数を分母に足した数」は必ず $1$ 未満になります。
また、「分母の数を分子に足した数」は元の数より $1$ 大きくなります。

つまりこう評価できます。

$0<a\left(\underset{\text{末尾が0}}{\underbrace{\cdots 0_{(2)}}}\right)<1$
$k\le a(\cdots 0\underset{末尾に1がk個}{\underbrace{11\cdots {11}_{(2)}}})<k+1$

したがって、 $a(n)$ の整数部分は引数の二進数表記の末尾に $"1"$ が連続何個続いているか数えることでわかります。

二進数で $1$ を足す操作を文字列操作として解釈する

漸化式を作る準備が整うまであともう一息です!

二進数で $1$ を足すことを文字列操作のように考えると、右側の$1$を削れるだけ削り、その後、一番右にある　$0$ を$1$ に変え、それから削った分だけ下位に$0$ を追加する操作に対応します。
全部の桁が $1$ の場合は場合分けがいりそうに思えますが、一番左に $0$ を付加したものとみなせば場合分けせずにすみます。

漸化式を作る

ようやく漸化式を作る準備が整いました!
$a(n+1)$ を $a(n)$ で表す式を作りましょう。

$k=\lfloor a(n)\rfloor$

とおきます。

${\displaystyle \begin{array}{rlrl}& s=a(n)-k& & \text{(末尾の連続k個の"1"を削除)}\\ & t={(s^{-1}-1)}^{-1}& & \text{(末尾の"0"を削除)}\\ & u=t+1& & \text{(末尾に"1"を付加)}\\ & a(n+1)={(u^{-1}+k)}^{-1}& & \text{(末尾に連続k個の"0"を付加)}\end{array}}$

順に代入して

${\displaystyle \begin{array}{rl}a(n+1)& ={({({({(a(n)-k)}^{-1}-1)}^{-1}+1)}^{-1}+k)}^{-1}\\ & ={({(\frac{a(n)-k}{1-a_n+k}+1)}^{-1}+k)}^{-1}\\ & ={((1-a(n)+k)+k)}^{-1}\\ & ={(2k+1-a(n))}^{-1}\end{array}}$

${\displaystyle \begin{array}{rl}a(n+1)& ={(2k+1-a(n))}^{-1}\end{array}}$

ここで
$k=\lfloor a(n)\rfloor$
$\{a(n)\}=a(n)-k$
なので

${\displaystyle \begin{array}{rl}a(n+1)& =\frac{1}{\lfloor a(n)\rfloor +1-\{a(n)\}}\end{array}}$

できました!

これが「すべての正の有理数を作る式」です!

練習問題

問題 $1$ ～ $3$

さて、日曜数学会のスライドの最後に $3$ つの練習問題を出しました。ここに再掲します。

このすぐ下に解答を置きますので、自分で考えたい人のために少しスキマをあけておきます。
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

解答 $1$ ～ $3$

解答1

これは記事中の計算を単純に入れ替えるだけでOKです。
実際にやってみると

${\displaystyle \begin{array}{rlrl}& s={(a(n{)}^{-1}-k)}^{-1}& & \text{(末尾の連続k個の"1"を削除)}\\ & t=s-1& & \text{(末尾の"0"を削除)}\\ & u={(t^{-1}+1)}^{-1}& & \text{(末尾に"1"を付加)}\\ & a(n+1)=u+k& & \text{(末尾に連続k個の"0"を付加)}\end{array}}$

順に代入して

${\displaystyle \begin{array}{rl}a(n+1)& ={({({(a(n{)}^{-1}-k)}^{-1}-1)}^{-1}+1)}^{-1}+k\\ & ={(\frac{a(n{)}^{-1}-k}{1-a(n{)}^{-1}+k}+1)}^{-1}+k\\ & =2k+1-a(n{)}^{-1}\end{array}}$

${\displaystyle \begin{array}{rl}a(n+1)& =2k+1-a(n{)}^{-1}\end{array}}$

ここで
$k=\lfloor a(n{)}^{-1}\rfloor$
$\{a(n{)}^{-1}\}=a(n{)}^{-1}-k$
なので

${\displaystyle \begin{array}{rl}a(n+1)& =\lfloor a(n{)}^{-1}\rfloor +1-\{a(n{)}^{-1}\}\end{array}}$

この式もまた、全ての正の有理数をもれなくダブりなく１回ずつ産み出す式となっています!
$2$つの式からできる数列を比較してみましょう。

2つの「すべての正の有理数を作る式」

双対らしさを感じていただけますでしょうか。
この$2$つの式は、実に美しい関係だと思います。

解答2

まずは本当にそうなるのか確かめてみましょう。

${\displaystyle a\left(\lfloor \frac{4}{3}\cdot 2^{n-1}\rfloor \right)}$

の方は ${\displaystyle \frac{1}{1}},{\displaystyle \frac{1}{2}},{\displaystyle \frac{3}{2}},{\displaystyle \frac{3}{5}},{\displaystyle \frac{8}{5}},\cdots$

${\displaystyle a\left(\lfloor \frac{5}{3}\cdot 2^{n-1}\rfloor \right)}$

の方は ${\displaystyle \frac{1}{1}},{\displaystyle \frac{2}{1}},{\displaystyle \frac{2}{3}},{\displaystyle \frac{5}{3}},{\displaystyle \frac{5}{8}},\cdots$

となり、確かに分子・分母ともにフィボナッチ数になっています。

実は、カッコの中にある ${\displaystyle \frac{4}{3}},{\displaystyle \frac{5}{3}}$ をそれぞれ二進数の小数で表すと

${\displaystyle \frac{4}{3}}=1.0101010101{\cdots }_{(2)}$

${\displaystyle \frac{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

まずは第 $n$ 項の分母と、第 $n+1$ 項の分子を見比べてみましょう。

第n項の分母と、第n+1項の分子に注目

お気づきいただけましたでしょうか。どの位置を見ても

　　　第 $n$ 項の分母 $=$ 第 $n+1$ 項の分子

となっていますね!
それでは、第 $n$ 項の分母 $=$ 第 $n+1$ 項の分子が必ず成り立つことを証明しましょう。

$a(n)={\displaystyle \frac{Q}{P}}$ とします。($P,Q$は互いに素)

$Q$ を $P$ で割った商を $s$ 、あまりを $q$ とおくと

$\lfloor \frac{Q}{P}\rfloor =s,\lfloor \frac{Q}{P}\rfloor =\frac{q}{P}$

となります。
したがって

　　　　　${\displaystyle \begin{array}{rl}a(n+1)& =\frac{1}{\lfloor \frac{Q}{P}\rfloor +1-\left\{\frac{Q}{P}\right\}}\\ & =\frac{1}{s+1-\frac{q}{P}}\\ & =\frac{P}{P(s+1)-q}\end{array}}$

ですから、
　　　　　${\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原子数列に関する記事群の目次

　みなさんもいろいろ遊んでみてください。
　そして、何か情報がありましたらコメント等で教えてください。