3
$\begingroup$

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.

$\endgroup$

2 Answers 2

11
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 27, 2012 at 23:28
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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