雙射記數

雙射記數系統（Bijective numeration）是一種表示數字的位數值系統，逐个非負整數攏會當使用有限數字串表示。該名稱「雙射」指甲是非負整數集佮用有限符號集的有限字符串集間存在雙射（即一一對應）。

大多數字系統，譬如講十進制嘛，攏毋是雙射的；因為不止一捾數字會當表示仝一个正整數：添加前導零袂改變表示的值，比如講「一」、「 一」、「 一」攏表示數字嘛「一」。 一進制因為干焦一个數字「一」所以必須愛「是」雙射的。

雙射進制-_ k _ 記數系統是一个雙射進位制。用集合 { 一 , 二 , . . . , _ k _ }（其中 _ k _ ≥ 一）編碼正整數；值的位置定義為「k」的冪倍數。Smullyan ( 一千九百六十一 ) 稱此為_ k _-adic：用有限非零數字串表示普通整數的系統，而且_ p _-adic數是包含整數做子集的一个數學值系統，並且可能需要無限數字序列表示。

定義

雙射進位制使用集合 { 一 , 二 , . . . , _ k _ }（其中 _ k _ ≥ 一）來唯一編碼逐个非負整數：

• 零由空字符串表示。
• 非空數字串表示的整數

: _ a _ n _ a _ n− 一 . . . _ a _ 一 _ a _ 零=_ a _ n _ k _ n + _ a _ n− 一 _ k _ n− 一 + . . . + _ a _ 一 _ k _ 一 + _ a _ 零 _ k _ 零 .

• 表示整數的數字串 _ m _ > 零是 _ a _ n _ a _ n− 一 . . . _ a _ 一 _ a _ 零

當

$ { \ begin { aligned } a _ { 零 } &=m-q _ { 零 } k , & q _ { 零 } &=f \ left ( { \ frac { m } { k } } \ right ) & \ \ a _ { 一 } &=q _ { 零 }-q _ { 一 } k , & q _ { 一 } &=f \ left ( { \ frac { q _ { 零 } } { k } } \ right ) & \ \ a _ { 二 } &=q _ { 一 }-q _ { 二 } k , & q _ { 二 } &=f \ left ( { \ frac { q _ { 一 } } { k } } \ right ) & \ \ & \ , \ , \ , \ vdots & & \ , \ , \ , \ vdots \ \ a _ { n } &=q _ { n 影一 } 板零 k , & q _ { n } &=f \ left ( { \ frac { q _ { n 影一 } } { k } } \ right )=零 \ end { aligned } } $

而且

$ f ( x )=\ lceil x \ rceil 影一 , $

$ \ lceil x \ rceil $ 是無小於的上細整數 _ x _（上取整函數）

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

: $ f ( x )=\ lfloor x \ rfloor , $

性質

對於 $ k \ geq 二 $ 進制：

• 表示非負整數 n 的雙射 k 進位數是 $ \ lfloor \ log _ { k } ( ( n + 一 ) ( k 影一 ) ) \ rfloor $，佮 $ \ lceil \ log _ { k } ( n + 一 ) \ rceil $ 相比並，k 進制若是講「一」，位數就是講 _ n _。
• 上細漢會當表示做長度 $ l \ geq 零 $ 的雙射 _ k _ 進制數字的非負整數是 $ min ( l )={ \ frac { k ^ { l } 影一 } { k 影一 } } $。
• 上大的表示為長度 $ l \ geq 零 $ 的雙射 _ k _ 進制數字的非負整數是 $ max ( l )={ \ frac { k ^ { l + 一 }-k } { k 影一 } } $，相當於是 $ max ( l )=k \ times min ( l ) $ 抑是 $ max ( l )=min ( l + 一 ) 影一 $。
• 非負整數 _ n _ 的雙射 _ k _ 進制佮普通進制 _ k _ 相仝，當普通的進制無含數字「零」，抑是等效地，雙射進制也毋是空字符合也毋包含數字 _ k _。

對進制 $ k \ geq 一 $，

• 會有 $ k ^ { l } $ 個雙射進制，長度為 $ l \ geq 零 $ 的 _ k _。
• 雙射進制 _ k _ 的列表 .。用 λ 表示空串，一、二、三、八、十、十二、十六為底的數如下（遮列出普通的表示方式以供較）：

例

• 雙射五進制的三更四千一百五十二=三 × 五十四 + 四 × 五十三 + 一 × 五十二 + 五 × 五十一 + 二 × 一=兩千四百二十七（十進制）
• 雙射十進制一百十九 A（A 代表數值十）=一 × 一百空三 + 一 × 一百空二 + 九 × 一百空一 + 十 × 一=千二百（十進制）
• 雙射十一進制 B=十一（十進制）
• 雙射三十五進制 Z=三十五（十進制）

參考

• Böhm , C . , On a family of Turing machines and the related programming language , ICC Bulletin , July 一千九百六十四 ,三: 一百九十一   .
• Forslund , Robert R . , A logical alternative to the existing positional number system , Southwest Journal of Pure and Applied Mathematics , 一千九百九十五 ,一: 二十七–二十九 , MR  一百三十八石六千三百七十六 , S 二 CID  一千九百空一孵空六百六十四   .
• Foster , J . E . , A number system without a zero symbol , Mathematics Magazine , 一千九百四十七 ,二十一( 一 ) : 三十九–四十一 , JSTOR  三百空二四九千四百七十九 , doi : 十 . 三百空二四九千四百七十九分之兩千三百空七   .
• Knuth , D . E . , The Art of Computer Programming , Vol . 二 : Seminumerical Algorithms 一 st , Addison-Wesley , Solution to Exercise 四孵一糊二十四 , p . 一百九十五 , 一千九百六十九   . ( Discusses bijective base 鋪十 . )
• Salomaa , A . , Formal Languages , Academic Press , Note 九陽一 , pp . 九十–九十一矣 , 一千九百七十三   . ( Discusses bijective base-_ k _ for all _ k _ ≥ 二 . )
• Smullyan , R . , 九 . Lexicographical ordering ; _ n _-adic representation of integers , Theory of Formal Systems , Annals of Mathematics Studies四十七, Princeton University Press : 三十四–三十六 , 一千九百六十一   .