雙射記數

雙射記數系統（Bijective numeration）是一種表示數字的位置數值系統，每個非負整數都可使用有限數字串表示。該名稱「雙射」指的是非負整數集和用有限符號集的有限字符串集間存在雙射（即一一對應）。

记数系统
印度-阿拉伯数字系统
西方阿拉伯数字 阿拉伯文数字 高棉數字 孟加拉数字	印度數字 波羅米數字 泰语数字
漢字文化圈記數系統
中文数字 閩南語數字 越南语数字 算筹	日語數字 朝鲜语數字 苏州码子
字母記數系統
阿拉伯字母數字 亚美尼亚数字 西里爾數字 吉茲數字	希伯來數字 希腊数字 阿利耶波多數字
其它記數系統
阿提卡數字 巴比倫數字 古埃及数字 伊特拉斯坎數字	玛雅数字 罗马数字 熙笃会数字 卡克托维克数字
依底数区分的进位制系统
1 2 3 4 5 6 8 9 10 11 12 15 16 18 20 24 30 32 36 60 64
查 论 编

大多數數字系統，例如十進制，都不是雙射的；因為不止一串數字可以表示同一個正整數：添加前導零（英语：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 .