Editing Floor and ceiling functions (section)

==Applications==

===Mod operator===

For an integer ''x'' and a positive integer ''y'', the [[modulo operation]], denoted by ''x'' mod ''y'', gives the value of the remainder when ''x'' is divided by ''y''.  This definition can be extended to real ''x'' and ''y'', ''y'' ≠  0, by the formula

:<math>x \bmod y = x-y\left\lfloor \frac{x}{y}\right\rfloor.</math>

Then it follows from the definition of floor function that this extended operation satisfies many natural properties.  Notably, ''x'' mod ''y'' is always between 0 and ''y'', i.e.,

if ''y'' is positive,
:<math>0 \le x \bmod y <y,</math>
and if ''y'' is negative,
:<math>0 \ge x \bmod y >y.</math>

===Quadratic reciprocity===
Gauss's third proof of [[quadratic reciprocity]], as modified by Eisenstein, has two basic steps.<ref>Lemmermeyer, § 1.4, Ex. 1.32–1.33</ref><ref>Hardy & Wright, §§ 6.11–6.13</ref>

Let ''p'' and ''q'' be distinct positive odd prime numbers, and let <math>m = \tfrac12(p - 1),</math>  <math>n = \tfrac12(q - 1).</math>

First, [[Gauss's lemma (number theory)|Gauss's lemma]] is used to show that the [[Legendre symbol]]s are given by

:<math>\begin{align}
\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 }, \\[5mu]
\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 }.
\end{align}</math>

The second step is to use a [[Geometric series|geometric]] argument to show that

:<math>\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.
</math>

Combining these formulas gives quadratic reciprocity in the form

:<math>\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{mn}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.</math>

There are formulas that use floor to express the quadratic character of small numbers mod odd primes ''p'':<ref>Lemmermeyer, p. 25</ref>
:<math>\begin{align}
\left(\frac{2}{p}\right) &= (-1)^{\left\lfloor\frac{p+1}{4}\right\rfloor}, \\[5mu]
\left(\frac{3}{p}\right) &= (-1)^{\left\lfloor\frac{p+1}{6}\right\rfloor}.
\end{align}</math>

===Rounding===
For an arbitrary real number <math>x</math>, [[rounding]] <math>x</math> to the nearest integer with [[Rounding#Tie-breaking|tie breaking]] towards positive infinity is given by
:<math>\text{rpi}(x)=\left\lfloor x+\tfrac{1}{2}\right\rfloor = \left\lceil \tfrac12\lfloor 2x \rfloor \right\rceil;</math>
rounding towards negative infinity is given as
:<math>\text{rni}(x)=\left\lceil x-\tfrac{1}{2}\right\rceil = \left\lfloor \tfrac12 \lceil 2x \rceil \right\rfloor.</math>

If tie-breaking is away from 0, then the rounding function is
:<math>\text{ri}(x) = \sgn(x)\left\lfloor|x|+\tfrac{1}{2}\right\rfloor</math>
(where <math>\sgn</math> is the [[sign function]]), and [[Rounding#Rounding half to even|rounding towards even]] can be expressed with the more cumbersome
:<math>\lfloor x\rceil=\left\lfloor x+\tfrac{1}{2}\right\rfloor+\left\lceil\tfrac14(2x-1)\right\rceil-\left\lfloor\tfrac14(2x-1)\right\rfloor-1,</math>
which is the above expression for rounding towards positive infinity <math>\text{rpi}(x)</math> minus an [[integer|integrality]] [[indicator function|indicator]] for <math>\tfrac14(2x-1)</math>.

Rounding a [[real number]] <math>x</math> to the nearest integer value forms a very basic type of [[Quantization (signal processing)|quantizer]] – a ''uniform'' one.  A typical (''mid-tread'') uniform quantizer with a quantization ''step size'' equal to some value <math>\Delta</math> can be expressed as

:<math>Q(x) = \Delta \cdot  \left\lfloor \frac{x}{\Delta} + \frac{1}{2} \right\rfloor</math>,

===Number of digits===
The number of digits in [[radix|base]] ''b'' of a positive integer ''k'' is
:<math>\lfloor \log_{b}{k} \rfloor + 1 = \lceil \log_{b}{(k+1)} \rceil .</math>

===Number of strings without repeated characters===
The number of possible [[String (computer science)|strings]] of arbitrary length that doesn't use any character twice is given by<ref>{{OEIS el |1=A000522 |2=Total number of arrangements of a set with n elements: a(n) = Sum_{k=0..n} n!/k!.}} (See Formulas.)</ref>{{Better source needed|date=February 2022}} 

:<math>(n)_0 + \cdots + (n)_n = \lfloor e n! \rfloor</math>

where:

* {{math|''n''}} > 0 is the number of letters in the alphabet (e.g., 26 in [[English language|English]])
* the [[falling factorial]] <math>(n)_k = n(n-1)\cdots(n-k+1)</math> denotes the number of strings of length {{math|''k''}} that don't use any character twice.
* {{math|''n''}}! denotes the [[factorial]] of {{math|''n''}}
* {{math|''e''}} = 2.718... is [[Euler's number]]

For {{math|''n''}} = 26, this comes out to 1096259850353149530222034277.

===Factors of factorials===
Let ''n'' be a positive integer and ''p'' a positive prime number. The exponent of the highest power of ''p'' that divides ''n''! is given by a version of [[Legendre's formula]]<ref>Hardy & Wright, Th. 416</ref>

:<math>\left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + \left\lfloor\frac{n}{p^3}\right\rfloor + \dots = \frac{n-\sum_{k}a_k}{p-1}</math>

where <math display="inline">n = \sum_{k}a_kp^k</math> is the way of writing ''n'' in base ''p''. This is a finite sum, since the floors are zero when ''p''<sup>''k''</sup> > ''n''.

===Beatty sequence===
The [[Beatty sequence]] shows how every positive [[irrational number]] gives rise to a partition of the [[natural number]]s into two sequences via the floor function.<ref>Graham, Knuth, & Patashnik, pp. 77–78</ref>

===Euler's constant (γ)===
There are formulas for [[Euler–Mascheroni constant|Euler's constant]] γ = 0.57721 56649 ... that involve the floor and ceiling, e.g.<ref>These formulas are from the Wikipedia article [[Euler–Mascheroni constant|Euler's constant]], which has many more.</ref>

:<math>\gamma =\int_1^\infty\left({1\over\lfloor x\rfloor}-{1\over x}\right)\,dx,</math>

:<math>\gamma = \lim_{n \to \infty} \frac{1}{n} \sum_{k=1}^n \left( \left \lceil \frac{n}{k} \right \rceil - \frac{n}{k} \right),</math>

and

:<math>
 \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 - \cdots - \tfrac1{15}\right) + \cdots
</math>

===Riemann zeta function (ζ)===
The fractional part function also shows up in integral representations of the [[Riemann zeta function]]. It is straightforward to prove (using integration by parts)<ref>Titchmarsh, p. 13</ref> that if <math>\varphi(x)</math> is any function with a continuous derivative in the closed interval [''a'', ''b''],

:<math>\sum_{a<n\le b}\varphi(n) =
\int_a^b\varphi(x) \, dx +
\int_a^b\left(\{x\}-\tfrac12\right)\varphi'(x) \, dx +
\left(\{a\}-\tfrac12\right)\varphi(a) -
\left(\{b\}-\tfrac12\right)\varphi(b).
</math>

Letting <math>\varphi(n) = n^{-s}</math> for [[real part]] of ''s'' greater than 1 and letting ''a'' and ''b'' be integers, and letting ''b'' approach infinity gives

:<math>\zeta(s) = s\int_1^\infty\frac{\frac12-\{x\}}{x^{s+1}}\,dx + \frac{1}{s-1} + \frac 1 2.</math>

This formula is valid for all ''s'' with real part greater than &minus;1, (except ''s'' = 1, where there is a pole) and combined with the Fourier expansion for {''x''} can be used to extend the zeta function to the entire complex plane and to prove its functional equation.<ref>Titchmarsh, pp.14–15</ref>

For ''s'' = ''σ'' + ''it'' in the critical strip 0 < ''σ'' < 1,

:<math>\zeta(s)=s\int_{-\infty}^\infty e^{-\sigma\omega}(\lfloor e^\omega\rfloor - e^\omega)e^{-it\omega}\,d\omega.</math>

In 1947 [[Balthasar van der Pol|van der Pol]] used this representation to construct an analogue computer for finding roots of the zeta function.<ref>Crandall & Pomerance, p. 391</ref>

===Formulas for prime numbers===
The floor function appears in several formulas characterizing prime numbers.  For example, since
<math display=block>\left\lfloor\frac{n}{m} \right\rfloor -\left\lfloor\frac{n-1}{m}\right\rfloor = \begin{cases}
1 &\text{if } m \text{ divides } n \\
0 &\text{otherwise},
\end{cases}</math>
it follows that a positive integer ''n'' is a prime [[if and only if]]<ref>Crandall & Pomerance, Ex. 1.3, p. 46. The infinite upper limit of the sum can be replaced with ''n''. An equivalent condition is ''n''&nbsp;&gt;&nbsp;1 is prime if and only if
<math display=block>\sum_{m=1}^{\lfloor \sqrt n \rfloor} \left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 1.</math></ref>

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

One may also give formulas for producing the prime numbers.  For example, let ''p''<sub>''n''</sub> be the ''n''-th prime, and for any integer ''r''&nbsp;>&nbsp;1, define the real number ''α'' by the sum

:<math>\alpha = \sum_{m=1}^\infty p_m r^{-m^2}.</math>

Then<ref>Hardy & Wright, § 22.3</ref>

:<math>p_n = \left\lfloor r^{n^2}\alpha \right\rfloor - r^{2n-1}\left\lfloor r^{(n-1)^2}\alpha\right\rfloor.</math>

A similar result is that there is a number ''θ'' = 1.3064... ([[Mills' constant]]) with the property that

:<math>\left\lfloor \theta^3 \right\rfloor, \left\lfloor \theta^9 \right\rfloor, \left\lfloor \theta^{27} \right\rfloor, \dots</math>

are all prime.<ref name="Ribenboim, p. 186">Ribenboim, p. 186</ref>

There is also a number ''ω'' = 1.9287800... with the property that

:<math>\left\lfloor 2^\omega\right\rfloor, \left\lfloor 2^{2^\omega} \right\rfloor, \left\lfloor 2^{2^{2^\omega}} \right\rfloor, \dots</math>

are all prime.<ref name="Ribenboim, p. 186"/>

Let {{pi}}(''x'') be [[Prime-counting function|the number of primes less than or equal to ''x'']]. It is a straightforward deduction from [[Wilson's theorem]] that<ref>Ribenboim, p. 181</ref>

:<math>\pi(n) = \sum_{j=2}^n\Biggl\lfloor\frac{(j-1)!+1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor\Biggr\rfloor.</math>

Also, if ''n'' ≥ 2,<ref>Crandall & Pomerance, Ex. 1.4, p. 46</ref>

:<math>\pi(n) = \sum_{j=2}^n \left\lfloor \frac{1} {\displaystyle\sum_{k=2}^j\left\lfloor\left\lfloor\frac{j}{k}\right\rfloor\frac{k}{j} \right\rfloor} \right\rfloor.</math>

None of the formulas in this section are of any practical use.<ref>Ribenboim, p. 180 says that "Despite the nil practical value of the formulas ... [they] may have some relevance to logicians who wish to understand clearly how various parts of arithmetic may be deduced from different axiomatzations ... "</ref><ref>Hardy & Wright, pp. 344—345 "Any one of these formulas (or any similar one) would attain a different status if the exact value of the number α ... could be expressed independently of the primes. There seems no likelihood of this, but it cannot be ruled out as entirely impossible."</ref>

===Solved problems===
[[Ramanujan]] submitted these problems to the ''Journal of the Indian Mathematical Society''.<ref>Ramanujan, Question 723, ''Papers'' p. 332</ref>

If ''n'' is a positive integer, prove that
<ol type="i">
<li> <math>\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,</math></li>

<li> <math>\left\lfloor\tfrac12 + \sqrt{n+\tfrac12}\right\rfloor = \left\lfloor\tfrac12 + \sqrt{n+\tfrac14}\right\rfloor,</math></li>

<li> <math>\left\lfloor\sqrt{n}+ \sqrt{n+1}\right\rfloor = \left\lfloor \sqrt{4n+2}\right\rfloor.</math></li>
</ol>Some generalizations to the above floor function identities have been proven.<ref>{{Cite journal |last1=Somu |first1=Sai Teja |last2=Kukla |first2=Andrzej |title=On some generalizations to floor function identities of Ramanujan |url=http://math.colgate.edu/~integers/w33/w33.pdf |journal=Integers |year=2022 |volume=22|arxiv=2109.03680 }}</ref>

===Unsolved problem===
The study of [[Waring's problem]] has led to an unsolved problem:

Are there any positive integers ''k'' ≥ 6 such that<ref>Hardy & Wright, p. 337</ref>

:<math>3^k-2^k\Bigl\lfloor \bigl(\tfrac 3 2\bigr)^k \Bigr\rfloor  > 2^k-\Bigl\lfloor \bigl(\tfrac 3 2\bigr)^k \Bigr\rfloor -2 \ ?</math> 

[[Kurt Mahler|Mahler]] has proved there can only be a finite number of such ''k''; none are known.<ref>{{cite journal
| last1=Mahler | first1=Kurt | authorlink1=Kurt Mahler
| title=On the fractional parts of the powers of a rational number II
| date=1957
| journal=[[Mathematika]]
| volume=4
| issue=2 | pages=122–124
| doi=10.1112/S0025579300001170}}</ref>