How many distinct values of floor(N/i) exists for i=1 to N.

Question

Say we have a function $F(i)=\text{floor}(N/i)$.

Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$

e.g. We have $N=25$ then.

$F(1)=25$

$F(2)=12$

$F(3)=8$

$F(4)=6$

$F(5)=5$

...

$F(24)=1$

$F(25)=1$

So total distinct values of $F(i)$ are $(N=25)$ :- $25, 12, 8, 6, 5, 4, 3, 2, 1$

total distinct values are $9$: $(2 \times 5-1)$

Can anyone please help in that total number of distinct values are $O(\sqrt{N})$?

What if $N$ isn't a square? Then the number of distinct values can't be $2\sqrt N-1$, because that isn't a whole number. — John Gowers, Dec 15 '14 at 18:21
Look here: http://math.stackexchange.com/questions/2062/dirichlets-divisor-problem — marty cohen, Dec 15 '14 at 18:24
Are you trying to say that the number of distinct values is $O(\sqrt N)$? Or that it is bounded by $2\sqrt N-1$? — John Gowers, Dec 15 '14 at 18:24
Can you please help me in coming up with some simpler proof. — veer, Dec 15 '14 at 18:24
Sorry. My advice is to look at the various proofs in different number theory books and articles. — marty cohen, Dec 15 '14 at 18:27
I have searched all over the internet but there isn't any thing relevant that could help me in reaching the proof.......i don't want a formal proof even an intutive proof will work — veer, Dec 15 '14 at 18:33

score 12 · Accepted Answer · answered Dec 15 '14 at 18:36

12

If $k \leqslant \sqrt{N}$, then $\lfloor N/\lfloor N/k\rfloor\rfloor = k$, since, letting $m = \lfloor N/k\rfloor$, we have $$mk\leqslant N < (m+1)k = mk + k \leqslant mk + m = m(k+1),$$ so that gives you $\lfloor \sqrt{N}\rfloor$ values. And the values of $\lfloor N/k\rfloor$ for $k \leqslant \lfloor \sqrt{N}\rfloor$ are all different, since

$$\frac{N}{k-1} - \frac{N}{k} = \frac{N}{k(k-1)} > 1$$

for $1 < k \leqslant \lfloor \sqrt{N}\rfloor$.

So you have either $2\lfloor \sqrt{N}\rfloor$ or $2\lfloor\sqrt{N}\rfloor - 1$ distinct values, depending on whether

$$N \geqslant \lfloor \sqrt{N}\rfloor(\lfloor\sqrt{N}\rfloor+1)$$

or not.

answered Dec 15 '14 at 18:36

Daniel Fischer

206,697

Thank You very much Daniel – veer Dec 15 '14 at 18:39
Hi Daniel! I am sorry I may sound dumb, but how does proving $mk < m(k+1)$ prove that $\lfloor N/\lfloor N/k\rfloor\rfloor = k$? – ukh Nov 21 '15 at 08:20
@nitrogen The crucial part is the relation to $N$. We have $mk \leqslant N < m(k+1)$. Dividing by $m$ yields $k \leqslant N/m < k+1$, and that means $k = \lfloor N/m\rfloor$. – Daniel Fischer Nov 21 '15 at 09:14
Thank you very much. Just one more concept I need to understand, to prove all $\lfloor N/k\rfloor$ are distinct for $1 \lt k \leqslant \lfloor \sqrt{N}\rfloor$, it is needed to prove that $\lfloor\frac{N}{k-1}\rfloor - \lfloor \frac{N}{k} \rfloor > 0$, but I don't know why you removed the floor function and computed the difference. Why does that work? – ukh Nov 21 '15 at 11:12
Also, why should the difference be > 1, does not a difference of at least 1 ensure all consecutive floor values are different? – ukh Nov 21 '15 at 11:18
1

@nitrogen Suppose $x \leqslant y$. If $\lfloor x\rfloor = \lfloor y\rfloor = n$, then we have $n \leqslant x < n+1$ and $n \leqslant y < n+1$, hence $y-x < (n+1) - n = 1$. So if the difference between two real numbers is at least $1$ (yes, a difference of exactly $1$ is also sufficient), the two numbers have different floors. Since it's easier to compute with $\frac{N}{k}$ and $\frac{N}{k-1}$ than with $\bigl\lfloor\frac{N}{k}\bigr\rfloor$ and $\bigl\lfloor \frac{N}{k-1}\bigr\rfloor$, when that suffices to show the desired thing, one often drops the floors. – Daniel Fischer Nov 21 '15 at 11:20
Daniel, can you recommend some topics that help me understand such basic things, I don't know what to look for as I am not a maths student. – ukh Nov 21 '15 at 11:23
@nitrogen Sorry, I don't know what to recommend. Except of course practice. And more practice. Apart from that, maybe an introduction to Number Theory (there are lots of good books with approximately that title). – Daniel Fischer Nov 21 '15 at 11:30
Let us continue this discussion in chat. – ukh Nov 21 '15 at 11:34

score 3 · Answer 2 · answered Oct 21 '17 at 13:23

Let $k = \left\lfloor{\frac{N}{i}}\right\rfloor$. Take two cases -

$k \le \sqrt{N}$: Clearly there are $\mathcal{O}(\sqrt{N})$ possible values for $k$ in this case
$k > \sqrt{N}$: In this case $i \le \sqrt{N}$. Since there are $\mathcal{O}(\sqrt{N})$ possible values for $i$, there are $\mathcal{O}(\sqrt{N})$ values for $k$ as well.

$\implies$ the maximum distinct values of $k$ is $\mathcal{O}(\sqrt{N})$

score 0 · Answer 3 · answered Mar 18 '17 at 20:42

Get the ceil() value of the positive root of the equation t^2 + t - (N + 1) = 0. Let's say the required root be r, then compare (r^2 - 1) with N if (r^2 - 1 >= N) the answer will be 2 * ( r - 1) else the answer will be 2 * (r - 1) + 1. Here is cpp psuedo code :

    int n; // get n
    int r = ceil((sqrt(5 + 4 * n) - 1.00) / 2.00);
    if(r * r - 1 >= n)
        return 2 * (r - 1);
    else
        return 2 * (r - 1) + 1;

How many distinct values of floor(N/i) exists for i=1 to N.

3 Answers3