区間(0,1)有理数の整列　～ナンバリング　　　元祖・のび太算の利用

$${\dfrac{2}{5} + \dfrac{1}{2} = \dfrac{2+1}{5+2} =\dfrac{3}{7}}$$

これは、誤った計算です。マンガドラえもんの中で、のび太の答案にありそうな間違いで、このような計算を「のび太算」と呼んでいたと記憶してます。確認のため検索したところ、全然見つからず、それどころか百マス計算か何かで同様の名前が使われていて、そちらの方ばかりがヒットする。

「のび太算」の命名者は、分母同士の和を分母に、分子同士の和を分子にするこの計算を「愚かな間違い」的な意味で揶揄して使っていたと思いますが、実は、興味深い演算で有用です。以下いくつかの性質を述べます。

$${a,b,c,d}$$を非負整数とします。
分数$${a/b}$$と分数$${c/d}$$の間に、分数(a+c)/(b+d)はあります。これは、

$${(\dfrac{a}{b}-\dfrac{a+c}{b+d})(\dfrac{a+c}{b+d}-\dfrac{c}{d})=\dfrac{(ad-bc)^2}{bd(b+d)^2}≧0}$$

から示されます。

分数$${a/b}$$と分数$${c/d}$$において、$${|ad-bc|=1}$$を満たす時、
この二つの分数はお互いに「近所」にあると呼ぶことにします。

$${a/b}$$と$${c/d}$$が近所にあるなら、$${a/b}$$と$${(a+c)/(b+d)}$$は
近所にあるし、$${c/d}$$と$${(a+c)/(b+d)}$$も近所にあります。
例えば、2/5と1/2は|2×2-5×1|=1なので近所にあります。のび太算により得られる3/7は、|2×7-5×3|=1、あるいは、|1×7-2×3|=1のように、演算元の二つと近所にあることが確認できます。

尚、三つの分数x,y,zがあり、xとy、xとzが近所であるからといって、yとzも近所であるとは限りません。
上で挙げた例の、2/5、1/2、3/7はどの二つも近所です。
一方、1/2は、2/5と近所だし、(3+k)/(5+2k)　（ただし、kは非負整数）等とも近所です。しかし、2/5と(3+k)/(5+2k)は、近所ではありません。

ある有理数　$${0 < m/n < 1}$$　が与えられ、これがある二つの正の有理数$${a/b}$$と$${c/d}$$ののび太算でできたものとした時、$${a/b,c/d}$$の組み合わせは、複数あるが、「$${a/b}$$と$${c/d}$$は近所」という条件を加えると、$${a/b}$$と$${c/d}$$は入れ替えを除いてユニークに決まります。

数学的には、$${a+c=m,b+d=n,ad-bc=±1}$$の様に、変数が四つで式が三つの不定方程式を解くことになるので、媒介変数一つを用いて解を表すことになりますが、$${a,b,c,d}$$が非負整数という条件によって、一つに確定するという見方もできます。

しかし、次のような方法で全ての有理数$${0 < m/n < 1}$$が作成可能であることを考えると、納得できると思う。

---

長い直線を書き、左端に　0/1　、右端に　1/1　を分数として書く。
ここまでは、前準備です。以降、ループ部分です。
ループ
数直線上にいくつかの分数が書かれている。ｎ個の分数が書かれているとすると、n-1箇所の、「数字と数字の間」が存在するが、その「数字と数字の間」に印を付け、そこに、両隣ののび太算の結果を、分数として書く。
これを、n-1箇所全てで行う。
後は、ループの先頭に戻って、同じ事を繰り返します。

0/1と1/1は近所です。数直線の真ん中に1/2を書いて、一回目のループが終了します。1回目は1個の数字が書かれました。
$${\dfrac{0}{1}　　　　　　　　　　 \dfrac{1}{2}　　　　　　　　　 \dfrac{1}{1}}$$

二回目のループでは、0/1と1/2の間に1/3、1/2と1/1の間に2/3を書きます。2回目は2個の数字が書かれました。
$${\dfrac{0}{1}　　　　　　 \dfrac{1}{3}　　　　　　 \dfrac{1}{2}　　　　　　 \dfrac{2}{3}　　　　　　 \dfrac{1}{1}}$$

三回目のループでは、0/1と1/3の間に1/4、1/3と1/2の間に2/5、1/2と2/3の間に3/5、2/3と1/1の間に3/4を書きます。3回目は4個の数字が書かれます。
$${\dfrac{0}{1}　　　 \dfrac{1}{4}　　　 \dfrac{1}{3}　　　 \dfrac{2}{5}　　　 \dfrac{1}{2}　　　 \dfrac{3}{5}　　　 \dfrac{2}{3}　　　 \dfrac{3}{4}　　　 \dfrac{1}{1}}$$

次のループでは、
$${\dfrac{0}{1} 　\dfrac{1}{5} 　\dfrac{1}{4} 　\dfrac{2}{7}　 \dfrac{1}{3}　 \dfrac{3}{8}　 \dfrac{2}{5}　 \dfrac{3}{7}　 \dfrac{1}{2}　 \dfrac{4}{7}　 \dfrac{3}{5}　 \dfrac{5}{8}　 \dfrac{2}{3}　 \dfrac{5}{7}　 \dfrac{3}{4}　 \dfrac{4}{5}　 \dfrac{1}{1}}$$

