The Floor Function

How many multiples of 7 are there between 1 and 100?

You could list them: 7, 14, 21, ..., 98. Count: 14.

Or you could compute $\lfloor 100/7 \rfloor = 14$ directly.

The floor function is the bridge between division and counting. Every time a problem asks "how many integers satisfy...", the floor function is either the answer or the tool that finds it.

---

The definition

The floor of a real number $x$, written $\lfloor x \rfloor$, is the largest integer that does not exceed $x$.

$\lfloor x \rfloor = \max\{n \in \mathbb{Z} : n \leq x\}$

Equivalently: $\lfloor x \rfloor = n$ where $n$ is the unique integer satisfying $n \leq x < n+1$.

Examples:

• $\lfloor 3.7 \rfloor = 3$
• $\lfloor 5 \rfloor = 5$
• $\lfloor -2.3 \rfloor = -3$ (not $-2$ — the floor goes down)
• $\lfloor \pi \rfloor = 3$
• $\lfloor -\pi \rfloor = -4$

The fractional part is defined as $\{x\} = x - \lfloor x \rfloor$. Always satisfies $0 \leq \{x\} < 1$.

---

Basic properties

P1. $\lfloor x \rfloor \leq x < \lfloor x \rfloor + 1$

P2. $\lfloor x \rfloor = x \iff x$ is an integer.

P3. $\lfloor x + n \rfloor = \lfloor x \rfloor + n$ for any integer $n$.

Proof. Adding an integer shifts $x$ without changing its fractional part. $\blacksquare$

P4. $\lfloor x \rfloor + \lfloor y \rfloor \leq \lfloor x + y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1$

Proof. Write $x = \lfloor x \rfloor + \{x\}$ and $y = \lfloor y \rfloor + \{y\}$. Then $x+y = (\lfloor x\rfloor + \lfloor y\rfloor) + (\{x\}+\{y\})$. Since $0 \leq \{x\}+\{y\} < 2$, the floor of $x+y$ is either $\lfloor x\rfloor + \lfloor y\rfloor$ or $\lfloor x\rfloor + \lfloor y\rfloor + 1$. $\blacksquare$

P5. $\lfloor x/n \rfloor = \lfloor \lfloor x \rfloor / n \rfloor$ for positive integer $n$.

This one is subtle but very useful — you can take the floor inside or outside, result is the same.

Common mistake. $\lfloor x + y \rfloor \neq \lfloor x \rfloor + \lfloor y \rfloor$ in general. Example: $\lfloor 0.6 + 0.7 \rfloor = \lfloor 1.3 \rfloor = 1$ but $\lfloor 0.6 \rfloor + \lfloor 0.7 \rfloor = 0$.

---

Counting with the floor function

Multiples of $d$ up to $n$: The number of positive multiples of $d$ that do not exceed $n$ is $\lfloor n/d \rfloor$.

Proof. The multiples are $d, 2d, 3d, \ldots$ The largest one $\leq n$ is $d \cdot \lfloor n/d \rfloor$, so there are $\lfloor n/d \rfloor$ of them. $\blacksquare$

Integers in an interval: The number of integers in $[a, b]$ is $\lfloor b \rfloor - \lceil a \rceil + 1$, where $\lceil a \rceil = -\lfloor -a \rfloor$ is the ceiling function.

For integers $a \leq b$: count is $b - a + 1$.

---

Legendre's formula — highest power of a prime in $n!$

Theorem. The largest power of prime $p$ dividing $n!$ is:

$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$

(The sum is finite since $\lfloor n/p^k \rfloor = 0$ for $p^k > n$.)

Why. Among $1, 2, \ldots, n$:

• $\lfloor n/p \rfloor$ multiples of $p$ — each contributes at least one factor of $p$
• $\lfloor n/p^2 \rfloor$ multiples of $p^2$ — each contributes an extra factor
• $\lfloor n/p^3 \rfloor$ multiples of $p^3$ — each contributes yet another
• and so on.

Total factors of $p$ in $n!$ is the sum. $\blacksquare$

Example. Highest power of 2 in $100!$:

$\left\lfloor \frac{100}{2} \right\rfloor + \left\lfloor \frac{100}{4} \right\rfloor + \left\lfloor \frac{100}{8} \right\rfloor + \left\lfloor \frac{100}{16} \right\rfloor + \left\lfloor \frac{100}{32} \right\rfloor + \left\lfloor \frac{100}{64} \right\rfloor = 50 + 25 + 12 + 6 + 3 + 1 = 97$

So $2^{97} \mid 100!$ but $2^{98} \nmid 100!$.

Application. Number of trailing zeros in $n!$ = $v_5(n!)$ (since $v_2 > v_5$ always, pairs of 2 and 5 form 10s).

Trailing zeros in $100!$: $\lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24$.

---

Hermite's identity

$\lfloor x \rfloor + \lfloor x + \tfrac{1}{n} \rfloor + \lfloor x + \tfrac{2}{n} \rfloor + \cdots + \lfloor x + \tfrac{n-1}{n} \rfloor = \lfloor nx \rfloor$

Proof. Write $x = m + \{x\}$ where $m = \lfloor x \rfloor$. The left side shifts by integers summing to $m \cdot n$ plus contributions from the fractional parts. The fractional part $\{x\}$ falls in exactly one interval $[k/n, (k+1)/n)$, and the identity reduces to a counting argument on the fractional parts. $\blacksquare$

Special case ($n=2$): $\lfloor x \rfloor + \lfloor x + \frac{1}{2} \rfloor = \lfloor 2x \rfloor$.

---

Worked problems

Problem 1. How many integers from 1 to 1000 are divisible by 3 but not by 7?

Divisible by 3: $\lfloor 1000/3 \rfloor = 333$.

Divisible by both 3 and 7 (i.e., by 21): $\lfloor 1000/21 \rfloor = 47$.

Answer: $333 - 47 = 286$.

Problem 2. Find the number of trailing zeros in $50!$.

$\lfloor 50/5 \rfloor + \lfloor 50/25 \rfloor = 10 + 2 = 12$.

Problem 3. Prove: $\lfloor \sqrt{n} \rfloor$ equals the number of perfect squares $\leq n$.

Perfect squares $\leq n$: $1^2, 2^2, \ldots, k^2$ where $k^2 \leq n < (k+1)^2$. So $k = \lfloor \sqrt{n} \rfloor$. $\blacksquare$

Problem 4. Find $\displaystyle\sum_{k=1}^{100} \lfloor \sqrt{k} \rfloor$.

$\lfloor \sqrt{k} \rfloor = m$ when $m^2 \leq k < (m+1)^2$, i.e., for $2m+1$ values of $k$.

$\sum_{k=1}^{100} \lfloor \sqrt{k} \rfloor = \sum_{m=1}^{9} m \cdot (2m+1) + 10 \cdot 1$

(For $m=1$ to $9$: each value holds for $2m+1$ integers. For $m=10$: only $k=100$.)

$= \sum_{m=1}^{9}(2m^2+m) + 10 = 2\cdot\frac{9\cdot10\cdot19}{6} + \frac{9\cdot10}{2} + 10 = 570 + 45 + 10 = 625$.

---

The floor function's most important application in this thread: counting lattice points — integer coordinate points — under curves. That's where divisor counting and hyperbola geometry meet, in Counting Lattice Points.