双射记数

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

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

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

定义

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

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

a_na_n−1 ... a₁a₀ = a_n kⁿ + a_n−1 kⁿ⁻¹ + ... + a₁ k¹ + a₀ k⁰.

• 表示整数的数字串m>0是a_na_n−1 ... a₁a₀

当

${\displaystyle {\begin{aligned}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)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k}}\right)=0\end{aligned}}}$

且

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

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

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

${\displaystyle f(x)=\lfloor x\rfloor ,}$

扩展到整数

已隐藏部分未翻译内容，欢迎参与翻译。

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

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

meaning that

${\displaystyle 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 ${\displaystyle n}$ with bijective numeration digit representation ${\displaystyle d}$ is represented by ${\displaystyle {\overline {d_{k-1}}}d_{k}d}$. For base ${\displaystyle k>2}$, negative numbers ${\displaystyle n<-1}$ are represented by ${\displaystyle {\overline {d_{k-1}}}d_{i}d}$ with ${\displaystyle i<k-1}$, while for base ${\displaystyle k=2}$, negative numbers ${\displaystyle n<-1}$ are represented by ${\displaystyle {\overline {d_{k}}}d}$. This is similar to how in signed-digit representations, all integers ${\displaystyle n}$ with digit representations ${\displaystyle d}$ are represented as ${\displaystyle {\overline {d_{0}}}d}$ where ${\displaystyle 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 ${\displaystyle k}$-adic integers, of which the integers are only a subset.

性质

对于${\displaystyle k\geq 2}$进制：

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

对于进制${\displaystyle k\geq 1}$，

• 会有${\displaystyle k^{l}}$个双射进制，长度为${\displaystyle l\geq 0}$的k。^[2]
• 双射进制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×5⁴ + 4×5³ + 1×5² + 5×5¹ + 2×1 = 2427（十进制）
• 双射十进制119A（A代表数值10） = 1×10³ + 1×10² + 9×10¹ + 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 × 26² + 2 × 26¹ + 3 × 26⁰ = 731。

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

历史

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

注释

1. How many digits are in the bijective base-k numeral for n?. Stackexchange. [22 September 2018].
2. Forslund (1995).
3. Harvey, Greg, Excel 2013 For Dummies, John Wiley & Sons, 2013, ISBN 9781118550007.
4. Hellier, Coel, Appendix D: Variable star nomenclature, Cataclysmic Variable Stars - How and Why They Vary, Praxis Books in Astronomy and Space, Springer: 197, 2001, ISBN 9781852332112.

参考

• Böhm, C., On a family of Turing machines and the related programming language, ICC Bulletin, July 1964, 3: 191.
• Forslund, Robert R., A logical alternative to the existing positional number system, Southwest Journal of Pure and Applied Mathematics, 1995, 1: 27–29, MR 1386376, S2CID 19010664.
• Foster, J. E., A number system without a zero symbol, Mathematics Magazine, 1947, 21 (1): 39–41, JSTOR 3029479, doi:10.2307/3029479.
• Knuth, D. E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms 1st, Addison-Wesley, Solution to Exercise 4.1-24, p. 195, 1969. (Discusses bijective base-10.)
• Salomaa, A., Formal Languages, Academic Press, Note 9.1, pp. 90–91, 1973. (Discusses bijective base-k for all k ≥ 2.)
• Smullyan, R., 9. Lexicographical ordering; n-adic representation of integers, Theory of Formal Systems, Annals of Mathematics Studies 47, Princeton University Press: 34–36, 1961.