The problem:
Estimation of number of distinct integers in the sequence $a_i =\lfloor \frac{n}{n + 1 - i} \rfloor, i\geq 0$ for some given $n$
This problem is derived from a programming problem that I've solved. My algorithm gives $63245$ when $n = 10^9$.
https://codeforces.com/problemset/problem/1263/C
This is the best I've come up so far:
I've tried to evaluate the distance between two consecutive elements in the sequence, namely $a_i$ and $a_{i+1}$.
$$a_{i + 1} - a_i = \lfloor \frac{n}{n - i}\rfloor - \lfloor \frac{n}{n + 1 - i}\rfloor$$. Applying the properties of floor function, we can derive that:
$$\frac{n}{(n - i)(n - i + 1)} - 1\leq a_{i} - a_{i + 1} \leq \frac{n}{(n - i)(n - i + 1)} + 1$$. Roughly speaking, this means that the distance is around $\frac{n}{(n - i)(n - i + 1)}$.
This calculation fits with the sequence generated by my algorithm. $$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 1561, 1562, 1563, 1564, 1565,..., 80372, 80379, 80385, ..., 329924, 330033, 330141, 330250, 330360$$.
As $i$ grows large, the distance grows large quadratically. I'm stuck from here. Any help would be highly appreciated. Thank you for reading :D