5
$\begingroup$

Given a fixed real number $k$, I'd like to ask how to calculate the asymptotic behavior of the cardinality of the set $$S_k=\left\{\left\lfloor\frac{N}{i^k}\right\rfloor \ \bigg| \ i \in \mathbb{Z}^+\right\}$$ for sufficiently large $N$, here $\lfloor\cdot\rfloor$ is the floor function.

An example: when $k=1$, it turns out that $|S_k|=\Theta(N^{\frac{1}{2}})$.

It seems that $|S_k|=\Theta(N^{\frac{1}{k+1}})$ asymptotically, but I cannot prove it rigorously.

$\endgroup$

1 Answer 1

1
$\begingroup$

Write $S_k=S_k^-\cup S_k^+$, where $$ S_k^+=\{\lfloor N/i^k\rfloor :i\in [1,N^{1/(k+1)})\cap \mathbb Z\}\\ S_k^-=\{\lfloor N/i^k\rfloor :i\in (N^{1/(k+1)},N^{1/k}]\cap \mathbb Z\} $$

  • Obviously, $|S_k^+|\in O(N^{1/(k+1)})$, since there $\lfloor N^{1/(k+1)}\rfloor$ possibilities for $i$. With some more thought, the values $\lfloor N/i^k\rfloor$ are distinct for distinct $i$, so $|S_k^+|\in \Theta(N^{1/(k+1)})$.

  • Furthermore, $|S_k^-|\in O(N^{1/(k+1)})$, since $S_k^-\subseteq [1,N^{1/(k+1)})\cap \mathbb Z$. You can in fact show the other inclusion by proving that for $i\ge N^{1/(k+1)}$, that $$ \frac{N}{(i+1)^k}\ge \frac{N}{i^k}-1 $$ so that as $i$ increases from $N^{1/(k+1)}$ to $N^{1/k}$, it hits every element of $[1,N^{1/(k+1)})$ in decreasing order.

Combining these gives you want you want.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .