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$
  • $\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 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 at 19:42
  • $\begingroup$ Edited the post. Wrong formatting. My apologies. @lulu $\endgroup$ – sn3jd3r Jun 15 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 at 19:55
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$
  • 1
    $\begingroup$ @Travis Ah, thank you! $\endgroup$ – Dietrich Burde Jun 16 at 11:37
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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