1

位取り記数法の性質の良さ

180
1
$$$$

要約

位取り記数法を$N$進法から一般化し、完全性、一意性、単調性という性質を定義しました。また、性質の間の関係を考察し、完全性と一意性を満たす位取り記数法は$N$進法にある程度近いものに限ることを示しました。

導入

現在多くのヒトが使用している10進法は次のように表現できます。

任意の非負整数$n$について、非負整数$k$に対し整数$0\leq a_k\leq 9$が存在して,
\begin{equation*} n=\sum_{k=0}^\infty a_k10^k =a_0\cdot 1+a_1\cdot 10+a_2\cdot 10^2+\cdots \end{equation*}
が成立する。 ただし、有限個の$k$を除いて$a_k=0.$

また、時間の表現が60進法になっているという話もありますが、それは次のように表現できます。

\begin{equation*} n =s\cdot 1+m\cdot 60+h\cdot 60^2+d\cdot 12\cdot 60^2 \end{equation*}

上の例では$10^k$のまとまりを使っていますが、下の例では途中で$12\cdot 60^2$のまとまりが登場しています。この点も踏まえて次のように一般化して性質を考えてみました。

本文

位取り記数法の定義

非負整数$k$に対し、$A_k,D^{(k)}$を正の整数とし、整数列$(D^{(k)})_{k=0}^\infty$$D^{(0)}=1$かつ狭義短調増加とします。
そして、正の整数$N$$0\leq a_k\leq A_k$となる整数$a_k$を用いて

\begin{equation*} \sum_{k=0}^N a_kD^{(k)} \end{equation*}

と書かれる整数について考えます。
$D^{(k)}$が各まとまりを、$A_k$$D^{(k)}$の位(くらい)にとれる値の最大値を指定しているわけですね。10進法ならば$A_k=9,D^{(k)}=10^k$となります。

性質

さらに、位取り記数法の性質を次のように定めます。

位取り記数法の性質
(1)完全性

任意の非負整数$n$に対し,ある$a_k(k=1,\ldots N)$
\begin{equation} n=\sum_{k=0}^N a_kD^{(k)}. \end{equation}

(2)一意性

\begin{equation*} \sum_{k=0}^N a_kD^{(k)} =\sum_{k=0}^{N'} a'_kD^{(k)} \end{equation*}
ならば$N=N'$かつ$a_k=a'_k(k=1,\ldots N)$.

(3)単調性

$a_N< a'_N$ならば$\displaystyle \sum_{k=0}^N a_kD^{(k)} <\sum_{k=0}^{N'} a'_kD^{(k)}.$

完全性は任意の非負整数が位取り記数法で表記できるということであり、一意性は表記できるならばやり方はただ一つということであり、そして単調性は桁の増え方が10進法と同様ということです。

それでは、性質を満たしたり満たさなかったりする例を見てみます。

(1)$A_k=8,D^{(k)}=10^k$は完全性を満たさないが一意性と単調性を満たす。
(2)$A_k=10,D^{(k)}=10^k$は一意性と単調性を満たさないが完全性を満たす。
(3)$A_k=9,D^{(k)}=10^k$は完全性と一意性と単調性を満たす。

また、次のような例も考えられます。

(4)$A_0=1,A_1=2,A_2=2,A_k=21(k\geq 3)$とし、$D^{(0)}=1,D^{(1)}=4,D^{(2)}=6,D^{(k)}=22^{k-2}(k\geq 3)$とする。このとき、

n位取り記数法短縮記法
$1$$1$$1$
$2$$\times$$\times$
$3$$\times$$\times$
$4$$0+1\cdot 4$$10$
$5$$1+1\cdot 4$$11$
$6$$0+0\cdot 4+1\cdot 6$$100$
$7$$1+0\cdot 4+1\cdot 6$$101$
$8$$0+2\cdot 4$$20$
$9$$1+2\cdot 4$$21$
$10$$0+1\cdot 4+1\cdot 6$$110$
$11$$1+1\cdot 4+1\cdot 6$$111$
$12$$0+0\cdot 4+2\cdot 6$$200$
$13$$1+0\cdot 4+2\cdot 6$$201$
$14$$0+2\cdot 4+1\cdot 6$$120$
$15$$1+2\cdot 4+1\cdot 6$$121$
$16$$0+1\cdot 4+2\cdot 6$$210$
$17$$1+1\cdot 4+2\cdot 6$$211$
$18$$\times$$\times$
$19$$\times$$\times$
$20$$0+2\cdot 4+2\cdot 6$$220$
$21$$1+2\cdot 4+2\cdot 6$$221$
$22$$0+0\cdot 4+0\cdot 6+1\cdot 22$$1000$
$23$$1+0\cdot 4+0\cdot 6+1\cdot 22$$1001$
$24$$\times$$\times$
$25$$\times$$\times$
$26$$0+1\cdot 4+0\cdot 6+1\cdot 22$$1010$

