読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

位取り記数法

数学 代数学

最初にお知らせ。今回からは細かいところや、使うメリットがあまりないところまで TeX 記法を用いるのをやめます。

n 個の異なる要素の並び替え(順列)の全て n! 種類を辞書に載せたとき、ある特定の番号(自然数)のところにはどんな順列が来るか、あるいはある特定の順列は辞書の何番目に載っているか。こういうことを調べようとしていたのです。

そのときに有用なのが『階乗進法』という概念です。今回はその階乗進法への架け橋として、我々がよくなじんでいる『位取り記数法』について確認の意味もこめて記事にします。

例えば、2012 という数字列の意味しているところを考えます。あまりひねくれてもみっともないので、常識的に考えて『10進位取り記数法』であるということにしましょう。日本語の漢数字で書けば「二千十二」と表されるものです。数学的に位取りを確かにして書くと、2*10^3 + 0*10^2 + 1*10^1 + 2*10^0 と表されるところになるでしょう。

さて、2012という数字列には、0 という数字が使われていますが、これは『無』ではなく『空』を意味しています。もし、この数字列から 0 を取り去ったら、212 となりますが、これを10進位取り記数法と解釈すれば、その意味は「二百十二」であり、2*10^2 + 1*10^1 + 2*10^0 なので、数字列 212 と 2012 は自然数になおすと、違う値を持つこととなります。

ここからは数字列ではなく自然数として 2012 を扱います。2012 の日本語での漢字表現は先述の通り「二千十二」ですが、「百」という漢字が使われていませんし、「十」の直前は一二三四五六七八九のいずれの数字でもありません。しかし、〇という数字も導入して「二千十二」を「二千〇百一十二」と書けば、先程の指数を用いた表記及び位取り記数法とうまく対応しています。そして、俗に(日本語の、主に縦書きの文章で)用いられている通り、単に「二〇一二」と書いても意味は伝わります。これは使う数字の種類(文字のセット)が異なっているだけで、位取り記数法そのものです。

しかし、自然数としての 2012 を、任意の基数の位取り記数法としての数字列に直すにはどのようなアルゴリズムでもって行えばいいのでしょう。

10進法の場合を蛇足ながらも書くと、

10^3 < 2012 < 10^4 であることを踏まえて、

2012 = 2 * 10^3 + 12
  12 = 0 * 10^2 + 12
  12 = 1 * 10^1 + 2
   2 = 2 * 10^0

計算しているように見えませんが、これは割り算を行っているのです。

2012 / 10^3 = 2 余り 12
  12 / 10^2 = 0 余り 12
  12 / 10^1 = 1 余り 2
   2 / 10^0 = 2

イコールのすぐ右を縦に読めば「2012」と読めますよね。

一般的な形で書けば、

  1. 与えられた自然数 n に対して、10^N ≦ n < 10^(N+1) が成り立つ N を決定する
  2. i ← N
  3. i < 0 になるまで以下の処理を繰り返す
    1. n / (10^i) の商を q, 余りを r とする。
    2. q[i] ← q
    3. n ← r
    4. i ← i - 1
  4. 得られた q[N], q[N-1], q[N-2], …, q[2], q[1], q[0] が n の位取り記数法である(結果)

10進法以外の底を用いたいならば、上記のアルゴリズムの 10 の部分を変換したい底に置き換えてください。

ちなみに16進法での「二千十二」の表現は、16^2 < 2012 < 16^3 であることを踏まえて

 2012 =  7 * 16^2 + 220
  220 = 13 * 16^1 +  12
   12 = 12 * 16^0

より、2012 = 7*16^2 + 13*16^1 + 12*16^0 となります。我々は10種類しか数字をもっていないので16種類の数字の必要な16進法の表現は難に思えますが、その解決法として16進法ではアルファベット(A, B, C, D, E, F)を数字(10, 11, 12, 13, 14, 15)として使います。ですので、10進法での「2012」は、16進法では「7DC」と書くことになります。

位取り記数法への変換をご説明したところで、次はいよいよ階乗進法へとコマを進めます。