跳转到内容

雙射記數

维基百科,自由的百科全书

雙射記數系統(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)來唯一編碼每個非負整數:

  • 零由空字符串表示。
  • 由非空數字串表示的整數
anan−1 ... a1a0 = an kn + an−1 kn−1 + ... + a1 k1 + a0 k0.
  • 表示整數的數字串m>0是anan−1 ... a1a0
是不小於的最小整數x上取整函数

相反,標準進位制可用類似遞歸算法定義當

擴展到整數

[编辑]
已隱藏部分未翻譯内容,歡迎參與翻譯

進制, the bijective base- numeration system could be extended to negative integers in the same way as the standard base- numeral system by use of an infinite number of the digit , where , represented as a left-infinite sequence of digits . This is because the Euler summation

meaning that

and for every positive number with bijective numeration digit representation is represented by . For base , negative numbers are represented by with , while for base , negative numbers are represented by . This is similar to how in signed-digit representations, all integers with digit representations are represented as where . This representation is no longer bijective, as the entire set of left-infinite sequences of digits is used to represent the -adic integers, of which the integers are only a subset.

性質

[编辑]

對於進制:

  • 表示非負整數n的雙射k進位位數是[1],與相比,k進制如果是「1」,位數就是n
  • 最小可表示為長度的雙射k進制數字的非負整數是
  • 最大可表示為長度的雙射k進制數字的非負整數是,相當於
  • 非負整數n的雙射k進制可和普通進制k相同,當且僅當普通進制不含數字「0」,或者等效地,雙射進制既不是空字符串也不包含數字k

對於進制

  • 會有個雙射進制,長度為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×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。[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 .

參考

[编辑]