Maxima で綴る数学の旅

紙と鉛筆の代わりに、数式処理システムMaxima / Macsyma を使って、数学を楽しみましょう

-数学- 分数の足し算の約分とp進展開とpadicsパッケージ

 

f:id:jurupapa:20160529122342j:plain
この記事のコードをJupyter notebook形式で見るにはこちら。

 

tsujimotterさんのブログ記事は難しいやつは読みきれないものも多いのですが、Maximaで計算してみて、記事にさせていただくこともあり、いつも楽しみにしています。そんな中、分数の和で約分が生じる条件にp進数が関係する、という記事を読み、これは試したい、と思いました。

約分が発生する条件を使えば、約分が発生する分数足し算問題を量産することもできるかもしれない!(小学生諸君に怒られそうですが、、、)

以前、p進数入門シリーズで取り上げた、メキシコの大学のJosé Antonio Vallejo先生作成のpadicsパッケージで実際にやってみたいと思います。

 

tsujimotterさんの記事によれば、分数の足し算で約分が発生するための必要十分条件が次のようにまとめられています。

\(\frac{a}{b},\, \frac{c}{d}\)が既約分数、\(p\)を素数とする。\(\frac{a}{b},\, \frac{c}{d}\)の\(p\)進展開の最低次数の係数を\(k, l\)とすると、これらの分数の足し算で\(p\)による約分が起こる条件は、\(k+l=0\, mod\, p\)かつ\(b,\, d\)の\(p\)進附値が同じで正である、ことである。

 \(\frac{a}{b},\, \frac{c}{d}\)が既約であることに注意すれば、この条件は次のように言い換えることもできます。

\(k+l=0\, mod\, p\)かつ\(\frac{a}{b},\, \frac{c}{d}\)の\(p\)進附値が同じで負である

padicsパッケージにはp進展開を行うための関数や、p進附値を求める関数も整備されています。それらを使って計算してみましょう。

 

まずパッケージの読み込みです。maxima-asdfを使っていれば以下の2行でインストール&読み込み完了です。使っていない人は、githubからpadics.macファイルをダウンロードしてload()関数で読み込んでください。

(%i1) install_github("YasuakiHonda","padics","master")$
(%i2) asdf_load_source("padics")$

tsujimotterさんの記事で取り上げられていた分数を例にしてみます。
(%i3) 4/15+9/35;
$$ \tag{${\it \%o}_{3}$}\frac{11}{21} $$

この計算では5の約分が発生したのでした。

これらの分数が約分条件を満たすことを確認してみましょう。まず両方の分数のp進附値を求めてみます。それにはpadic_order(x,p)という関数を使います。xはp進附値を求めたい分数です。またこの場合5での約分ですから、求めるのは5進附値です。
(%i4) [padic_order(4/15,5),padic_order(9/35,5)];
$$ \tag{${\it \%o}_{4}$}\left[ -1 , -1 \right] $$

確かに両方とも5進附値は-1となりました。分母だけが5で1回割り切れる、ということがわかります。

次にそれぞれの分数の5進展開を求めます。padicsパッケージには有理数をp進展開し、その最初のn桁を求めるhensel(q,p,n)という関数があるので、これを使います。
(%i5) [hensel(4/15,5,6),hensel(9/35,5,6)];
$$ \tag{${\it \%o}_{5}$}\left[ \left[ \left[ -1 \right] , 3 , 3 , 1 , 3 , 1 , 3 \right] , \left[ \left[ -1 \right] , 2 , 2 , 1 , 4 , 2 , 3 \right] \right] $$

hensel(4/15,5,6)は4/15の5進展開の最初の6桁を出力します。出力が[[-1],3,3,1,3,1,3]となっています。最初の-1は最小次数が-1であることを示します。残りの3,3,1,3,1,3は5^(-1),5^0,5^1,,,5^4の係数です。従って最小次数の係数は最初の3となります。

hensel(9/35,5,6)は9/35の5新展開の最初の6桁を出力します。最小次数は-1で最小次数の係数は2,2,1,4,2,3の最初の2です。

ちなみにp進展開の最小次数はp進附値と一致します。hensel(q,p,n)、便利です。

 

