雙射記數

雙射記數系統（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 n a n -1 ... a 1 a 0

=

a n k n + a n -1 k n -1 + ... + a 1 k 1 + a 0 k 0

.

表示整數的數字串m>0是 $a n a n -1 ... a 1 a 0$

當

{\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}}

且

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$ ^[1]，與 $\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。^[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 進制，可能由於人們普遍不熟悉這一系統，導致考古文獻中並未發現這一點。

註釋

^ How many digits are in the bijective base-k numeral for n?. Stackexchange. [22 September 2018].
^ Forslund (1995).
^ Harvey, Greg, Excel 2013 For Dummies, John Wiley & Sons, 2013, ISBN 9781118550007 .
^ 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 .

[1] How many digits are in the bijective base-k numeral for n?. Stackexchange. [22 September 2018].

[FOOTNOTEForslund1995-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 .

[1]

[2]

[3]

[4]

閱論編進制的記數系統
基本進位制	一進制二進制三進制四進制五進制六進制七進制八進制九進制十進制十一進制十二進制十三進制十四進制十五進制十六進制十七進制十八進制十九進制二十進制二十六進制三十六進制六十進制六十四進制一百進制
平衡進位制	平衡三進制
廣義的進制系統	Base64 十進位制二進指數法非整數進位制根號2進制黃金進制 e進制負底數進制（英語：Negative base）複底數進制 2i進制 -1±i進制混合底數（英語：Mixed radix）階乘進制斐波那契編碼雙射記數系統
相關條目	底數數位位元位元組進位制米迪定理記數系統