Phần nguyên

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Các hàm Floor và ceiling

Hàm Floor
Hàm Ceiling

Trong toán họckhoa học máy tính, hàm floorceiling là các qui tắc cho tương ứng một số thực vào một số nguyên gần nhất bên trái và bên phải số đã cho. Vậy floor(x) là số nguyên lớn nhất không vượt quá x, còn ceiling(x) là số nguyên nhỏ nhất không nhỏ hơn x.

Kí hiệu[sửa | sửa mã nguồn]

Gauss giới thiệu cặp ngoặc vuông [x] cho hàm floor trong quadratic reciprocity (1808).[1] Nó vẫn là ký hiệu tiêu chuẩn[2] trong toán học cho đến khi Iverson giới thiệu các hàm "floor" và "ceiling" với các ký hiệu \lfloor x \rfloor\lceil x \rceil vào năm 1962 trong ngôn ngữ lập trình APL của ông ấy.[3][4] Bây giờ cả hai cách ký hiệu vẫn đang được dùng trong toán học.

Ví dụ[sửa | sửa mã nguồn]

x Floor(x) \lfloor\;\rfloor Ceiling(x) \lceil\;\rceil Phần lẻ  \{ \; \}
−2.7 −3 −2 0.3
−2 −2 −2 0
12/5 = 2.4 2 3 2/5 = 0.4
2.7 2 3 0.7

Đọc phần bên dưới để biết thêm về định nghĩa phần lẻ.

Định nghĩa và tính chất[sửa | sửa mã nguồn]

Trong những công thức dưới đây. xy là các số thực, k, m, và n là các số nguyên, và \mathbb{Z} là tập hợp số nguyên (số dương, số âm, và không).

Floor và ceiling có thể được định nghĩa bằng tập hợp như sau

 \lfloor x \rfloor=\max\, \{n\in\mathbb{Z}\mid n\le x\},
 \lceil x \rceil=\min\,\{n\in\mathbb{Z}\mid n\ge x\}.

Trong nữa khoảng có độ dài bằng một có duy nhất một số nguyên, vậy với số thực x tùy ý, có duy nhất cặp m,n thỏa mãn

x-1<m\le x \le n <x+1.\;

Khi đó  \lfloor x \rfloor = m\;  and  \;\lceil x \rceil = n\;  có thể là định nghĩa cho các hàm floor và ceiling.

Phần lẻ x kí hiệu \{x\} là hàm số định nghĩa theo công thức sau,   \{x\} = x -\lfloor x\rfloor,  and   Toán tử mô-đun được định nghĩa theo công thức x \,\bmod\, y = x-y\left\lfloor \frac{x}{y}\right\rfloor.

Equivalences[sửa | sửa mã nguồn]

Các công thức dưới đây dùng để rút gọn các biểu thức chứa các hàm floors, ceilings.[5]


\begin{align}
\lfloor x \rfloor = n &\;\;\Leftrightarrow &n &\le x < n+1,\\
\lceil x \rceil = n &\;\;\Leftrightarrow &n -1 &< x \le n,\\

\lfloor x \rfloor = n &\;\;\Leftrightarrow &x-1 &< n \le x,\\
\lceil x \rceil = n &\;\;\Leftrightarrow &x &\le n < x+1.
\end{align}

In the language of order theory, the floor function is a residuated mapping, that is, part of a Galois connection: it is the upper adjoint of the function that embeds the integers into the reals.


\begin{align}
x<n &\;\;\Leftrightarrow &\lfloor x \rfloor &< n, \\
n<x &\;\;\Leftrightarrow &n &< \lceil x \rceil, \\
x\le n &\;\;\Leftrightarrow &\lceil  x \rceil &\le n, \\
n\le x &\;\;\Leftrightarrow &n &\le \lfloor x \rfloor.
\end{align}

Các công thức dưới đây đưa ra quy tắc khi cộng thêm một số nguyên vào các hàm phần nguyên như thế nào:


