取整函数

取整函数

对于高斯符號,有如下性质。

按定义:

[

x

]

x

<

[

x

]

+

1

{\displaystyle [x]\leq x<[x]+1}

当且仅当x为整数时取等号。

设x和n为正整数,则:

[

n

x

]

n

x

x

1

x

{\displaystyle \left[{\frac {n}{x}}\right]\geq {\frac {n}{x}}-{\frac {x-1}{x}}}

当n为正整数时,有:

[

x

n

]

=

x

x

mod

n

n

,

{\displaystyle \left\lbrack {\frac {x}{n}}\right\rbrack ={\frac {x-x{\bmod {n}}}{n}},}

其中

x

mod

n

{\displaystyle x{\bmod {n}}}

表示

x

{\displaystyle x}

除以

n

{\displaystyle n}

的餘數。

对任意的整数k和任意实数x,

[

k

+

x

]

=

k

+

[

x

]

.

{\displaystyle [{k+x}]=k+[x].}

一般的數值修約規則可以表述为将x映射到floor(x + 0.5);

高斯符號不是连续函数,但是上半连续的。作为一个分段的常数函数,在其导数有定义的地方,高斯符號导数为零。

设x为一个实数,n为整数,则由定义,n ≤ x当且仅当n ≤ floor(x)。

當x是正數時,有:

[

2

x

]

2

[

x

]

1

{\displaystyle \left\lbrack 2x\right\rbrack -2\left\lbrack x\right\rbrack \leqslant 1}

用高斯符號可以写出若干个素数公式,但没有什么实际价值,見§ 質數公式。

对于非整数的x,高斯符號有如下的傅里叶级数展开:

[

x

]

=

x

1

2

+

1

π

k

=

1

sin

(

2

π

k

x

)

k

.

{\displaystyle [x]=x-{\frac {1}{2}}+{\frac {1}{\pi }}\sum _{k=1}^{\infty }{\frac {\sin(2\pi kx)}{k}}.}

根据Beatty定理,每个正无理数都可以通过高斯符號制造出一个整数集的分划。

最后,对于每个正整数k,其在 p 进制下的表示有

[

log

p

(

k

)

]

+

1

{\displaystyle [\log _{p}(k)]+1}

个数位。

函數間之關係

编辑

由上下取整函數的定義,可見

x

x

,

{\displaystyle \lfloor x\rfloor \leq \lceil x\rceil ,}

等號當且僅當

x

{\displaystyle x}

為整數,即

x

x

=

