Question

Given a number n. Suppose $p_1< p_2<....< p_k$ be any k distinct primes less than n. How do i find the cardinality of the set, S={$(e_1,e_2,...,e_k): p_1^{e_1}p_2^{e_2}...p_k^{e_k} < n$}. Assume that $(1,1,...,1)\in S$ and $e_i\geq 1\;\;\forall i$. It will be great if one could give a non-trivial upper bound for the cardinality of this set.

P.S. I have a way of getting the cardinality of the set approximately for four primes but things get complicated when the number of primes are increased.

Answer 1

Take a logarithm: so the condition is $\sum_{j=1}^ke_j \log p_j < \log n$. Geometrically, it is the number of points of the lattice $\prod_{j=1}^k (\log p_j)\mathbb{Z}$ within the orthogonal simplex with edge $\log n$. This gives lower and upper bounds, and an asymptotics, $$|S_n|=\frac{(\log n)^k}{k!\prod_ {j=1}^k\log p _ j }\big(1+o(1)\big)\ .$$

Answer 2

What I did was the following,

Suppose $p_1p_2.....p_k^{e_k} < n$. Then the maximum value that $e_k$ can take would be $\leq$ $\frac{\log \left(\frac{n}{p_1p_2...p_{k-1}}\right)}{\log p_k}$. Then I tried to find the maximum power $e_{k-1}$ of $p_{k-1}$ for which $p_{k-1}^{e_{k-1}} < {p_k}^{l_1}$, for $1\leq l_1\leq\frac{\log \left(\frac{n}{p_1p_2...p_{k-1}}\right)}{\log p_k}-1=\frac{\log \left(\frac{n}{p_1p_2...p_{k-1}p_k}\right)}{\log p_k}$. Then the maximum value of $e_{k-1}$ would be $\leq l_1\frac{\log p_k}{\log p_{k-1}}$, for $1\leq l_1\leq \frac{\log \left(\frac{n}{p_1p_2...p_{k-1}p_k}\right)}{\log p_k}$. Similarly I proceeded this way for getting the maximum power of $p_{k-2}$ for which $p_{k-2}^{e_{k-2}} < p_{k-1}^{l_2}$, for $1 \leq l_2\leq l_1\frac{\log p_k}{\log p_{k-1}}-1$. And so on. Finally I had to calculate the following sum for getting an upper bound for |S|, $$\sum_{l_1=1}^{\frac{\log \left(\frac{n}{p_1p_2...p_{k-1}p_k}\right)}{\log p_k}}\sum_{l_2=1}^{l_1\frac{\log p_k}{\log p_{k-1}}-1}.....\sum_{l_{k-1}=1}^{l_{k-2}\frac{\log p_3}{\log p_2}-1}l_{k-1}\left(\frac{\log p_2}{\log p_1}\right)$$.

Now these sums are easy to calculate for two, or three primes. Indeed for 4 primes things get complicated. I hope I was going correctly. Infact if I try taking the most trivial upper bound of each sum, considering the upper limit of each sum. Then I find the sum bounded by, $$\frac{\left(\log \left(\frac{n}{p_1p_2...p_{k-1}p_k}\right)\right)^k}{\prod_{j=1}^{k}\log p_j}$$ That's not a good bound since the numerator can be negative sometimes as well. Hopefully absolute value of this fraction would help since i understand why such negative sign might be coming while i calculated the sum exactly for three primes.

@ Pietro: Thanks for your help. It was simple for an upper bound.