N進じゃない位取り記数法

はじめに

　この記事では位取り記数法について私なりに色々考えてみた話を紹介していきます。
　皆さんご存じのように私たちが普段$2021$とか$3.1415\dots$とかのように数値を表すのに使っている記法は$10$進位取り記数法と呼ばれています。これは、平たく言うと、数字の各桁に$10$のべきを対応させた記数法となっています。
$$\begin{array}{rcl}2021& =& 2\cdot {10}^3+0\cdot {10}^2+2\cdot {10}^1+1\cdot {10}^0\\ \pi =3.14\dots & =& 3\cdot {10}^0+1\cdot {10}^{-1}+4\cdot {10}^{-2}+\cdots \\ \dots d_1{d}_0.d_{-1}{d}_{-2}\dots & =& \cdots +{10}^1{d}_1+{10}^0{d}_0+{10}^{-1}{d}_{-1}+{10}^{-2}{d}_{-2}+\cdots \end{array}$$
　このように数字の各桁に何らかの値を掛けて数値を表す記法を位取り記数法といいます。位取り記数法は基本的に$10$進法や$2$進法という$N$進法
$$\dots d_1{d}_0.d_{-1}{d}_{-2}{\dots }_{(N)}=\cdots +N^1{d}_1+N^0{d}_0+N^{-1}{d}_{-1}+N^{-2}{d}_{-2}+\cdots$$
として使われるのが一般的ですが、そろばんの二五進法
$$01|12|02|13=(0\cdot 5+1)\cdot {10}^3+(1\cdot 5+2)\cdot {10}^2+(0\cdot 5+2)\cdot {10}^1+(1\cdot 5+3)\cdot {10}^0$$
($|$で各串の境界を表し、左の数字が天、右の数字が地の状態を表すものとした)や時間を表す記数法
$$11:30:25=(1\cdot 10+1)\cdot {60}^2+(3\cdot 10+0)\cdot 60+(2\cdot 10+5)\text{秒}$$
など少し変則的な記数法も使われています。
　数学クラスタではしばしば位取り記数法の各桁にある数列を整列させたり、各桁を並べ替えたりして遊ぶようなことがあります。
$$\begin{array}{rl}111111& =3\cdot 7\cdot 11\cdot 13\cdot 37\\ {123}_{(29)}& ={321}_{(17)}\end{array}$$
でもこういうのって大体$10$進法や$N$進法止まりで、もっと一般の記数法で遊ばれることは少ないように感じます(尤も専用の記法がないだけで実質的に変則的な記数法で遊んでいることもありますが)。それはちょっともったいない気がしたので私なりに$N$進じゃない記数法について軽く考察してみることにしました。

位取り記数法

定義

　まず位取り記数法に求められる要件について定めておきましょう。

　とりあえず非負整数を表現できるものとして次のような性質は欲しいです。

　この条件と単調増加性から$A_k$未満の任意の非負整数$n$は
$$n=d_{k-1}\dots d_2{d}_1{d}_0{}_{(\mathit{A})}(0\le d_l<c_l)$$
のように書けるので
$$A_k=1+\sum _{l=0}^{k-1}{A}_l(c_l-1)$$
である必要があります。特に漸化式
$$A_{k+1}=A_k+A_k(c_k-1)=c_k{A}_k$$
が成り立つので$1=d_0{}_{(\mathit{A})}=A_0{d}_0$と表せることから$A_0=1$に注意すると
$$A_k=\prod _{l=0}^{k-1}{c}_l$$
であればよいことになります。よって以下のようにまとめられます。

　私たちが普段使っている記数法が上手くいってるのは
$$A_k=\prod _{l=0}^{k-1}{c}_l$$
というカラクリがあったんですね。
　ちなみに負の方向にも
$$A_{-k}=\frac{1}{c_{-k}}{A}_{-(k-1)}=(\prod _{l=1}^k{c}_{-l}{)}^{-1}$$
と伸ばして
$$\begin{array}{rl}r& =\dots d_1{d}_0.d_{-1}{d}_{-2}\dots {}_{(\mathit{A})}\\ & =\cdots +A_1{d}_1+A_0{d}_0+A_{-1}{d}_{-1}+A_{-2}{d}_{-2}+\cdots \end{array}$$
と表すことで任意の有理数や実数まで表現することができます(仮数は$0\le d_{-k}<c_{-k}$)。