\begin{align}
\lfloor x+n \rfloor &= \lfloor x \rfloor+n,\\
\lceil x+n \rceil &= \lceil x \rceil+n,\\
\{ x+n \} &= \{ x \}.
\end{align}

Các công thức trên không đúng nếu n không phải số nguyên, tuy vậy:

\begin{align}
&\lfloor x \rfloor + \lfloor y \rfloor &\leq \;\lfloor x + y \rfloor \;&\leq\; \lfloor x \rfloor + \lfloor y \rfloor + 1,\\
&\lceil x \rceil + \lceil y \rceil -1 &\leq \;\lceil x + y \rceil \;&\leq \;\lceil x \rceil + \lceil y \rceil.
\end{align}

Mối liên hệ giữa các hàm[sửa | sửa mã nguồn]

Từ định nghĩa dễ dàng có được

\lfloor x \rfloor \le \lceil x \rceil,   dấu bằng xảy ra khi và chỉ khi x là số nguyên, i.e.
\lceil x \rceil - \lfloor x \rfloor = \begin{cases}
0&\mbox{ if } x\in \mathbb{Z}\\
1&\mbox{ if } x\not\in \mathbb{Z}
\end{cases}

n là số nguyên thì:

\lfloor n \rfloor = \lceil n \rceil = n.

Khi số âm là đối số thì đổi các hàm floor và ceil đồng thời đưa dấu trừ ra ngoài:

\lfloor x \rfloor +\lceil -x \rceil=0,   tức là:
\lfloor -x \rfloor =-\lceil x \rceil,
\lceil -x \rceil =-\lfloor x \rfloor,
\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases}
0&\mbox{ if } x\in \mathbb{Z}\\
-1&\mbox{ if } x\not\in \mathbb{Z},
\end{cases}
\lceil x \rceil + \lceil -x \rceil = \begin{cases}
0&\mbox{ if } x\in \mathbb{Z}\\
1&\mbox{ if } x\not\in \mathbb{Z}.
\end{cases}

Về phần lẻ:

\{ x \} +  \{ -x \} = \begin{cases}
0&\mbox{ if } x\in \mathbb{Z}\\
1&\mbox{ if } x\not\in \mathbb{Z}.
\end{cases}

Floor, ceiling, và phần lẻ là hàm idempotent:


\begin{align}
\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{align}

Dể thấy các đẳng thức sau là đúng:


\begin{align}
\Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\
\Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor. \\
\end{align}

Với y có định thì, x mod y là hàm idempotent:

(x \,\bmod\, y) \,\bmod\, y =  x \,\bmod\, y.\;

Cũng từ định nghĩa ta có,

\{x\}= x \,\bmod\, 1.\;

Phép chia[sửa | sửa mã nguồn]

Nếu n ≠ 0,

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

Nếu n > 0,

\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.

Nếu m > 0,

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=\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.

Với m = 2:

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

Tổng quát,[6] với m > 0,

\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,
\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.

Biểu thức dưới đây dùng để chuyển đổi floors sang ceilings và ngược lại (m > 0)[7]

\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,
\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,

Nếu mn là các số nguyên dươngnguyên tố cùng nhau, thì

\sum_{i=1}^{n-1} \left\lfloor \frac{im}{n} \right\rfloor = \frac{1}{2}(m - 1)(n - 1).

Vì vế phải của biểu thức trên đối xứng theo mn, vậy nên ta có biểu thức dưới đây

\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.

Tổng quát, nếu mn nguyên dương,

\begin{align}
&\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 + 
\dots + 
\left\lfloor \frac{(m-1)n+x}{m} \right \rfloor.
\end{align}

Cho các số nguyên dương m,n, and arbitrary real number x:

 \left\lfloor \frac{\lfloor x/m\rfloor}{n} \right\rfloor = \left\lfloor \frac{x}{mn} \right\rfloor
 \left\lceil \frac{\lceil x/m\rceil}{n} \right\rceil = \left\lceil \frac{x}{mn} \right\rceil

Sự liên tục[sửa | sửa mã nguồn]

