MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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)\, .$$

share|cite|improve this answer
And because you insist that each $e_i\ge1$, I believe that $(\log n)^k/k!\prod_{j=1}^k \log p_j$ is an actual upper bound for $\#S$. – Greg Martin Oct 27 '12 at 23:28

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.