2010:01: Winter Study Conundrum

Let n  be a natural number greater than 1 and suppose n has k distinct prime factors.  Please prove that  log(n)  ≥  k  log(2).

Solution. Congrats to Sean Pegado, the first to submit the following correct solution:

If n = p_1^e_1 * p_2^e_2 * …. * p^e_k, we know that the smallest possible value for p_i will be 2. Since we have distinct prime factors, we can rewrite
n = p_1^e_1 * p_2^e_2 * …. * p^e_k ≥ 2^e_1 * … * 2^e_k = 2^{e_1 + … + e_k}.
Since we have k distinct prime factors, we know that each e_i must be positive, and thus greater than or equal to 1.
n ≥ 2^{e_1 + … + e_k} ≥ 2^{1+…+1} = 2^k.
So n ≥ 2^k, and log(n) ≥ k*log(2).