となり、完全性と単調性を満たさないが一意性を満たす。

(5)$A_0=2,A_1=2,A_2=2,A_k=21(k\geq 3)$とし、$D^{(0)}=1,D^{(1)}=4,D^{(2)}=6,D^{(k)}=22^{k-2}(k\geq 3)$とする。
このとき、
$3$をこの位取り記数法で表記できず、
$6=0+0\cdot 4+1\cdot 6=2+1\cdot 4$であり、
$0+0\cdot 4+1\cdot 6<0+2\cdot 4$である。
従って完全性も一意性も単調性も満たさない。

以上の例では次のような性質の満たし方が存在することがわかりました。

例番号完全性一意性単調性
(1)$\times$$\circ$$\circ$
(2)$\circ$$\times$$\times$
(3)$\circ$$\circ$$\circ$
(4)$\times$$\circ$$\times$
(5)$\times$$\times$$\times$

これ以外の例は存在するのでしょうか。

性質の関係

実は上の表以外の例が存在しないことが示せます。
まずは必要な補題を示します。

(1)整数$N\geq M\geq 0$
$\displaystyle \sum_{k=M}^Na_kD^{(k)}\neq 0$ならば,$\displaystyle \sum_{k=M}^Na_kD^{(k)}\geq D^{(M)}.$
(2)単調性$\Leftrightarrow $任意の非負整数$K$
$\displaystyle D^{(K+1)}>S^{(K)}:=\sum_{k=0}^{K}A_kD^{(k)}.$

(1)$\displaystyle \sum_{k=M}^Na_kD^{(k)}\neq 0$より$\displaystyle\sum_{k=M}^Na_k\neq 0$だから,
$\displaystyle \sum_{k=M}^Na_kD^{(k)}\geq \sum_{k=M}^Na_kD^{(M)}\geq D^{(M)}.\ \square$
(2)$(\Rightarrow)$$D^{(K+1)}$の位の値を比較すれば定義より明らか.
$(\Leftarrow)$について,$\displaystyle \sum_{k=0}^{N}a_kD^{(k)},\sum_{k=0}^{N}a'_kD^{(k)}$
$a_N< a'_N$のとき,
$\displaystyle \sum_{k=0}^{N}a'_kD^{(k)}-\sum_{k=0}^{N}a_kD^{(k)}$
$\displaystyle=(a'_N-a_N)D^{(N)}+\sum_{k=0}^{N-1}(a'_k-a_k)D^{(k)}$
$\displaystyle \geq D^{(N)}-\sum_{k=0}^{N-1}A_kD^{(k)}>0$だから,
$\displaystyle \sum_{k=0}^{N}a_kD^{(k)}<\sum_{k=0}^{N}a'_kD^{(k)}.\ \square$

完全性と一意性を満たすとき,任意の非負整数$K$に対し
\begin{equation} D^{(K+1)}=S^{(K)}+1=\sum_{k=0}^{K}A_kD^{(k)}+1 \end{equation}

10進法でいえば、99の次が100であり、999の次が1000であるというようなことです。

帰納法を用いて示す.
整数$1\leq n\leq A_0$$1D^{(0)},\ldots ,A_0D^{(0)}$と表記できるから一意性より
\begin{equation} D^{(1)}\geq A_0D^{(0)}+1. \end{equation}
また,完全性より整数$A_0D^{(0)}+1$$\displaystyle \sum_{k=0}^{N}a_kD^{(k)} $と表記すると
$\displaystyle A_0D^{(0)}+1=\sum_{k=0}^{N}a_kD^{(k)}$
$\displaystyle=a_0D^{(0)}+\sum_{k=1}^{N}a_kD^{(k)}$となり,左辺は正だから補題1の(1)より
$\displaystyle (A_0-a_0)D^{(0)}+1=\sum_{k=1}^{N}a_kD^{(k)}\geq D^{(1)}.$
よって
$\displaystyle A_0D^{(0)}+1\leq D^{(1)}\leq (A_0-a_0)D^{(0)}+1.$
左辺と右辺を比較すると$a_0=0$となるから,
\begin{equation} D^{(1)}=A_0D^{(0)}+1. \end{equation}
すなわち$K=0$での成立を示せた.
このとき,整数$1\leq n \leq S^{(1)}$はそれぞれ,
$1D^{(0)},\ldots ,A_0D^{(0)},1D^{(1)},$
$1D^{(0)}+1D^{(1)},\ldots,A_0D^{(0)}+1D^{(1)},2D^{(1)},$
$1D^{(0)}+2D^{(1)},\ldots,A_0D^{(0)}+A_1D^{(1)}$
と表記できる.同様に整数$0\leq K'< K$
\begin{equation} D^{(K'+1)}= S^{(K')}+1 \end{equation}
が成立すると仮定すると,整数$1\leq n \leq S^{(K)}$はそれぞれ
$\displaystyle 1D^{(0)},\ldots , \displaystyle\sum_{k=0}^{K}a_kD^{(k)} ,\ldots, \displaystyle\sum_{k=0}^{K}A_kD^{(k)}$
と表記できる.よって一意性から
\begin{equation} D^{(K+1)}\geq S^{(K)}+1 \end{equation}
が従い,完全性から$\displaystyle S^{(K)}+1=\sum_{k=0}^{N}a_kD^{(k)}$
と表記すると,補題1の(1)より
$\displaystyle\sum_{k=0}^{N}a_kD^{(k)} =a_0D^{(0)}+\cdots+a_KD^{(K)}+\sum_{k=K+1}^{N}a_kD^{(k)}$
だから
$\displaystyle\sum_{k=0}^{K}(A_k-a_k)D^{(k)}+1=\sum_{k=K+1}^{N}a_kD^{(k)}\geq D^{(K+1)}$
となる.従って,
\begin{equation} S^{(K)}+1\leq D^{(K+1)}\leq \sum_{k=0}^{K}(A_k-a_k)D^{(k)}+1 \end{equation}
が従い,$a_0=\cdots=a_K=0$であり,
\begin{equation} D^{(K+1)}=S^{(K)}+1 \end{equation}
となり,$K$での成立が確かめられ,帰納法によって補題が示された. $\square$