Không có hàm nào chúng ta đang xét là liên tục cả, nhưng đều tuyến tính trên từng đoạn. \lfloor x \rfloor  and \lceil x \rceilhàm hằng trên từng đoạn và gián đoạn tại các điểm nguyên. Hàm \{ x\} cũng gián đoạn tại các điểm nguyên, và   x  \,\bmod\, y với biến x hằng y gián đoạn tại các bội của y.

\lfloor x \rfloor  is upper semi-continuous and  \lceil x \rceil  and \{ x\}\;  are lower semi-continuous. x mod y is lower semicontinuous for positive y and upper semi-continuous for negative y.

Khai triển chuỗi[sửa | sửa mã nguồn]

Các hàm chúng ta đang xét đều không liên tục vì thế chúng không có các khai triển chuỗi lũy thừa. Hàm floor và ceiling không liên tục nên không có khai triển Fourier.

Với y cố định,x mod y có khai triển Fourier [8]

x \,\bmod\, y = \frac{y}{2} - \frac{y}{\pi} \sum_{k=1}^\infty 
\frac{\sin\left(\frac{2 \pi k x}{y}\right)} {k}.

Phần lẻ {x} = x mod 1 khai triển:

\{x\}= \frac{1}{2} - \frac{1}{\pi} \sum_{k=1}^\infty 
\frac{\sin(2 \pi k x)} {k}.

Dùng công thức {x} = x − floor(x), floor(x) = x − {x} ta có

\lfloor x\rfloor = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}.

Ứng dụng[sửa | sửa mã nguồn]

Phần lẻ[sửa | sửa mã nguồn]

Hàm phần lẻhàm răng cưa, kí hiệu \{x\} với x là số thực, được định nghĩa bởi công thức[9]

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

Với mọi x,

0\le\{x\}<1.\;

Với x>0 trong dạng thập phân, floor(x) là phần bên trái của biểu diễn thập phân, phần lẻ của x là phần bên phải khi thay tất cả các số bên trái bởi 0.

Toán tử mod[sửa | sửa mã nguồn]

Toán tử mod, kí hiệu là x mod y,x, y thực, y ≠ 0, xác định theo công thức

x \,\bmod\, y = x-y\left\lfloor \frac{x}{y}\right\rfloor.

x mod y luôn nằm giữa 0 và y; i.e.

Nếu y > 0,

0 \le x \,\bmod\, y <y,

còn nếu y < 0,

0 \ge x \,\bmod\, y >y.

Nếu x nguyên còn y nguyên dương,

(x \,\bmod\, y) \equiv x \pmod{y}.

x mod y với y có định là hàm răng cưa.

Quadratic reciprocity[sửa | sửa mã nguồn]

Gauss's third proof of quadratic reciprocity, as modified by Eisenstein, has two basic steps.[10][11]

Let p and q be distinct positive odd prime numbers, and let

m = \frac{p - 1}{2},\;\; n = \frac{q - 1}{2}.

First, Gauss's lemma is used to show that the Legendre symbols are given by

\left(\frac{q}{p}\right) = (-1)^{\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor }

and

\left(\frac{p}{q}\right) = (-1)^{\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor }.

The second step is to use a geometric argument to show that

\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor

+\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor

= mn.

Combining these formulas gives quadratic reciprocity in the form

\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{mn}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.

There are formulas that use floor to express the quadratic character of small numbers mod odd primes p:[12]

\left(\frac{2}{p}\right)  = (-1)^{\left\lfloor\frac{p+1}{4}\right\rfloor},
\left(\frac{3}{p}\right)  = (-1)^{\left\lfloor\frac{p+1}{6}\right\rfloor}.

Làm tròn[sửa | sửa mã nguồn]

Việc làm tròn các số dương x đến số nguyên gần nhất được diễn tả như sau \lfloor x + 0.5\rfloor.

Số các chữ số[sửa | sửa mã nguồn]

Số các chử số trong hệ cơ số b của số nguyên dương k

