双射记数

双射记数系统（Bijective numeration）是一种表示数字的位置数值系统，每个非负整数都可使用有限数字串表示。该名称“双射”指的是非负整数集和用有限符号集的有限字符串集间存在双射（即一一对应）。

大多数数字系统，例如十进制，都不是双射的；因为不止一串数字可以表示同一个正整数：添加前导零不会改变表示的值，例如“1”、“01”、“001”都表示数字“1”。而一进制因为只有一个数字“1”所以必然“是”双射的。

双射进制-k记数系统是一个双射进位制。使用集合{1, 2, ..., k}（其中k≥1）编码正整数；值的位置定义为“k”的幂倍数。称此为k-adic：用有限非零数字串表示普通整数的系统，而p-adic数是包含整数作为子集的一个数学值系统，并且可能需要无限数字序列表示。

## 定义

双射进位制使用集合{1, 2, ..., k}（其中k≥ 1）来唯一编码每个非负整数：

- 零由空字符串表示。
- 由非空数字串表示的整数

anan−1 ... a1a0 = .

- 表示整数的数字串m>0是anan−1 ... a1a0

当

$$\begin{align} a_0 & = m - q_0 k , & q_0 & = f\left(\frac m k \right) & \\ a_1 & = q_0 - q_1 k , & q_1 & = f\left(\frac {q_0} k \right) & \\ a_2 & = q_1 - q_2 k , & q_2 & = f\left(\frac {q_1} k \right) & \\ <pre> & \,\,\,\vdots & & \,\,\,\vdots \\ </pre> a_n & = q_{n-1} - 0 k , & q_n & = f\left(\frac {q_{n-1}} k \right) = 0 \end{align}$$

且

$$f(x) = \lceil x \rceil - 1,$$

$\lceil x \rceil$是不小于的最小整数x（上取整函数）

相反，标准进位制可用类似递归算法定义当

$$f(x) = \lfloor x \rfloor,$$

### 扩展到整数

在$k > 1$进制, the bijective base-$k$ numeration system could be extended to negative integers in the same way as the standard base-$b$ numeral system by use of an infinite number of the digit $d_{k - 1}$, where $f(d_{k - 1}) = k - 1$, represented as a left-infinite sequence of digits $\ldots d_{k - 1}d_{k - 1}d_{k - 1} = \overline{d_{k - 1}}$. This is because the Euler summation

$$g(\overline{d_{k - 1}}) = \sum_{i = 0}^\infty f(d_{k - 1}) k^i = -\frac{k - 1}{k - 1} = -1$$

meaning that

$$g(\overline{d_{k - 1}}d_{k}) = f(d_{k}) \sum_{i = 1}^\infty f(d_{k - 1}) k^i = 1 + \sum_{i = 0}^\infty f(d_{k - 1}) k^i = 0$$

and for every positive number $n$ with bijective numeration digit representation $d$ is represented by $\overline{d_{k - 1}}d_{k}d$. For base $k > 2$, negative numbers $n < -1$ are represented by $\overline{d_{k - 1}}d_{i}d$ with $i < k - 1$, while for base $k = 2$, negative numbers $n < -1$ are represented by $\overline{d_{k}}d$. This is similar to how in signed-digit representations, all integers $n$ with digit representations $d$ are represented as $\overline{d_0}d$ where $f(d_0) = 0$. This representation is no longer bijective, as the entire set of left-infinite sequences of digits is used to represent the $k$-adic integers, of which the integers are only a subset.

## 性质

对于$k \geq 2$进制：

- 表示非负整数n的双射k进位位数是$\lfloor \log_k ((n+1)(k - 1))\rfloor$，与$\lceil \log_k(n+1)\rceil$相比，k进制如果是“1”，位数就是n。
- 最小可表示为长度$l \geq 0$的双射k进制数字的非负整数是$min(l)=\frac{k^l-1}{k-1}$。
- 最大可表示为长度$l \geq 0$的双射k进制数字的非负整数是$max(l)=\frac{k^{l+1}-k}{k-1}$，相当于$max(l)=k \times min(l)$或$max(l)=min(l+1)-1$。
- 非负整数n的双射k进制可和普通进制k相同，当且仅当普通进制不含数字“0”，或者等效地，双射进制既不是空字符串也不包含数字k。

对于进制$k \geq 1$。

- 会有$k^l$个双射进制，长度为$l \geq 0$的k。
- 双射进制k的列表.。用λ表示空串，1、2、3、8、10、12、16为底的数如下（这里列出普通的表示方式以供比较）：

双射一进制｜ λ ｜ 1 ｜ 11 ｜ 111 ｜ 1111 ｜ 11111 ｜ 111111 ｜ 1111111 ｜ 11111111 ｜ 111111111 ｜ 1111111111 ｜ 11111111111 ｜ 111111111111 ｜ 1111111111111 ｜ 11111111111111 ｜ 111111111111111 ｜ 1111111111111111 ｜ ...

