0
$\begingroup$

I am doing some revision, and during an analysis for equality of bit-strings the following lemma is being used -

The number of distinct prime divisors of any number less than $2^n$ is at most n.

Why is this true? I have looked around, but most places seem to come to tighter bounds.

EDIT: I some formatting was wrong as i posted the lemma. The exact quote for the lemma is

Lemma 7.4: The number of distinct prime divisors of any number less than $2^n$ is at most n.

And is from page 168 in "Randomized Algorithms" by Motwani and Raghavan.

$\endgroup$
4
  • $\begingroup$ This is not clear. Did you really mean "any number less than $2$"? And what is $n$ meant to be? If $n$ is the number, then it is clear that there can't be more than $n$ distinct primes dividing it. Was that what you were asking? $\endgroup$
    – lulu
    Jun 15, 2019 at 19:41
  • 1
    $\begingroup$ Whatever bound it is that you have in mind, keep in mind that it would suffice to prove a tighter one. $\endgroup$
    – lulu
    Jun 15, 2019 at 19:42
  • $\begingroup$ Edited the post. Wrong formatting. My apologies. @lulu $\endgroup$
    – user488081
    Jun 15, 2019 at 19:51
  • 1
    $\begingroup$ It is easy to prove, because each of the $n$ primes is $\ge 2$ so a product of $n$ of them is $\ge 2^n$. It is also easy to prove rather tighter bounds if you need them, because the product of three primes is at least $30$, for example, rather than $8$. $\endgroup$
    – Mark Bennet
    Jun 15, 2019 at 19:55

3 Answers 3

Reset to default
2
$\begingroup$

Let $k$ be a number with $n$ distinct prime divisors. Then we have $$ k=p_1\cdots p_n\ge p_1\cdots p_1=p_1^n=2^n, $$ where $p_i$ is the $i$-th prime number. It follows since $p_1<p_i$ for all $i\ge 2$.

$\endgroup$
0
0
$\begingroup$

Hint. Can you find a useful inequality for the product of $n$ distinct primes?

$\endgroup$
0
$\begingroup$

Because 2 is the lowest prime, it follows $2^n$ is the first time a number with prime factors, can have n counted with multiplicities. You can get better bounds. But, this is a greatest lower bound of possibility for n. By Bertrands postulate,it is certain to occur by $2^{{n^2+n\over 2}}$ without multiplicities required.

$\endgroup$

You must log in to answer this question.