{

0

,

x

Z

,

1

,

x

Z

.

{\displaystyle \lceil x\rceil -\lfloor x\rfloor ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

實際上,上取整與下取整函數作用於整數

n

{\displaystyle n}

,效果等同恆等函數:

n

=

n

=

n

.

{\displaystyle \lfloor n\rfloor =\lceil n\rceil =n.}

自變量加負號,相當於將上取整與下取整互換,外面再加負號,即:

x

+

x

=

0

,

x

=

x

,

x

=

x

.

{\displaystyle {\begin{aligned}\lfloor x\rfloor +\lceil -x\rceil &=0,\\-\lfloor x\rfloor &=\lceil -x\rceil ,\\-\lceil x\rceil &=\lfloor -x\rfloor .\end{aligned}}}

且:

x

+

x

=

{

0

,

x

Z

,

1

,

x

Z

,

{\displaystyle \lfloor x\rfloor +\lfloor -x\rfloor ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\-1,&{\text{ 若 }}\ x\not \in \mathbb {Z} ,\end{cases}}}

x

+

x

=

{

0

,

x

Z

,

1

,

x

Z

.

{\displaystyle \lceil x\rceil +\lceil -x\rceil ={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

至於小數部分

{

x

}

=

x

x

{\displaystyle \{x\}=x-\lfloor x\rfloor }

,自變量取相反數會使小數部分變成關於1的「補數」:

{

x

}

+

{

x

}

=

{

0

,

x

Z

,

1

,

x

Z

.

{\displaystyle \{x\}+\{-x\}={\begin{cases}0,&{\text{ 若 }}\ x\in \mathbb {Z} ,\\1,&{\text{ 若 }}\ x\not \in \mathbb {Z} .\end{cases}}}

上取整、下取整、小數部分皆為冪等函數,即函數疊代兩次的結果等於自身:

x

=

x

,

x

=

x

,

{

{

x

}

}

=

{

x

}

.

{\displaystyle {\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}}}

而多個上取整與下取整依次疊代的效果,相當於最內層一個:

x

=

x

,

x

=

x

,

{\displaystyle {\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

{\displaystyle m}

n

{\displaystyle n}

為正整數,且

n

0

{\displaystyle n\neq 0}

,則

0

{

m

n

}

1

1

|

n

|

.

{\displaystyle 0\leq \left\{{\frac {m}{n}}\right\}\leq 1-{\frac {1}{|n|}}.}

n

{\displaystyle n}

為正整數,則[3]

x

+

m

n

=

x

+

m

n

,

{\displaystyle \left\lfloor {\frac {x+m}{n}}\right\rfloor =\left\lfloor {\frac {\lfloor x\rfloor +m}{n}}\right\rfloor ,}

x

+

m

n

=

x

+

m

n

.

{\displaystyle \left\lceil {\frac {x+m}{n}}\right\rceil =\left\lceil {\frac {\lceil x\rceil +m}{n}}\right\rceil .}

m

{\displaystyle m}

為正數,則[4]

n

=

n

m

+

n

1

m

+

+

n

m

+

1

m

,

{\displaystyle n=\left\lceil {\frac {n}{m}}\right\rceil +\left\lceil {\frac {n-1}{m}}\right\rceil +\dots +\left\lceil {\frac {n-m+1}{m}}\right\rceil ,}

n

=

n

m

+

n

+

1

m

+

+

n

+

m

1

m

.

{\displaystyle n=\left\lfloor {\frac {n}{m}}\right\rfloor +\left\lfloor {\frac {n+1}{m}}\right\rfloor +\dots +\left\lfloor {\frac {n+m-1}{m}}\right\rfloor .}

m

=

2

{\displaystyle m=2}

,上式推出:

n

=

n

2

+

n

2

.

{\displaystyle n=\left\lfloor {\frac {n}{2}}\right\rfloor +\left\lceil {\frac {n}{2}}\right\rceil .}

更一般地,對正整數

m

{\displaystyle m}

,有埃爾米特恆等式(英语:Hermite's identity):[5]

m

x

=

x

+

x

1

m

+

+

x

m

1

m

,

{\displaystyle \lceil mx\rceil =\left\lceil x\right\rceil +\left\lceil x-{\frac {1}{m}}\right\rceil +\dots +\left\lceil x-{\frac {m-1}{m}}\right\rceil ,}

m

x

=

x

+

x

+

1

m

+

+

x

+

m

1

m

.

{\displaystyle \lfloor mx\rfloor =\left\lfloor x\right\rfloor +\left\lfloor x+{\frac {1}{m}}\right\rfloor +\dots +\left\lfloor x+{\frac {m-1}{m}}\right\rfloor .}

對於正整數

m

{\displaystyle m}

,以下兩式可將上下取整函數互相轉化:[6]

n

m

=

n

+

m

1

m

=

n

1

m

+

1

,

{\displaystyle \left\lceil {\frac {n}{m}}\right\rceil =\left\lfloor {\frac {n+m-1}{m}}\right\rfloor =\left\lfloor {\frac {n-1}{m}}\right\rfloor +1,}

n

m

=

n

m

+

1

m

=

n

+

1

m

1.

{\displaystyle \left\lfloor {\frac {n}{m}}\right\rfloor =\left\lceil {\frac {n-m+1}{m}}\right\rceil =\left\lceil {\frac {n+1}{m}}\right\rceil -1.}

對任意正整數

m

{\displaystyle m}

n

{\displaystyle n}

,有:[7]

k

=

1

n

1

k

m

n

=

(

m

1

)

(

n

1

)

+

gcd

(

m

,

n

)

1

2

,

{\displaystyle \sum _{k=1}^{n-1}\left\lfloor {\frac {km}{n}}\right\rfloor ={\frac {(m-1)(n-1)+\gcd(m,n)-1}{2}},}

作為特例,當

m

{\displaystyle m}

n

{\displaystyle n}

互質時,上式簡化為

k

=

1

n

1

k

m

n

=

1

2

(

m

1

)

(

n

1

)

.

{\displaystyle \sum _{k=1}^{n-1}\left\lfloor {\frac {km}{n}}\right\rfloor ={\frac {1}{2}}(m-1)(n-1).}

此等式可以幾何方式證明。又由於右式關於

m

{\displaystyle m}

n

{\displaystyle n}

對稱,可得

m

n

+

2

m

n

+

+

(

n

1

)

m

n

=

n

m

+

2

n

m

+

+

(

m

1

)

n

m

.

{\displaystyle \left\lfloor {\frac {m}{n}}\right\rfloor +\left\lfloor {\frac {2m}{n}}\right\rfloor +\dots +\left\lfloor {\frac {(n-1)m}{n}}\right\rfloor =\left\lfloor {\frac {n}{m}}\right\rfloor +\left\lfloor {\frac {2n}{m}}\right\rfloor +\dots +\left\lfloor {\frac {(m-1)n}{m}}\right\rfloor .}

更一般地,對正整數

m

,

n

{\displaystyle m,n}

,有

x

n

+

m

+

x

n

+

2

m

+

x

n

+

+

(

n

1

)

m

+

x

n

=

x

m

+

n

+

x

m

+

2

n

+

x

m

+

+

(

m

1

)

n

+

x

m

.

{\displaystyle {\begin{aligned}&\left\lfloor {\frac {x}{n}}\right\rfloor +\left\lfloor {\frac {m+x}{n}}\right\rfloor +\left\lfloor {\frac {2m+x}{n}}\right\rfloor +\dots +\left\lfloor {\frac {(n-1)m+x}{n}}\right\rfloor \\=&\left\lfloor {\frac {x}{m}}\right\rfloor +\left\lfloor {\frac {n+x}{m}}\right\rfloor +\left\lfloor {\frac {2n+x}{m}}\right\rfloor +\cdots +\left\lfloor {\frac {(m-1)n+x}{m}}\right\rfloor .\end{aligned}}}

上式算是一種「互反律」(reciprocity law)[7],與§ 二次互反律有關。

💡 相关推荐

[交流]试了几天的新归墟,说下感想了
365bet足球外围网站

[交流]试了几天的新归墟,说下感想了

📅 07-08 👀 3106
梦幻开服多久可以转入——了解转服全流程
谁有365bet网址

梦幻开服多久可以转入——了解转服全流程

📅 07-04 👀 3727
《率土之滨》平民赛季步兵武将推荐
365bet足球外围网站

《率土之滨》平民赛季步兵武将推荐

📅 06-29 👀 221