双射记数
![]() | 此条目需要精通或熟悉数学的编者参与及协助编辑。 (2023年1月5日) |
数制 |
记数系统 |
---|
数制列表 |
双射记数系统(Bijective numeration)是一种表示数字的位置数值系统,每个非负整数都可使用有限数字串表示。该名称“双射”指的是非负整数集和用有限符号集的有限字符串集间存在双射(即一一对应)。
大多数数字系统,例如十进制,都不是双射的;因为不止一串数字可以表示同一个正整数:添加前导零不会改变表示的值,例如“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。
对于进制,
双射一进制 | λ | 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 进制,可能由于人们普遍不熟悉这一系统,导致考古文献中并未发现这一点。
注释
- ^ 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.
|