雙射記數

雙射記數系統（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.)