2つの分数が\(p=5\)での約分の条件を満たすかどうか確認するためには、本当は5進展開の1桁が必要なだけです。
(%i6) [hensel(4/15,5,1),hensel(9/35,5,1)];
$$ \tag{${\it \%o}_{6}$}\left[ \left[ \left[ -1 \right] , 3 \right] , \left[ \left[ -1 \right] , 2 \right] \right] $$

これでそれぞれの分数の5進附値が-1で等しく負であること、5進展開の1桁目が3, 2で足すと5なのでmod 5で0となることが確認できます。つまりこれらの分数を足し算すると5による約分が発生するわけです。

 

ちなみに、有理数qに対してp進展開の最初のn桁を対応させたもの(つまり上記の出力結果)は、ヘンゼルコードと呼ばれています。そのため関数名がhensel(q,p,n)なのです。

padicsパッケージには実はヘンゼルコードから対応する有理数qを求める関数hensel_to_farey(hc,p)という関数もあります。これを使うと約分のある足し算に使える分数を生成できます。やってみましょう。11で約分を発生させることとして、適当に分母を決めます。
(%i7) 11*13*8;
$$ \tag{${\it \%o}_{7}$}1144$$

分子も適当に191と決めました。一つ目の分数は191/1144です。これの11進展開を8桁求めてみます。
(%i8) hensel(191/1144,11,8);
$$ \tag{${\it \%o}_{8}$}\left[ \left[ -1 \right] , 3 , 0 , 2 , 5 , 10 , 0 , 7 , 2 \right] $$

191/1144の11進附値は-1で最小次数の係数は3です。

ということは11進附値が-1で最小次数の係数が8であるような分数と足し算すると約分が発生するはずです。11進附値が-1で最小次数の係数が8、それより後ろの桁を適当に1,2,3,5,1,2,3,5とするとヘンゼルコードは[[-1],8,1,2,3,5,1,2,3,5]となります。これが11進展開となるような分数をhensel_to_farey()で計算します。
(%i9) hensel_to_farey([[-1],8,1,2,3,5,1,2,3,5],11);
$$ \tag{${\it \%o}_{9}$}\frac{13223}{53680} $$

では確認のために191/1144と13223/53680を足してみます。
(%i10) 191/1144+13223/53680;
$$ \tag{${\it \%o}_{10}$}\frac{26219}{63440} $$

最小公倍数で通分した後、分子を足して、11で約分が発生して、上記の結果となります。

tsujimotterさんの記事では素数\(p\)による約分が発生する条件が示されました。その簡単な応用として、素数の冪乗\(p^n,\, n \in N\) による約分の発生する条件も簡単にわかります。

\(\frac{a}{b},\, \frac{c}{d}\)の\(p\)進附値が同じで\(-m \left(-m \leq -n, m \in N\right)\)であり、最小次数(\(=-m\)次)の係数\(k,\, l\)が\(k+l=0\, mod\, p\)かつ\(-m+1\)次〜\(-m+n-1\)次の係数の和がmod pでp-1になること。

これは右方向への繰り上がりが発生することで、約分の次数が上がると理解することができます。実際にやってみましょう。今度はいきなり条件に合うヘンゼルコードを作成して、そこから分数を生成します。

素数\(p=7\)で考えることにし、7進附値が-2, -2次の係数の和が7, -1次の係数の和が6となるようなヘンゼルコードの組を適当に作ってみました。[[-2],1,3,4,1,3,1,3,1]と[[-2],6,3,4,1,4,1,4,1]です。これらを分数に変換します。
(%i11) hensel_to_farey([[-2],1,3,4,1,3,1,3,1],7);
$$ \tag{${\it \%o}_{11}$}\frac{1459}{1176} $$
(%i12) hensel_to_farey([[-2],6,3,4,1,4,1,4,1],7);
$$ \tag{${\it \%o}_{12}$}\frac{757}{2352} $$

得られた2つの分数を足してみます。
(%i13) 1459/1176+757/2352;
$$ \tag{${\it \%o}_{13}$}\frac{25}{16} $$

1176と2352の最小公倍数は2352、結果の分数は25/16なので、\(7^2=49\)で約分が発生し、さらに(7進展開とは別に)3でも約分が発生しました。

これで、約分の生じる分数足し算を量産することが出来るようになりました。