取整函數
這是此頁批准，以及是最近的修訂。
佇咧數學佮電腦科學中，取整函數是一類將實數對映到相倚的整數的函數。
捷用的取整函數有兩个，分別是下取整函數（英語：floor function）和上取整函數（ceiling function）。
下取整函數即為取底符號，佇數學中一般的記作 $ [x] $ 抑是講 $ \ lfloor x \ rfloor $ 抑是講 $ E ( x ) $，佇電腦科學中一般記作 floor ( _ x _ )，表示無超過 _ x _ 的整數內底上大的一个。
- $ [x]=\ max \ , \ { n \ in \ mathbb { Z } \ mid n \ leq x \ } . $
比如講伊，$ [三孵六三三]=三 $，$ [五十六]=五十六 $，$ [鋪二]=鋪二 $，$ [抹二鋪二六三]=ma三 $。對非負的實數，其下取整函數的值一般號做伊的整數部份抑是取整部份。而且 $ x-[x] $ 叫做 _ x _ 的小數部份。每一个分數攏會當表示成其整數的部份佮一个真分數的佮，實數的整數部份佮小數部份是佮此概念相應的楦延。
下取整函數的符號用方括號表示（$ [x] $）， 這號做高斯符號，首擺出現是佇卡爾 ・ 被里德里希望 ・ 高斯的數學著作《算術研究》。
上取整函數即為取頂符號佇數學中一般的記作 $ \ lceil x \ rceil $，佇電腦科學中一般記作 ceil ( _ x _ )，表示無細膩 _ x _ 的整數內底上細的一个。
- $ \ lceil x \ rceil=\ min \ { n \ in \ mathbb { Z } \ mid x \ leq n \ } . $
比如講伊，$ \ lceil 三孵六三三 \ rceil=四 $，$ \ lceil 五十六 \ rceil=五十六 $，$ \ lceil 鋪二 \ rceil=鋪二 $，$ \ lceil 抹二鋪二六三 \ rceil=鋪二 $。
電腦內面的上取整函數和下取整函數的號名來自英文的 _ ceiling _（天篷）和 _ floor _（塗跤）， 一九六二年由肯尼斯 ・ 艾佛森於《A Programming Language》引入來。
性質
對高斯符號，有如下性質。
- 照定義：
- $ [x] \ leq x < [x] + 一 $ 若是唯一 _ x _ 為整數時號等號。
- 設 x 和 n 為正實數，著：
- $ \ left [{ \ frac { n } { x } } \ right] \ geq { \ frac { n } { x } }-{ \ frac { x 影一 } { x } } $
- 當 _ n _ 為當整數的時陣，有：
- $ \ left \ lbrack { \ frac { x } { n } } \ right \ rbrack={ \ frac { x-x { \ bmod { n } } } { n } } , $ 其中 $ x { \ bmod { n } } $ 表示 $ x $ 除以 $ n $ 的餘數。
- 對任意的整數 _ k _ 佮任意實數 _ x _，
- $ [{ k + x }]=k + [x] . $
- 一般的數值修約規則會當表示對將 _ x _ 嘿映到 floor ( _ x _ + 空七五 )；
- 高斯符號毋是連紲函數，但是頂半連紲的。成做一个分段的常數函數，佇其導數有定義的所在，高斯符號導數為零。
- 設 _ x _ 為一个實數，_ n _ 為整數，則由定義，_ n _ ≤ _ x _ 若是唯一 _ n _ ≤ floor ( _ x _ )。
- 當 _ x _ 是正數的時陣，有：
- $ \ left \ lbrack 二 x \ right \ rbrack 鋪二 \ left \ lbrack x \ right \ rbrack \ leqslant 一 $
- 用高斯符號會當寫出若干個質數公式，但是無啥物實際的價值，見 § 質數公式。
- 對非整數的 _ x _，高斯符號有如下的傅立葉級數展開：
- $ [x]=x-{ \ frac { 一 } { 二 } } + { \ frac { 一 } { \ pi } } \ sum _ { k=一 } ^ { \ infty } { \ frac { \ sin ( 二 \ pi kx ) } { k } } . $
- 根據 Beatty 定理，每一个正無理數攏會當通過高斯符號製造出一个整數集的分劃。
- 最後咧，著每一个正整數 _ k _，其在 p 進位下的表示有 $ [\ log _ { p } ( k )] + 一 $ 個數位。
函數間之關係
由頂下取整函數的定義，可見
- $ \ lfloor x \ rfloor \ leq \ lceil x \ rceil , $
等號若而且唯若 $ x $ 為整數，即
- $ \ lceil x \ rceil-\ lfloor x \ rfloor={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $
實際上，頂取整佮下取整函數作用佇整數 $ n $，效果等同恆等函數：
- $ \ lfloor n \ rfloor=\ lceil n \ rceil=n . $
自變數加負號，等於是共頂取整佮下取整相換，外口閣加負號，即：
- $ { \ begin { aligned } \ lfloor x \ rfloor + \ lceil-x \ rceil &=零 , \ \-\ lfloor x \ rfloor &=\ lceil-x \ rceil , \ \-\ lceil x \ rceil &=\ lfloor-x \ rfloor . \ end { aligned } } $
而且：
- $ \ lfloor x \ rfloor + \ lfloor-x \ rfloor={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 影一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } , \ end { cases } } $
- $ \ lceil x \ rceil + \ lceil-x \ rceil={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $
若小數部份 $ \ { x \ }=x-\ lfloor x \ rfloor $，自變數取顛倒反數會使小數部份變做是關於一的「補數」：
- $ \ { x \ } + \ {-x \ }={ \ begin { cases } 零 , & { \ text { 若是 } } \ x \ in \ mathbb { Z } , \ \ 一 , & { \ text { 若是 } } \ x \ not \ in \ mathbb { Z } . \ end { cases } } $
上取整、硩規下、小數部份攏為冪等等函數，即函數疊代兩改的結果等於家己：
- $ { \ begin { aligned } { \ Big \ lfloor } \ lfloor x \ rfloor { \ Big \ rfloor } &=\ lfloor x \ rfloor , \ \ { \ Big \ lceil } \ lceil x \ rceil { \ Big \ rceil } &=\ lceil x \ rceil , \ \ { \ Big \ { } \ { x \ } { \ Big \ } } &=\ { x \ } . \ end { aligned } } $
若濟上取整和下取整依照相疊代的效果，不止仔成上內層一个：
- $ { \ begin { aligned } { \ Big \ lfloor } \ lceil x \ rceil { \ Big \ rfloor } &=\ lceil x \ rceil , \ \ { \ Big \ lceil } \ lfloor x \ rfloor { \ Big \ rceil } &=\ lfloor x \ rfloor , \ end { aligned } } $
因為外層取整函數實際消息作用佇整數頂頭，無帶來變化。
商
若是 $ m $ 和 $ n $ 為正整數，而且 $ n \ neq 零 $，著
- $ 零 \ leq \ left \ { { \ frac { m } { n } } \ right \ } \ leq 一-{ \ frac { 一 } { | n | } } . $
若是 $ n $ 為正整數，著
- $ \ left \ lfloor { \ frac { x + m } { n } } \ right \ rfloor=\ left \ lfloor { \ frac { \ lfloor x \ rfloor + m } { n } } \ right \ rfloor , $
- $ \ left \ lceil { \ frac { x + m } { n } } \ right \ rceil=\ left \ lceil { \ frac { \ lceil x \ rceil + m } { n } } \ right \ rceil . $
若是 $ m $ 為正數，著
- $ n=\ left \ lceil { \ frac { n } { m } } \ right \ rceil + \ left \ lceil { \ frac { n 影一 } { m } } \ right \ rceil + \ dots + \ left \ lceil { \ frac { n-m + 一 } { m } } \ right \ rceil , $
- $ n=\ left \ lfloor { \ frac { n } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { n + 一 } { m } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { n + m 影一 } { m } } \ right \ rfloor . $
代 $ m=二 $，上式推出：
- $ n=\ left \ lfloor { \ frac { n } { 二 } } \ right \ rfloor + \ left \ lceil { \ frac { n } { 二 } } \ right \ rceil . $
閣較一般，著正整數 $ m $，有埃爾米特恆等式：
- $ \ lceil mx \ rceil=\ left \ lceil x \ right \ rceil + \ left \ lceil x-{ \ frac { 一 } { m } } \ right \ rceil + \ dots + \ left \ lceil x-{ \ frac { m 影一 } { m } } \ right \ rceil , $
- $ \ lfloor mx \ rfloor=\ left \ lfloor x \ right \ rfloor + \ left \ lfloor x + { \ frac { 一 } { m } } \ right \ rfloor + \ dots + \ left \ lfloor x + { \ frac { m 影一 } { m } } \ right \ rfloor . $
著正整數 $ m $，以下兩式會當將頂下取整函數互相轉化：
- $ \ left \ lceil { \ frac { n } { m } } \ right \ rceil=\ left \ lfloor { \ frac { n + m 影一 } { m } } \ right \ rfloor=\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor + 一 , $
- $ \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor=\ left \ lceil { \ frac { n-m + 一 } { m } } \ right \ rceil=\ left \ lceil { \ frac { n + 一 } { m } } \ right \ rceil 影一 . $
著任意正整數 $ m $ 和 $ n $，有：
- $ \ sum _ { k=一 } ^ { n 影一 } \ left \ lfloor { \ frac { km } { n } } \ right \ rfloor={ \ frac { ( m 影一 ) ( n 影一 ) + \ gcd ( m , n ) 影一 } { 二 } } , $
做特別，當 $ m $ 和 $ n $ 互質的時陣，上式簡化為
- $ \ sum _ { k=一 } ^ { n 影一 } \ left \ lfloor { \ frac { km } { n } } \ right \ rfloor={ \ frac { 一 } { 二 } } ( m 影一 ) ( n 影一 ) . $
這个等式會當做幾方式證明。閣因為正式有關於 $ m $、$ n $ 對稱，可得
- $ \ left \ lfloor { \ frac { m } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 m } { n } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( n 影一 ) m } { n } } \ right \ rfloor=\ left \ lfloor { \ frac { n } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 n } { m } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( m 影一 ) n } { m } } \ right \ rfloor . $
閣較一般，著正整數 $ m , n $，有
- $ { \ begin { aligned } & \ left \ lfloor { \ frac { x } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { m + x } { n } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 m + x } { n } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { ( n 影一 ) m + x } { n } } \ right \ rfloor \ \=& \ left \ lfloor { \ frac { x } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { n + x } { m } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 n + x } { m } } \ right \ rfloor + \ cdots + \ left \ lfloor { \ frac { ( m 影一 ) n + x } { m } } \ right \ rfloor . \ end { aligned } } $
上式算是一个「互反律」（reciprocity law）， 佮 § 二次互反律有關。
應用
二次互反律
高斯予出兩改互反律的第三个證明，經過艾森斯坦修改了後，有以下兩个主要步數。
設 $ p $、$ q $ 替互異奇質數，閣設
- $ m={ \ frac { p 影一 } { 二 } } , $ $ n={ \ frac { q 影一 } { 二 } } . $
首先，利用高斯引理，證明勒壤得符號會當表示做和式：
- $ \ left ( { \ frac { q } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { q } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 q } { p } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { mq } { p } } \ right \ rfloor } , $
仝款
- $ \ left ( { \ frac { p } { q } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p } { q } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 p } { q } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { np } { q } } \ right \ rfloor } . $
其後，採用幾何論證，證明
- $ \ left \ lfloor { \ frac { q } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 q } { p } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { mq } { p } } \ right \ rfloor + \ left \ lfloor { \ frac { p } { q } } \ right \ rfloor + \ left \ lfloor { \ frac { 二 p } { q } } \ right \ rfloor + \ dots + \ left \ lfloor { \ frac { np } { q } } \ right \ rfloor=mn . $
總結上術兩步，得
- $ \ left ( { \ frac { p } { q } } \ right ) \ left ( { \ frac { q } { p } } \ right )=( 影一 ) ^ { mn }=( 影一 ) ^ { { \ frac { p 影一 } { 二 } } { \ frac { q 影一 } { 二 } } } . $
這馬二改互反律。一寡仔細整數模奇質數 $ p $ 的兩改特徵標，會當高斯符號表示，如：
- $ \ left ( { \ frac { 二 } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p + 一 } { 四 } } \ right \ rfloor } , $
- $ \ left ( { \ frac { 三 } { p } } \ right )=( 影一 ) ^ { \ left \ lfloor { \ frac { p + 一 } { 六 } } \ right \ rfloor } . $
質數公式
下整函數出現佇若干焦刻畫質數的公式內底。舉例，因為乎 $ \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor-\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor $ 佇咧 $ m $ 整除 $ n $ 時等於 $ 一 $，抑無來做 $ 零 $，所以正整數 $ n $ 為質數若是唯若
- $ \ sum _ { m=一 } ^ { \ infty } \ left ( \ left \ lfloor { \ frac { n } { m } } \ right \ rfloor-\ left \ lfloor { \ frac { n 影一 } { m } } \ right \ rfloor \ right )=二 . $
除表示質數條件以外，閣會當寫出公式使其取值做質數。比如講，記第 $ n $ 個質數為 $ p _ { n } $，任選一个整數 $ r > 一 $，然後定義實數 $ \ alpha $ 為
- $ \ alpha=\ sum _ { m=一 } ^ { \ infty } p _ { m } r ^ {-m ^ { 二 } } . $
是使用取整、冪、四則運算會當寫出質數公式：
- $ p _ { n }=\ left \ lfloor r ^ { n ^ { 二 } } \ alpha \ right \ rfloor-r ^ { 二 n 影一 } \ left \ lfloor r ^ { ( n 影一 ) ^ { 二 } } \ alpha \ right \ rfloor . $
類似閣有米爾斯常數 $ \ theta=一孵三空六四 \ ldots $，使
- $ \ left \ lfloor \ theta ^ { 三 } \ right \ rfloor , \ left \ lfloor \ theta ^ { 九 } \ right \ rfloor , \ left \ lfloor \ theta ^ { 二十七 } \ right \ rfloor , \ dots $
攏為質數。
若無三擺的函數，改做疊代以 $ 二 $ 為著的指數函數，亦有 $ \ omega=一孵九二八七八空空 \ ldots $ 使
- $ \ left \ lfloor 二 ^ { \ omega } \ right \ rfloor , \ left \ lfloor 二 ^ { 二 ^ { \ omega } } \ right \ rfloor , \ left \ lfloor 二 ^ { 二 ^ { 二 ^ { \ omega } } } \ right \ rfloor , \ dots $
攏為質數。
以質數計算函數 $ \ pi ( x ) $ 表示細於抑是等於 $ x $ 的質數個數。由威爾遴定理，可知
- $ \ pi ( n )=\ sum _ { j=二 } ^ { n } \ left \ lfloor { \ frac { ( j 影一 ) ! + 一 } { j } }-\ left \ lfloor { \ frac { ( j 影一 ) ! } { j } } \ right \ rfloor \ right \ rfloor . $
閣抑是講，當 $ n \ geq 二 $ 時：
- $ \ pi ( n )=\ sum _ { j=二 } ^ { n } \ left \ lfloor { \ frac { 一 } { \ sum _ { k=二 } ^ { j } \ left \ lfloor \ left \ lfloor { \ frac { j } { k } } \ right \ rfloor { \ frac { k } { j } } \ right \ rfloor } } \ right \ rfloor . $
本小節的公式無任何實際的用途。
其他的等式
- 對所有的實數 _ x _，有：
- $ \ left \ lbrack { \ frac { x } { 二 } } \ right \ rbrack={ \ frac { 一 } { 四 } } ( ( 影一 ) ^ { [x] } 影一 + 二 [x] ) $
- $ \ left \ lbrack { \ frac { x } { 三 } } \ right \ rbrack={ \ frac { 鋪二 } { \ sqrt { 三 } } } \ sin ( { \ frac { 二 \ pi } { 三 } } [x] + { \ frac { \ pi } { 三 } } ) + 一 $
- 設 _ x _ 為一个實數，_ n _ 為整數，著
- $ \ sum _ { k=零 } ^ { n 影一 } E ( x + { \ frac { k } { n } } )=E ( nx ) $
- $ E ( { \ frac { 一 } { n } } E ( nx ) )=E ( x ) $
- 對兩个倒反的高斯符號，有：
- 若是 x 為整數，著 $ E ( x ) + E (-x )=零 $
- 抑無 $ E ( x ) + E (-x )=影一 $
參考來源
- Crandall , Richard ; Pomerance , Carl . Prime Numbers : A Computational Perspective . New York : Springer . 兩千空一 [二千空二十二孵二孵六] . ISBN 空九三百八十七石九九五四千七百七十七石九 .（原始內容存檔佇兩千空二十二抹四鋪九）.
- Graham , Ronald L . ; Knuth , Donald E . ; Patashnik , Oren . Concrete Mathematics . Reading Ma . : Addison-Wesley . 一千九百九十四 . ISBN 空九二百空一四五五千八百空二五 .
- Hardy , G . H . ; Wright , E . M . An Introduction to the Theory of Numbers ( Fifth edition ) . Oxford : Oxford University Press . 一千九百八十 . ISBN 九百七十八八八十知知三千一百七十一孵五 .
- Lemmermeyer , Franz . Reciprocity Laws : from Euler to Eisenstein . Berlin : Springer . 兩千 . ISBN 三石五百四十五六鋪六千九百五十七石四 .
- Ribenboim , Paulo . The New Book of Prime Number Records . New York : Springer . 九百九十六 . ISBN 空九三百八十七石九九五四千四百五十七石五 .