Question 91
For each positive integer $n$ let $f(n)$ be the number of products of integers bigger than $1$ whose result is at most $n$, i.e. $f(n)$ is the number of $k$-tuples $(a_1, a_2, \dots, a_k)$ where $k$ is a natural number, $a_i \ge 2$ is an integer for all $i$ and $a_1 \cdot a_2 \cdot \dots a_k \le n$ (include, by convention, the empty $0$-tuple $(\cdot)$, whose product is $1$).
Thus, for example, $f(1) = 1$ because of the $0$-tuple $(\cdot)$ and $f(6) = 9$, because of the $0$-tuple $(\cdot)$, the $1$-tuples $(2), (3), (4), (5)$ and $(6)$ and the $2$-tuples $(2, 2), (2, 3)$ and $(3, 2)$.
Let $\alpha \gt 1$ such that $\sum_{m=1}^{\infty} \frac{1}{m^{\alpha}} = 2$.
a. Prove that there exists a constant $K \gt 0$ such that $f(n) \le K \cdot n^{\alpha}$ for all positive integers $n$.
b. Prove that there exists a constant $c \gt 0$ such that $f(n) \ge c \cdot n^{\alpha}$ for all positive integers $n$.
Thus, for example, $f(1) = 1$ because of the $0$-tuple $(\cdot)$ and $f(6) = 9$, because of the $0$-tuple $(\cdot)$, the $1$-tuples $(2), (3), (4), (5)$ and $(6)$ and the $2$-tuples $(2, 2), (2, 3)$ and $(3, 2)$.
Let $\alpha \gt 1$ such that $\sum_{m=1}^{\infty} \frac{1}{m^{\alpha}} = 2$.
a. Prove that there exists a constant $K \gt 0$ such that $f(n) \le K \cdot n^{\alpha}$ for all positive integers $n$.
b. Prove that there exists a constant $c \gt 0$ such that $f(n) \ge c \cdot n^{\alpha}$ for all positive integers $n$.