簡単な性質

仮数の決定

　ある非負整数$n$が与えられたときその$\mathit{A}$進展開は次にようにして求められます。
　まず$c_0$から順に割り算をして行き、商と余りを求めます。
$$\begin{array}{rcl}n\mathbf{\nabla }\mathbf{\cdot }{c}_0& =& q_0\cdots r_0\\ q_0\mathbf{\nabla }\mathbf{\cdot }{c}_1& =& q_1\cdots r_1\\ q_1\mathbf{\nabla }\mathbf{\cdot }{c}_2& =& q_2\cdots r_2\\ & ⋮& \\ q_{k-1}\mathbf{\nabla }\mathbf{\cdot }{c}_k& =& 0\cdots r_k\end{array}$$
このとき$n$の$\mathit{A}$進展開は$n=r_k\dots r_2{r}_1{r}_0{}_{(\mathit{A})}$となります。

　また一般の非負実数$r$の小数部分$f=r-[r]$については以下のように求められます。
　まず$c_{-1}$から順に掛け算をして行き、整数部分$r_{-k}$と小数部分$f_k$を求めます。
$$\begin{array}{rcl}{c}_{-1}f& =& r_{-1}+f_1\\ c_{-2}{f}_1& =& r_{-2}+f_2\\ c_{-3}{f}_2& =& r_{-3}+f_3\\ & ⋮& \end{array}$$
このとき$f=r-[r]$の$\mathit{A}$進展開は$f=0.r_{-1}{r}_{-2}{r}_{-3}\dots {}_{(\mathit{A})}$となります。

四則演算

　足し算引き算については$N$進法の場合とやることは変わりません。足し算
$$\dots d_2{d}_1{d}_0{}_{(\mathit{A})}+\dots e_2{e}_1{e}_0{}_{(\mathit{A})}=\dots f_2{f}_1{f}_0{}_{(\mathit{A})}$$
は$d_k$と$e_k$(と繰り上がり)の和が$c_k$未満のとき
$$f_k=d_k+e_k(+\text{繰り上がり})$$
とし、$c_k$以上のとき一桁繰り上がって
$$f_k=d_k+e_k(+\text{繰り上がり})-c_k$$
とするだけです(引き算についても同様)。
　掛け算割り算についてはおそらく特に一般的な方法がなく、かなり煩雑なことになります。せめて任意の$i,j$にある$k_{i,j}$が存在して$A_i{A}_j=A_{k_{i,j}}$のような関係が成り立ってくれているとある程度の定式化はできそうですが、おまけとして示すようにそのような性質を持つものは$N$進法(に類似するもの)のみに限られることがわかるのでどうしようもないです。

約数判定

　$10$進法ではある数が$2^k$や$5^k$で割り切れるか調べるには下$k$桁が$2^k$や$5^k$で割り切れるかどうかを確かめればよい、という約数判定がありました。
$$\begin{array}{rlrl}{2}^3& \nmid 28& & \therefore 2^3\nmid 1028\\ 5^3& \mid 125& & \therefore 5^3\mid 1125\end{array}$$

これは一般の$\mathit{A}$進法でも似たようなことができます。と言っても至極単純なことで、ある数が$d(d\mid A_k)$で割り切れるか調べるには下$k$桁が$d$で割り切れるかどうかを確かめればよい、という話です。漸化式$A_{l+1}=c_l{A}_l$が成り立っているので当然と言えば当然ですね。ついでに言うと合同式
$$\dots d_2{d}_1{d}_0{}_{(\mathit{A})}\equiv d_{k-1}\dots d_2{d}_1{d}_0{}_{(\mathit{A})}(\mathrm{mod}d)$$
が言えます。

階乗進法と問題点

　というわけで$N$進じゃない記数法を考えてみましょう。とりあえず$c_k=k+2$とした階乗進法
$$\dots d_2{d}_1{d}_0{}_{(!)}=\dots d_2\cdot 3!+d_1\cdot 2!+d_0\cdot 1!$$
なんてものを考えたくなります。階乗進法では一桁増えるごとに階乗$n!$の速さで大きくなるので、十分に大きい同じ数を表すのに指数関数$N^n$の速さで大きくなる$N$進法より少ない桁数で済みます。ただ$N$桁程度の$N$進数だったら階乗進法で表すより$N$進法で表した方が少ない桁数で済むのでよっぽど大きい数じゃない限り実用性は低そうです。
${100000}_{(3)}={20011}_{(!)}$($6$桁$\to 5$桁)
$100000={23551220}_{(!)}$($6$桁$\to 8$桁)
${10}^{30}={37\mathrm{MFCDG}58464\mathrm{CF}8\mathrm{BC}01182251220}_{(!)}$($31$桁$\to 28$桁)

小数展開

　階乗進法は小数展開に少し面白い性質があります。
$$d_0.d_{-1}{d}_{-2}{d}_{-3}\dots =d_0+\frac{d_{-1}}{2!}+\frac{d_{-2}}{3!}+\frac{d_{-3}}{4!}+\cdots (0\le d_0\le 1,0\le d_{-k}\le k)$$
$N$進法においては大抵の無理数に対し、それが恣意的に作られたものでなければ、その小数展開に目に見えた規則性はありませんが、階乗進法においては規則性が見られる場合があります。
$$\begin{array}{rclrc}e& =& 2+\sum _{n=2}^{\mathrm{\infty }}\frac{1}{n!}& =& 10.11111{\dots }_{(!)}\\ \sinh 1& =& 1+\sum _{n=1}^{\mathrm{\infty }}\frac{1}{(2n+1)!}& =& 1.010101{\dots }_{(!)}\\ \cosh 1& =& 1+\sum _{n=1}^{\mathrm{\infty }}\frac{1}{(2n)!}& =& 1.101010{\dots }_{(!)}\\ e^{-1}& =& \sum _{n=0}^{\mathrm{\infty }}\frac{2n}{(2n+1)!}& =& 0.020406080\mathrm{A}{\dots }_{(!)}\\ \sin 1& =& \sum _{n=0}^{\mathrm{\infty }}(\frac{4n+1}{(4n+2)!}+\frac{4n+2}{(4n+3)!})& =& 0.120056009\mathrm{A}{\dots }_{(!)}\\ \cos 1& =& \sum _{n=0}^{\mathrm{\infty }}(\frac{4n}{(4n+1)!}+\frac{4n+1}{(4n+2)!})& =& 0.1004500890{\dots }_{(!)}\end{array}$$
このように整数係数なマクローリン展開を持つ関数の特殊値といった限られた場合くらいにしかこのような性質は見られませんが、ネイピア数$e$のような馴染み深い超越数がこのような規則的な小数展開を持つのは中々面白いですね。

問題点

