1

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

447
1

要約

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

導入

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

任意の非負整数nについて、非負整数kに対し整数0ak9が存在して,
n=k=0ak10k=a01+a110+a2102+
が成立する。 ただし、有限個のkを除いてak=0.

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

n=s1+m60+h602+d12602

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

本文

位取り記数法の定義

非負整数kに対し、Ak,D(k)を正の整数とし、整数列(D(k))k=0D(0)=1かつ狭義短調増加とします。
そして、正の整数N0akAkとなる整数akを用いて

k=0NakD(k)

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

性質

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

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

任意の非負整数nに対し,あるak(k=1,N)
n=k=0NakD(k).

(2)一意性

k=0NakD(k)=k=0NakD(k)
ならばN=Nかつak=ak(k=1,N).

(3)単調性

aN<aNならばk=0NakD(k)<k=0NakD(k).

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

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

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

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

(4)A0=1,A1=2,A2=2,Ak=21(k3)とし、D(0)=1,D(1)=4,D(2)=6,D(k)=22k2(k3)とする。このとき、

n位取り記数法短縮記法
111
2××
3××
40+1410
51+1411
60+04+16100
71+04+16101
80+2420
91+2421
100+14+16110
111+14+16111
120+04+26200
131+04+26201
140+24+16120
151+24+16121
160+14+26210
171+14+26211
18××
19××
200+24+26220
211+24+26221
220+04+06+1221000
231+04+06+1221001
24××
25××
260+14+06+1221010

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

(5)A0=2,A1=2,A2=2,Ak=21(k3)とし、D(0)=1,D(1)=4,D(2)=6,D(k)=22k2(k3)とする。
このとき、
3をこの位取り記数法で表記できず、
6=0+04+16=2+14であり、
0+04+16<0+24である。
従って完全性も一意性も単調性も満たさない。

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

例番号完全性一意性単調性
(1)×
(2)××
(3)
(4)××
(5)×××

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

性質の関係

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

(1)整数NM0
k=MNakD(k)0ならば,k=MNakD(k)D(M).
(2)単調性任意の非負整数K
D(K+1)>S(K):=k=0KAkD(k).

(1)k=MNakD(k)0よりk=MNak0だから,
k=MNakD(k)k=MNakD(M)D(M). 
(2)()D(K+1)の位の値を比較すれば定義より明らか.
()について,k=0NakD(k),k=0NakD(k)
aN<aNのとき,
k=0NakD(k)k=0NakD(k)
=(aNaN)D(N)+k=0N1(akak)D(k)
D(N)k=0N1AkD(k)>0だから,
k=0NakD(k)<k=0NakD(k). 

完全性と一意性を満たすとき,任意の非負整数Kに対し
D(K+1)=S(K)+1=k=0KAkD(k)+1

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

帰納法を用いて示す.
整数1nA01D(0),,A0D(0)と表記できるから一意性より
D(1)A0D(0)+1.
また,完全性より整数A0D(0)+1k=0NakD(k)と表記すると
A0D(0)+1=k=0NakD(k)
=a0D(0)+k=1NakD(k)となり,左辺は正だから補題1の(1)より
(A0a0)D(0)+1=k=1NakD(k)D(1).
よって
A0D(0)+1D(1)(A0a0)D(0)+1.
左辺と右辺を比較するとa0=0となるから,
D(1)=A0D(0)+1.
すなわちK=0での成立を示せた.
このとき,整数1nS(1)はそれぞれ,
1D(0),,A0D(0),1D(1),
1D(0)+1D(1),,A0D(0)+1D(1),2D(1),
1D(0)+2D(1),,A0D(0)+A1D(1)
と表記できる.同様に整数0K<K
D(K+1)=S(K)+1
が成立すると仮定すると,整数1nS(K)はそれぞれ
1D(0),,k=0KakD(k),,k=0KAkD(k)
と表記できる.よって一意性から
D(K+1)S(K)+1
が従い,完全性からS(K)+1=k=0NakD(k)
と表記すると,補題1の(1)より
k=0NakD(k)=a0D(0)++aKD(K)+k=K+1NakD(k)
だから
k=0K(Akak)D(k)+1=k=K+1NakD(k)D(K+1)
となる.従って,
S(K)+1D(K+1)k=0K(Akak)D(k)+1
が従い,a0==aK=0であり,
D(K+1)=S(K)+1
となり,Kでの成立が確かめられ,帰納法によって補題が示された.

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

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

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

(1)補題2より,D(K+1)=S(K)+1>S(K)だから補題1の(2)より単調性を満たす.
(2)k=0NakD(k)=k=0NakD(k)とすると,補題1の(2)よりN=N.よってaNaNとすると,
(aNaN)D(N)=k=0N1(akak)D(k)
k=0N1AkD(k)=S(N1)
となるから単調性よりaNaN=0すなわちaN=aNであり,
k=0N1akD(k)=k=0N1akD(k)
となる.同様の議論をすればk=1,Nak=akとなり一意性を満たすことが従う.

以上の命題から、23=8通りのうち次の可能性

完全性一意性単調性
×
×
××

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

正則な位取り記数法

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

正則な位取り記数法は,任意の整数K1
D(K)=k=0K1(Ak+1)
を満たすものに限る.

補題2を用いて帰納法で示す.
K=1のとき,D(1)=A0D(0)+1=A0+1.
D(K)=k=0K1(Ak+1)を仮定すると,
D(K+1)=k=0KAkD(k)+1
=1+A0+A1(A0+1)++AK(AK1+1)(A0+1)
=(A0+1)+A1(A0+1)++AK(AK1+1)(A0+1)
=(A1+1)(A0+1)++AK(AK1+1)(A0+1)
==(AK+1)(AK1+1)(A0+1)
=k=0K1(Ak+1).

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

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

まとめ

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

投稿日:2023217
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

仮称
1
447

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 要約
  2. 導入
  3. 本文
  4. 位取り記数法の定義
  5. 性質
  6. 性質の関係
  7. 正則な位取り記数法
  8. まとめ