\lfloor \log_{b}{k} \rfloor + 1.

Thừa số của giai thừa[sửa | sửa mã nguồn]

đặt n nguyên dương và psố nguyên tố. Lũy thừa của p trong khai triển của n! được cho bởi công thức[13]

\left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + \left\lfloor\frac{n}{p^3}\right\rfloor + \dots

Chú ý rằng đó là tổng có giới hạn, số hạng bằng không khi pk > n.

Beatty sequence[sửa | sửa mã nguồn]

Beatty sequence shows how every positive irrational number gives rise to a partition of the natural numbers into two sequences via the floor function.[14]

Hằng số Euler γ[sửa | sửa mã nguồn]

Đây là những công thức cho Hằng số Euler γ = 0.57721 56649... chứa các hàm floor và ceiling, e.g.[15]

\gamma =\int_1^\infty\left({1\over\lfloor x\rfloor}-{1\over x}\right)\,dx,
 \gamma =      \lim_{n \to \infty} \frac{1}{n}\, \sum_{k=1}^n \left ( \left \lceil \frac{n}{k} \right \rceil - \frac{n}{k} \right ),


 \gamma = \sum_{k=2}^\infty (-1)^k \frac{ \left \lfloor \log_2 k \right \rfloor}{k}
  = \tfrac12-\tfrac13
  + 2\left(\tfrac14 - \tfrac15 + \tfrac16 - \tfrac17\right)
  + 3\left(\tfrac18 - \dots - \tfrac1{15}\right) + \dots

Hàm Riemann ζ[sửa | sửa mã nguồn]

Các công thức cho số nguyên tố[sửa | sửa mã nguồn]

n là số nguyên tố khi và chỉ khi[16]


\sum_{m=1}^\infty \left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 2.

r là số nguyên lớn hơn 1, pn là số nguyên tố thứ n, kí hiệu

\alpha = \sum_{m=1}^\infty p_m r^{-m^2}.

Thì[17]

p_n = \left\lfloor r^{n^2}\alpha \right\rfloor - r^{2n-1}\left\lfloor r^{(n-1)^2}\alpha\right\rfloor.

Có số θ = 1.3064... với tính chất

\left\lfloor \theta^3 \right\rfloor, \left\lfloor \theta^9 \right\rfloor, \left\lfloor \theta^{27} \right\rfloor, \dots

đều là số nguyên tố.[18]

Cũng có thêm số ω = 1.9287800... mà

\left\lfloor 2^\omega\right\rfloor, \left\lfloor 2^{2^\omega} \right\rfloor, \left\lfloor 2^{2^{2^\omega}} \right\rfloor, \dots

đều nguyên tố.[18]

π(x) là số các số nguyên tố nhỏ hơn hoặc bằng x. Nó được suy luận từ Định lý Wilson[19]

