Really hard number theory problem

[SNOOTCHIEBOOCHEE]

Homework Statement

neither my professor nor my TA could figure this out. so they are offering fat extra credit for the following problem

Let n be a positive integer greater than 1 and let p₁,p₂,...,p_t be the primes not exceeding n.

show that p₁p₂...p_t<4ⁿ

The Attempt at a Solution

I really don't know where to start here.

just throwing this out there, I am guessing they got 4^k by having the sum of something like 2k+1 choose k but that's just a complete guess.

 

[rmcdra]

The number of primes not exceeding n? So wouldn't that mean that t=n-1 or do you mean that one of numbers in the p sequence need to be less than n? Either one I think will help you. I would recommend trying to prove this by induction. Let Base be 2. Then in Hypothesis let n = k and prove for k+1 using base and your hypothesis.

 

[HallsofIvy]

I am going to assume that "the primes not exceeding n." means all primes less than or equal to n, not "less than or equal to n" many primes. If n= 2, "the primes not exceeding 2" are just 2 itself. 2 is less than or equal to 4²= 16. If n= 3, then "the primes not exceeding 3" are 2 and 3 so the product is 6: 6< 4³= 64. Now suppose that the statement is true for some k greater than or equal 3. Either k+1 is a prime itself, or it is not. If it is not, then "the primes less than or equal to k+1" is exactly the same as "the primes less than or equal to k". In that case, the induction step is easy: the product of primes is less than or equal to 4^k which is itself less than 4^k+1. If k+1 is a prime what happens?

 

[SNOOTCHIEBOOCHEE]

If k+1 is prime then k is divisible by two. can you factor out a two or soemthing?

 

[Mark44]

This problem intrigued me, and I have managed to spend maybe a couple of hours on it, so far without success. My attempt so far involves an induction argument.

Something that might be relevant is the Prime Factorization Theorem, that involves the number of primes less than or equal to a number n, \pi(n).

It says
<br /> lim \pi (n) (ln n)/n = 1, as n grows w/o bound.<br />

This means that
\pi (n) \approx n/(ln n), for large n.

Maybe this is helpful, maybe not.
Mark

 

[Dick]

I really don't think you can get away without considering the distribution of primes. The product of the primes less than n, P(n) can stay constant for a long time and then jump up by a factor much larger than 4. I don't think induction can work. Go with Mark's research. The density of primes around the integer k is 1/ln(k). The log of a prime around k is ln(k). So we can appoximate the log of the product of all of them by integrating ln(k)*1/ln(k) between 1 and n. Which is n. So the product of all the primes less than n is VERY approximately e^n. That's definitely less than 4^n. In fact, I think it's less than 3^n. But you should check low lying cases.