整数$1\leq n \leq S^{(K)}$を位取り記数法で表記する箇所は、与えられた$n$がどの$a_k$$a_kD^{(k)}\leq n<(a_k+1)D^{(k)}$を満たすか、のようなことを考えればアルゴリズムとして具体的に書け(ると思われ)ます。

そして次の命題を示します。

(1)完全性と一意性を満たせば単調性を満たす.
(2)単調性を満たせば一意性を満たす.

(1)補題2より,$D^{(K+1)}= S^{(K)}+1>S^{(K)}$だから補題1の(2)より単調性を満たす.$\blacksquare$
(2)$\displaystyle \sum_{k=0}^{N}a_kD^{(k)} =\sum_{k=0}^{N'}a'_kD^{(k)}$とすると,補題1の(2)より$N=N'$.よって$a_N\leq a'_N$とすると,
$\displaystyle (a'_N-a_N)D^{(N)}=\sum_{k=0}^{N-1}(a_k-a'_k)D^{(k)}$
$\displaystyle\leq \sum_{k=0}^{N-1}A_kD^{(k)}=S^{(N-1)}$
となるから単調性より$a'_N-a_N=0$すなわち$a'_N=a_N$であり,
$\displaystyle \sum_{k=0}^{N-1}a_kD^{(k)} =\sum_{k=0}^{N-1}a'_kD^{(k)}$
となる.同様の議論をすれば$k=1,\ldots N$$a_k=a_k'$となり一意性を満たすことが従う.$\blacksquare$

以上の命題から、$2^3=8$通りのうち次の可能性

完全性一意性単調性
$\circ$$\circ$$\times$
$\circ$$\times$$\circ$
$\times$$\times$$\circ$

が排除され、先に述べた例のような場合しか存在しないことが示されました。

正則な位取り記数法

ここでは特に完全性、一意性、単調性のすべてを満たす位取り記数法を正則な位取り記数法とし、次の形に限られることを示します。

正則な位取り記数法は,任意の整数$K\geq 1で$
\begin{equation} D^{(K)}=\prod_{k=0}^{K-1}(A_k+1) \end{equation}
を満たすものに限る.

補題2を用いて帰納法で示す.
$K=1$のとき,$D^{(1)}=A_0D^{(0)}+1=A_0+1.$
$\displaystyle D^{(K)}=\prod_{k=0}^{K-1}(A_k+1)$を仮定すると,
$\displaystyle D^{(K+1)}=\sum_{k=0}^{K}A_kD^{(k)}+1$
$=1+A_0+A_1(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=(A_0+1)+A_1(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=(A_1+1)(A_0+1)+\cdots + A_K(A_{K-1}+1)\cdots(A_0+1)$
$=\cdots =(A_K+1)(A_{K-1}+1)\cdots(A_0+1)$
$\displaystyle =\prod_{k=0}^{K-1}(A_k+1).\blacksquare$

逆にこの等式を満たすならば正則性が従うので、正則性と同値であることがわかります。

実際に10進法では$A_k+1=10$なのでこの等式を満たしています。上で言及した時間の表現の60進法もこれを満たしています。また、$A_k=k+1,D^{(k)}=(k+1)!$としてもこの等式を満たします。

まとめ

正則性という条件ではいわゆる$N$進法まで絞り込むことはできませんでした。追加の条件としては$A_k$が一定であることや、位を一つ上げる操作が特定の性質(線形性など)を持つことなどが考えられますが、ひとまずこれ以上の性質を定めるのはここではしないことにしました。

投稿日:2023217

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

仮称
1
180

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中