\pi(n) = \sum_{j=2}^n\left\lfloor\frac{(j-1)!+1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor\right\rfloor.

Nếu n ≥ 2,[20]


\pi(n) = \sum_{j=2}^n \left\lfloor \frac{1}{\sum_{k=2}^j\left\lfloor\left\lfloor\frac{j}{k}\right\rfloor\frac{k}{j}\right\rfloor}\right\rfloor.

Không công thức nào trên đây ứng dụng thực tế.

Vấn đề đả giải quyết[sửa | sửa mã nguồn]

Ramanujan đả gửi các bài toán sau đây đến Journal of the Indian Mathematical Society.[21]

Cho n là số nguyên dương, chứng minh rằng

(i)     \left\lfloor\tfrac{n}{3}\right\rfloor + \left\lfloor\tfrac{n+2}{6}\right\rfloor + \left\lfloor\tfrac{n+4}{6}\right\rfloor = \left\lfloor\tfrac{n}{2}\right\rfloor + \left\lfloor\tfrac{n+3}{6}\right\rfloor,

(ii)     \left\lfloor\tfrac12 + \sqrt{n+\tfrac12}\right\rfloor = \left\lfloor\tfrac12 + \sqrt{n+\tfrac14}\right\rfloor,

(iii)     \left\lfloor\sqrt{n}+ \sqrt{n+1}\right\rfloor = \left\lfloor \sqrt{4n+2}\right\rfloor.

Vấn đề chưa giải quyết[sửa | sửa mã nguồn]

Có số nguyên dương k nào thỏa mãn, k ≥ 6, mà[22]

3^k-2^k\left\lfloor \left(\tfrac32\right)^k \right\rfloor  > 2^k-\left\lfloor \left(\tfrac32\right)^k \right\rfloor -2\;\;?

Mahler[23] has proved there can only be a finite number of such k; none are known.

Xem thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

  1. ^ Lemmermeyer, pp. 10, 23
  2. ^ e.g. Cassels, Hardy & Wright, and Ribenboim use Gauss's notation, Graham, Knuth & Patashnik, and Crandall & Pomerance use Iverson's
  3. ^ Higham, p. 25
  4. ^ Iverson
  5. ^ Graham, Knuth, & Patashink, Ch. 3
  6. ^ Graham, Knuth, & Patashnik, p. 85 and Ex. 3.15
  7. ^ Graham, Knuth, & Patashnik, Ex. 3.12
  8. ^ Titchmarsh, p. 15, Eq. 2.1.7
  9. ^ Graham, Knuth, & Patashnik, p. 70
  10. ^ Lemmermeyer, § 1.4, Ex. 1.32–1.33
  11. ^ Hardy & Wright, §§ 6.11–6.13
  12. ^ Lemmermeyer, p. 25
  13. ^ Hardy & Wright, Th. 416
  14. ^ Graham, Knuth, & Patashnik, pp. 77–78
  15. ^ These formulas are from the Wikipedia article Euler's constant, which has many more.
  16. ^ Crandall & Pomerance, Ex. 1.3, p. 46
  17. ^ Hardy & Wright, § 22.3
  18. ^ a ă Ribenboim, p. 186
  19. ^ Ribenboim, p. 181
  20. ^ Crandall & Pomerance, Ex. 1.4, p. 46
  21. ^ Ramanujan, Question 723, Papers p. 332
  22. ^ Hardy & Wright, p. 337
  23. ^ Mahler, K. On the fractional parts of the powers of a rational number II, 1957, Mathematika, 4, pages 122-124

Tham khảo[sửa | sửa mã nguồn]

  • J.W.S. Cassels (1957). An introduction to Diophantine approximation. Cambridge Tracts in Mathematics and Mathematical Physics 45. Cambridge University Press. 
  • Crandall, Richard; Pomeramce, Carl (2001), Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-04777-9 Kiểm tra giá trị |isbn= (trợ giúp) 
  • Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994), Concrete Mathematics, Reading Ma.: Addison-Wesley, ISBN 0-201-55802-5 
  • Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715 
  • Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0898714206, p. 25
  • ISO/IEC. ISO/IEC 9899::1999(E): Programming languages — C (2nd ed), 1999; Section 6.3.1.4, p. 43.
  • Iverson, Kenneth E. (1962), A Programming Language, Wiley 
  • Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66967-4 Kiểm tra giá trị |isbn= (trợ giúp) 
  • Ramanujan, Srinivasa (2000), Collected Papers, Providence RI: AMS / Chelsea, ISBN 978-0821820766 
  • Ribenboim, Paulo (1996), The New Book of Prime Number Records, New York: Springer, ISBN 0-387-94457-5 
  • Michael Sullivan. Precalculus, 8th edition, p. 86
  • Titchmarsh, Edward Charles; Heath-Brown, David Rodney ("Roger") (1986), The Theory of the Riemann Zeta-function (ấn bản 2), Oxford: Oxford U. P., ISBN 0-19-853369-1 

Liên kết ngoài[sửa | sửa mã nguồn]

  • Štefan Porubský, "Integer rounding functions", Interactive Information Portal for Algorithmic Mathematics, Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic, retrieved 10/24/2008