Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Really hard number theory problem

  1. Oct 14, 2008 #1
    1. The problem statement, all variables and given/known data

    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 p1,p2,...,pt be the primes not exceeding n.

    show that p1p2...pt<4n

    3. The attempt at a solution

    I really dont know where to start here.

    just throwing this out there, im guessing they got 4k by having the sum of something like 2k+1 choose k but thats just a complete guess.
  2. jcsd
  3. Oct 15, 2008 #2
    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.
  4. Oct 15, 2008 #3


    User Avatar
    Science Advisor

    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 42= 16. If n= 3, then "the primes not exceeding 3" are 2 and 3 so the product is 6: 6< 43= 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 4k which is itself less than 4k+1. If k+1 is a prime what happens?
  5. Oct 15, 2008 #4
    If k+1 is prime then k is divisible by two. can you factor out a two or soemthing?
  6. Oct 15, 2008 #5


    Staff: Mentor

    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, [tex]\pi[/tex](n).

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

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

    Maybe this is helpful, maybe not.
  7. Oct 16, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    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.
    Last edited: Oct 16, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook