How many different number are there in sequence $⌊n/1\rfloor$, $⌊n/2⌋, ⌊n/3⌋, ..., ⌊n/n]$?

$1 \leq n \leq 10^{12}$ and n is an integer. Through some documents on the internet, I vaguely know that the answer is $\sqrt{n}$ or maybe $2\sqrt{(n)}$. Can anyone help me to prove this? My English is not very good, sorry if it makes you confused.

Solution 1:

The answer is indeed between $\sqrt{n}$ and $2 \sqrt{n}$ (plus-minus some constants, you can figure them out if needed). To understand this, look at $\sqrt{n}$.

• Clearly, there are at most $\sqrt{n}$ values which are less than $\lfloor \sqrt{n} \rfloor = \lfloor \frac{n}{\sqrt{n}} \rfloor \ge \lfloor \frac{n}{\lceil \sqrt{n} \rceil} \rfloor$. I.e., for $k \ge \lceil \sqrt{n} \rceil$, at most $\lfloor \sqrt n \rfloor$ values of $\lfloor \frac nk \rfloor$ are distinct.
• On the other hand, there are at most $\lfloor \sqrt{n} \rfloor$ distinct values $\lfloor \frac n1 \rfloor, \lfloor \frac n2 \rfloor, \ldots, \lfloor \frac{n}{\lfloor \sqrt n \rfloor} \rfloor$. Moreover, all these values are distinct, since for all $i \le \sqrt{n}$: $$\frac{n}{i-1} - \frac{n}{i} = \frac{n (i - (i - 1))}{i(i - 1)} \ge \frac{n}{\sqrt n(\sqrt n - 1)} \ge 1$$

Solution 2:

The answer is

$$\lfloor\frac{-1+\sqrt{1+4n}}{2}\rfloor + \lfloor\frac{n}{\lfloor\frac{-1+\sqrt{1+4n}}{2}\rfloor+1}\rfloor.$$

Set $$S_{n} := \{\lfloor \frac{n}{k}\rfloor: 1 \leq k \leq n, k \in \mathbb{N}\}$$

Clearly each member of $S_{n}$ is an integer and between $1$ and $n$.

Note that if $j \in S_{n}$ then for some $1\leq k_{j} \leq n, k_{j} \in \mathbb{N}$ we have

$$j \leq \frac{n}{k_{j}}<j+1$$

That is

$$\frac{n}{j+1}<k_{j} \leq \frac{n}{j}$$

That is $j \in S_{n}$ iff there is some integer in the interval $I_{n,j}:=(\frac{n}{j+1}, \frac{n}{j}]$. Now when $j(j+1) \leq n$ then $I_{n,j}$ is of length atleast $1$ and hence must contain an integer. Thus if $j \in \mathbb{N}$ and $j(j+1) \leq n$ then $j \in S_{n}$. Let $d_{n}$ be the maximum positive integer for which $d_{n}(d_{n}+1) \leq n$. for each $ d_{n} < v \leq n$ there is atmost one integer in the interval $I_{n,v}$ and if there were an integer it would be in the interval $[1,\frac{n}{d_{n}+1}]$ and clearly each positive integer in this interval is in some $I_{n,p}$ for some $p > d_{n}$.

Hence the total number is $$d_{n}+\lfloor\frac{n}{d_{n}+1}\rfloor$$ where

$$d_{n} = \lfloor\frac{-1+\sqrt{1+4n}}{2}\rfloor$$