いわゆる Excel 進数

　ここで、次のような数え方を考えてみましょう。

　皆様にも馴染みの深い、Excel の列 です。

　しかし、例えば、a~z の $26$ 文字を、$0\sim 25$ に割り当てた場合、以下のようになっておかしくなります。

　a と aa が同じ数字になったり、z の次が ba になったりと、いろいろおかしいです。

　これは、a を $0$ とみなしているにも関わらず、数え方がそうなっていないために起こります。

　ならば、$0\sim26$ の $27$ 進数にすれば良いかというと、今度は別の問題が出てきます。便宜的に、「無」を _ と表現します。

　本来、_z の次は aa であるべきですが、a_ になってしまいます。これでは、正しい数え上げができません。

　このような特殊な数え方をする $N$ 進数について考えていきます。

基本の進数の数え上げ

　まずは簡単な例として、普通の $N$ 進数から。

　単純な $16$ 進数で考えると、$n$ と文字列は以下の通りシンプルに変換できます。

　また、「$D$ 桁以下の文字列が何個あるか」も非常に考えやすいです。$10$ 進数を考えます。これはほぼ自明に $10^D$ です（※ 0 もカウントすることに注意してください）。

　$D$ 桁以下の文字列の個数がわかるということは、ちょうど $D$ 桁の個数も当然わかります。「ちょうど $D$ 桁になる文字列」の個数は、$10^D-10^{(D-1)}=9 \cdot 10^{(D-1)}$ です。

　表にまとめるとこんな感じです。

$N$ 進数の数え上げ表（$10$ 進数の場合）

桁	範囲	個数	桁（累計）	範囲	個数
$D=0$	$[0,1)$	$1$	$D\leq0$	$[0,1)$	$1$
$D=1$	$[1,10)$	$9$	$D\leq1$	$[0,10)$	$10$
$D=2$	$[10,100)$	$90$	$D\leq2$	$[0,100)$	$100$
$D=3$	$[100,1000)$	$900$	$D\leq3$	$[0,1000)$	$1000$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$D=M$	$[10^{M-1},10^M)$	$9 \times 10^{M-1}$	$D\leq M$	$[0,10^M)$	$10^M$

※ $D=0$ のときは、$0$ 桁の文字列であり、つまり 0 がそれにあたります。

　では、Excel 進数などで使われる数え上げについて、同じようなパターンで検証しています。AA だとわかりづらいので、1~9 の $9$ 種類の数を使う文字列で、Excel の列のように増えていくものとします。

　結論から言うと、以下のように、1-indexed の $9$ 進数として考えるとうまく変換できます。

$19$ 番目の文字列は？
　- $19$ を $9$ で割るとあまり $1$、よって、$1$ 番目の文字である 1（$1$ 桁目）
　- $(\lceil \frac{19}{9} \rceil-1) = 2$
　- $2$ を $9$ で割るとあまり $2$、よって、$2$ 番目の文字である 2（$2$ 桁目）
21 はどんな数？
- こっちは普通に $N$ 進数として考えて大丈夫です
- $2\times9+1 = 19$

※ 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21 より（1-indexedの） $19$ 番目の文字列です

※ 文字列の変換について、プログラム上は、各桁ごとにデクリメントした上で 0-indexed と考える方が簡潔に実装できます（詳細は後述する実装例）

　こちらは、単純な $N$ 進数とは変わって、差分の法がわかりやすいです。ちょうど $D$ 桁に含まれる文字列は 1~9 を $D$ 個あてはめるだけなので、$9^D$ です。表にまとめます。

特殊 $N$ 進数の数え上げ表（$9$ 進数の場合）

桁	範囲	個数	桁（累計）	範囲	個数
$D=0$	$[1,1)$	$0$※	$D\leq0$	$[1,1)$	$0$
$D=1$	$[1,11)$	$9$	$D\leq1$	$[1,11)$	$9$
$D=2$	$[11,111)$	$81$	$D\leq2$	$[1,111)$	$90$
$D=3$	$[111,1111)$	$729$	$D\leq3$	$[1,1111)$	$819$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$D=M$	$[111\cdots,111\cdots)$	$9^M$	$D\leq M$	$[1,111\cdots)$	$\frac{9^{M+1}-1}{8}-1$

※ $D=0$ のときは例外処理が必要です。なんか数学的に気持ち悪いので、$[1,1)$ に $1$ 個の「無」の文字列が含まれると考えれば累計の $-1$ も消えてスッキリしますが、まあ、これは捉え方の問題で、やる計算は同じです。

　このような特殊な $N$ 進数に名前があるのかというと、当然あって、bijective numeration と呼ばれているらしいです。

　bijective とは「全単射」のことであり、つまり一対一対応のことです。

　どういうことかというと、まず、普通の $N$ 進数だと、1 も 01 も 001 も同じ数（$=1$）を示してしまいます。この点、bijective-N 進数だと、異なる文字列が同じ数を示すということがなく、一対一対応します。

　さて、この bijective-N ですが、日本語で定まった訳がないようです。一応、参考記事 3では bijective numeration に対して「全単射記数法」という訳を当てています。ほぼ直訳ですが、まあ誰が訳してもこうなりそうですし、妥当だと思います。

　という訳で、本記事では、この訳語を採用し定着させるとともに、他に「全単射 $N$ 進数」といった表記を提案したいと思います。

例）「Excel の列は、$26$ を基数とした全単射 $26$ 進数によって管理されている」