次のループでは、
$${{\footnotesize \dfrac{0}{1} \dfrac{1}{6} \dfrac{1}{5} \dfrac{2}{9} \dfrac{1}{4} \dfrac{3}{11} \dfrac{2}{7} \dfrac{3}{10} \dfrac{1}{3} \dfrac{4}{11} \dfrac{3}{8} \dfrac{5}{13} \dfrac{2}{5} \dfrac{5}{12} \dfrac{3}{7} \dfrac{4}{9} \dfrac{1}{2} \dfrac{5}{9} \dfrac{4}{7} \dfrac{7}{12} \dfrac{3}{5} \dfrac{8}{13} \dfrac{5}{8} \dfrac{7}{11} \dfrac{2}{3} \dfrac{7}{10} \dfrac{5}{7} \dfrac{8}{11} \dfrac{3}{4} \dfrac{7}{9} \dfrac{4}{5} \dfrac{5}{6} \dfrac{1}{1}}}$$

このようにして数直線上に分数を書き加えていきます。
各段階のループが終了した時、隣合う分数は全て、近所です。
大小関係が崩れることもありません。
$${(0,1)}$$区間の有理数は、必ず、どこかに現れます。現れた時、その両隣にある分数が、$${a+c=m,b+d=n,ad-bc=±1}$$の近所関係にある解となります。

この有理数生成過程において、数直線に加えていった順に、有理数に番号を与えます。前準備は除くので、$${1/2}$$が一番目です。

このようにして生成した有理数ですが、番号と有理数の間の変換は高速に行うことができます。次は、某所で、ピタゴラス数関連の話をしていた時に投稿したプログラムです。有理数からそれに対応するピタゴラス数を見つけるのですが、有理数生成時に、ここで紹介した方法を用いています。

有理数のナンバリングと、その逆変換も搭載しているので、ご覧下さい。

有理数のナンバリング、及び、その有理数に対応するピタゴラス数

このプログラムの中の　f2n　は有理数から番号、n2f　は番号から有理数を返す関数です。

void f2n(int *p){  /*  p[0]に1、p[1]に分子,p[2] に分母を入れて呼び出すと、p[0]に順番を返す  */
	int num=p[0],m=p[1],n=p[2],a=p[3],b=p[4],c=p[5],d=p[6];
	int t1=a+c,t2=b+d,x=m*t2-n*t1;     /* x は (m/n)-(t1/t2) の n*t2倍  */

	if(x==0){return;}
	else if(x>0){p[0]=2*num+1;p[3]=t1;p[4]=t2;f2n(p);}
	else{        p[0]=2*num;p[5]=t1;p[6]=t2;f2n(p);}
}
void n2f(int n,int *p){   /*  nを指定すると、nに対応するFarey範囲を返す*/
	if(n==1){p[0]=0;p[1]=1;p[2]=1;p[3]=1;}
	else{
		int q[4];
		n2f(n/2,q);
		if(n%2==1){p[0]=q[0]+q[2];p[1]=q[1]+q[3];p[2]=q[2];p[3]=q[3];}
		else{      p[0]=q[0];p[1]=q[1];p[2]=q[0]+q[2];p[3]=q[1]+q[3];}
	}
}

(0,1)区間の有理数は、通常「値」として認識されますが、それを半分棄てます。与えられた有理数$${m/n}$$に対し、$${a+c=m,b+d=n,ad-bc=-1}$$を要請すると、四つの非負整数$${a,b,c,d}$$が確定します。そこで、有理数$${m/n}$$は区間$${[a/b,c/d]}$$に与えられたラベルと考えることから組んだコードです。

関数　f2n　には、調べたい有理数と、その有理数を含む範囲を放り込みます。すると関数は、
・その有理数は、この範囲のラベルそのものです。
・その有理数は、この範囲の右側の方にあります。範囲を中間より右側に狭め、再調査をして下さい。
・その有理数は、この範囲の左側の方にあります。範囲を中間より左側に狭め、再調査をして下さい。
のいずれかを返します。この「ラベルそのもの」「右側」「左側」の情報を蓄積して、番号に変換してます。

関数　n2f　はこの逆を行っています。
有理数生成において、一回目のループでは1/2の1個が加わります。
二回目のループでは1/3と2/3の2個。k回目のループでは、2^(k-1)個が加わります。新規に加わるメンバーは二分木構造に当てはめることができ、初回の投稿で示した二分木構造のノードへの番号当てはめが、ここでも使われています。n回目のループで加わった有理数は、n-1回目のループで加わった有理数の右側か左側の子として位置づけられています。
番号から、二分木構造のどの位置ノードかが判明するので、ルートからそのノードに向けて範囲を計算しながら進んでいけば、番号に対応する範囲→有理数を見つけられます。

プログラム中、Fareyの文字が見られます。当時はこの生成方法とファレイ数列はほぼ同一のものと思ってその名称を使っていたのですが、ファレイ数列についてよく読んでみると、別物でした。共通する性質はあるのですが、根本は異なります。ここでの方法の根底にはのび太算があります。

#有理数 #整列 #ナンバリング #のび太算 #数学がすき