双射二进制｜ λ ｜ 1 ｜ 2 ｜ 11 ｜ 12 ｜ 21 ｜ 22 ｜ 111 ｜ 112 ｜ 121 ｜ 122 ｜ 211 ｜ 212 ｜ 221 ｜ 222 ｜ 1111 ｜ 1112 ｜ ...

二进制｜ 0 ｜ 1 ｜ 10 ｜ 11 ｜ 100 ｜ 101 ｜ 110 ｜ 111 ｜ 1000 ｜ 1001 ｜ 1010 ｜ 1011 ｜ 1100 ｜ 1101 ｜ 1110 ｜ 1111 ｜ 10000 ｜ ...

双射三进制｜ λ ｜ 1 ｜ 2 ｜ 3 ｜ 11 ｜ 12 ｜ 13 ｜ 21 ｜ 22 ｜ 23 ｜ 31 ｜ 32 ｜ 33 ｜ 111 ｜ 112 ｜ 113 ｜ 121 ｜ ...

三进制｜ 0 ｜ 1 ｜ 2 ｜ 10 ｜ 11 ｜ 12 ｜ 20 ｜ 21 ｜ 22 ｜ 100 ｜ 101 ｜ 102 ｜ 110 ｜ 111 ｜ 112 ｜ 120 ｜ 121 ｜ ...

双射八进制｜ λ ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ 15 ｜ 16 ｜ 17 ｜ 18 ｜ ...

八进制｜ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 10 ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ 15 ｜ 16 ｜ 17 ｜ 20 ｜ ...

双射十进制｜ λ ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ A ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ 15 ｜ 16 ｜ ...

十进制｜ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ 10 ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ 15 ｜ 16 ｜ ...

双射十二进制｜ λ ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ A ｜ B ｜ C ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ ...

十二进制｜ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ A ｜ B ｜ 10 ｜ 11 ｜ 12 ｜ 13 ｜ 14 ｜ ...

双射十六进制｜ λ ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ A ｜ B ｜ C ｜ D ｜ E ｜ F ｜ G ｜ ...

十六进制｜ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ A ｜ B ｜ C ｜ D ｜ E ｜ F ｜ 10 ｜ ...

## 例

- 双射五进制的34152 = 3×54 + 4×53 + 1×52 + 5×51 + 2×1 = 2427（十进制）
- 双射十进制119A（A代表数值10） = 1×103 + 1×102 + 9×101 + 10×1 = 1200（十进制）
- 双射11进制B = 11（十进制）
- 双射35进制Z = 35（十进制）

## 双射十进制

双射十进制系统是一种以 10 为底的位置数字系统，不使用数字来表示零，而用一个数字代表十，例如 A。

与传统的十进制一样，每个数字位置代表十的幂，因此例如 123 是“一百，加上两个十，加上三个一”。所有在传统十进制中仅用非零数字表示的正整数（例如 123）在不带零的十进制中具有相同的表示形式。使用零的必须重写，例如10变为A，常规20变为1A，常规100变为9A，常规101变为A1，常规302变为2A2，常规1000变为99A，常规1110变为AAA，常规2010变为19AA，等等。

不带零的十进制的加法和乘法本质上与传统十进制相同，只是当位置超过十时而不是超过九时发生进位。因此，要计算 643 + 759，有十二个个位（在右边写 2，十位进位 1）、十个十（记为 A，不需要进位到百位）、十三个百（在右边写 3，进位 1）、和一个千（写 1），得到结果 13A2 而不是传统的 1402。

## 双射二十六进制

在双射二十六进制系统中，可以使用拉丁字母A到Z来表示1到26。（A=1，B=2，C=3，...，Z=26）

通过选择这种表示法，数字序列（从 1 开始）开始为 A、B、C、...、X、Y、Z、AA、AB、AC、...、AX、AY、AZ、BA、BB、BC，...

每个数字位置代表二十六的幂，例如数字 ABC 代表十进制的 1 × 262 + 2 × 261 + 3 × 260 = 731。

许多电子表格（包括 Microsoft Excel）使用此系统为电子表格的列分配标签，如 A、B、C、...、Z、AA、AB、...、AZ、BA、...、ZZ、AAA。在 Excel 2013 中，最多可以有 16384（214）列，从 A 到 XFD。该系统的一个变体用于命名变星。它可以应用于任何需要使用字母进行系统命名的问题，同时使字符串尽可能短。

所有英语单词（不区分大小写）都可以通过上述方法转换成十进制自然数。

## 历史

每个非负整数在双射 k (k ≥ 1) 进制中都有唯一的表示，这一事实是一个已被多次重新发现的“民间定理”。早期的例子是 （对于 k = 10），以及 和 （对于所有 k ≥ 1）。Smullyan 使用该系统提供逻辑系统中符号串的哥德尔编号； Böhm 使用这些表示以编程语言 P′′ 执行计算。提到了 k = 10 的特殊情况，讨论了 k ≥ 2 的情况。似乎是另一个重新发现，并提出假设说如果古代计数系统使用双射 k 进制，可能由于人们普遍不熟悉这一系统，导致考古文献中并未发现这一点。

## 参考

- . (Discusses bijective base-10.)
- . (Discusses bijective base-k for all k ≥ 2.)