　ただ階乗進法には実用的にちょっと問題があります。上でもしれっと$\mathrm{A}$とか$\mathrm{B}$とか出てきたように上や下に$10$桁以上伸びる数を表現するには$0$から$9$までの数字だけでは足りなくなってしまいます。そこで$32$進法などでも使われているように$9$の先に$\mathrm{A},\mathrm{B},\mathrm{C}\dots ,\mathrm{Z}$と延長することで$0$から$35$までの仮数を一桁で表すことができますが、それでも上や下に$36$桁以上伸びる数を表現するには足りません。そう、階乗進数では$k$桁目の仮数は$k$個必要なのですべての自然数に対してなんらかの記号を割り当てないといけないのです。
　じゃあ二桁以上使って仮数を表わせばいいじゃんとなりますが、$10$進法で表すにしても
$$12!-1=\{11\}\{10\}{87654321}_{(!)}$$
のようになりますし、階乗進法で表すにしても
$$6!-1=\{{21}_{(!)}\}\{{20}_{(!)}\}\{{11}_{(!)}\}{11}_{(!)}$$
のようにかなりわかりづらい見た目になってしまいます。
　このように仮数が無限に必要になる問題を防ぐには$c_k$が有限である必要があり、特に仮数を$\mathit{A}$進法で表したとき二桁以上になってしまう問題を防ぐには$c_k\le c_0$である必要があります。$c_0$を固定したとき、$c_k\le c_0$を満たすような記数法のうち、桁数の増加に伴う発散速度が一番大きいもの(任意の数を表すのに一番桁数が少なくて済むもの)は$N$進法($N=c_0$)となるのでそういう意味で$N$進法は最も理に適った記数法であると言えます。

まとめ

　$N$進法は掛け算割り算が定式的に計算可能で、仮数が有限である記数法のうち実用的に最も理に適った記数法なので、いくら未知の文化を発展させた宇宙人が飛来してきても記数法は$N$進法に則ったものを使っている可能性が高いですね(ローマ数字のようなものを使っていない限り)。
　$N$進法最強！$N$進法最強！

おまけ

掛け算の法則と$N$進数

　一般の位取り記数法における掛け算割り算について「任意の$i,j$にに対しある$k_{i,j}$が存在して$A_i{A}_j=A_{k_{i,j}}$のような関係が成り立つものは$N$進法(に類似するもの)のみに限られることがわかる」といったことを言いましたが、ここではそのことについて解説していきます。
　$A_k$は単調増加なので$A_{i-1}<A_j<A_{i+1}$ならば$A_j=A_i$が成り立つことを利用すると次のようにして
$$\cdots =c_2=c_1=c_0=c_{-1}=c_{-2}=\cdots$$
すなわちこれは$N$進法($N=c_0$)であることが言えます。

整数の掛け算がしやすい記数法

　さて数学的帰納法により$A_k=N^k$がわかりましたが、これは前提として$A_i{A}_j=A_{k_{i,j}}$という関係式において$i,j$が負の値を取ることを許しています。
　では$i,j$が非負のときのみを考えるとどうなるでしょうか。

　結論から言うと以下のような命題が成り立ちます。

　このように結局$N$進法に類似した記数法となるわけです。
　ちなみにこのような$A_k$に対して集合
$$M=\{e_k\mid k\in {\mathbb{Z}}_{\ge 0}\}$$
は$e_i+e_j=e_{k_{i,j}}\in M$と和について閉じており、また$e_0=0\in M$と加法単位元も持っているのでこれはモノイドと呼ばれる集合の一つとなります。特に非負整数${\mathbb{Z}}_{\ge 0}$の部分モノイドであるので自然数モノイド(numerical monoid)と呼ばれます。詳しくは 英語版Wikipedia を見てください。
　また先に示したように$k,i,j$が負のときにも$A_k=N^{e_k}$(ただし$k<0$ならば$e_k<0$)が成り立ち、$e_i+e_j=e_{k_{i,j}}$という関係があるならば$e_k=e_{1}k$が成り立つのでしたが、これは有理整数環$\mathbb{Z}$の(加法についての)部分モノイドで負の数と正の数を同時に含むようなもの$I=\{e_k\mid k\in \mathbb{Z}\}$は$\mathbb{Z}$の(単項)イデアルであるということを示唆しています。

　我ながらこんな証明よく考えたなーと思います。
　まあとにかく$N$進法ってよくできてるんだなーって思いました。

階乗進法のレピュニット

$$\begin{array}{rcl}{1}_{(!)}& =& 1\\ {11}_{(!)}& =& 3\\ {111}_{(!)}& =& 9=3^2\\ {1111}_{(!)}& =& 33=3\cdot 11\\ {11111}_{(!)}& =& 153=3^2\cdot 17\\ {111111}_{(!)}& =& 873=3^2\cdot 97\\ {1111111}_{(!)}& =& 5913=3^4\cdot 73\\ {11111111}_{(!)}& =& 46233=3^2\cdot 11\cdot 467\\ {111111111}_{(!)}& =& 409113=3^2\cdot 131\cdot 347\\ {1111111111}_{(!)}& =& 4037913=3^2\cdot 11\cdot 40787\\ {11111111111}_{(!)}& =& 43954713=3^2\cdot 11\cdot 443987\\ {111111111111}_{(!)}& =& 522956313=3^2\cdot {11}^2\cdot 23\cdot 20879\\ {1111111111111}_{(!)}& =& 6749977113=3^2\cdot 11\cdot 821\cdot 83047\\ {11111111111111}_{(!)}& =& 93928268313=3^2\cdot 11\cdot 2789\cdot 340183\\ {111111111111111}_{(!)}& =& 1401602636313=3^2\cdot 11\cdot 107\cdot 509\cdot 259949\\ {1111111111111111}_{(!)}& =& 22324392524313=3^2\cdot 11\cdot 225498914387\\ {11111111111111111}_{(!)}& =& 387011820620313=3^2\cdot 11\cdot 163\cdot 20143\cdot 1162943\\ {111111111111111111}_{(!)}& =& 6780385526348313=3^2\cdot 11\cdot 19727\cdot 3471827581\\ {1111111111111111111}_{(!)}& =& 128425485935180313=3^2\cdot 11\cdot 29\cdot 43\cdot 1621\cdot 641751001\\ {11111111111111111111}_{(!)}& =& 2561327494111820313=3^2\cdot {11}^2\cdot 53\cdot 67\cdot 662348503367\end{array}$$

何かありそうと思いましたが特に何もなさそうでした。$N$進数のレピュニットが
$$\sum _{k=0}^n{x}^k=\frac{x^k-1}{x-1}$$
に$x=N$を代入したものだったのに対して階乗進数のレピュニットは
$$\sum _{k=1}^n{x}^{\bar{k}}=x+x(x+1)+x(x+1)(x+2)+\cdots$$
に$x=1$を代入したものとみなせます($x^{\bar{k}}$は上昇階乗)。
$$\begin{array}{rcl}\sum _{k=1}^1{x}^{\bar{k}}& =& x\\ \sum _{k=1}^2{x}^{\bar{k}}& =& x(x+2)\\ \sum _{k=1}^3{x}^{\bar{k}}& =& x(x+2{)}^2\\ \sum _{k=1}^4{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3))\\ & =& x(x+2)(x^2+5x+5)\\ \sum _{k=1}^5{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3)(x+5))\\ & =& x(x+2)(x^3+9x^2+24x+17)\\ \sum _{k=1}^6{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3)(x+5{)}^2)\\ & =& x(x+2)(x^4+14x^3+68x^2+131x+77)\\ \sum _{k=1}^7{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3)(x+5)(x+5+(x+4)(x+6)))\\ & =& x(x+2)(x^5+20x^4+151x^3+529x^2+833x+437)\\ \sum _{k=1}^8{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3)(x+5)(x+5+(x+4)(x+6)(x+8)))\\ & =& x(x^6+27x^5+290x^4+1571x^3+4458x^2+6107x+2957)\\ \sum _{k=1}^9{x}^{\bar{k}}& =& x(x+2)(x+2+(x+1)(x+3)(x+5)(x+5+(x+4)(x+6)(x+8{)}^2))\\ & =& x(x+2)(x^7+35x^6+505x^5+3870x^4+16860x^3+41164x^2+50819x+23117)\\ \sum _{k=1}^{10}{x}^{\bar{k}}& =& (x+2+(x+1)(x+3)(x+5)(x+5+(x+4)(x+6)(x+8)(x+8+(x+7)(x+9))))\\ & =& x(x+2)(x^8+44x^7+819x^6+8387x^5+51379x^4+191167x^3+416230x^2+473387x+204557)\end{array}$$

うーん。