1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Difficult number theory problem proofs

  1. Jun 4, 2015 #1
    The following is a repost from 2008 from someone else as there was no solution offered or provided I thought id post one here
    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<4^n

    - An mathematically rigourous proof of this would take a long time but I would suggest the following outline which is logically correct I believe:

    First we need to consider a lowest bound value of n and for that purpose is can be stated as pt above

    so we want to show that p1*p2*p3...*pt < 4^pt

    consider the natural log of both sides
    log (p1*p2...) = log(4^pt)
    consider the left hand side
    log(p1*p2*p3...) = log p1+ logp2 + log p3 ...

    Now consider the prime number theorem which can be restated such that:
    logp1+logp2+logp3...+logpt ~ pt

    another way to think about using a well known restatement of the prime number theorem is that the density of primes at any point n (ie the approximate prime gap) is approximately equal to log n.

    eg logp1 is ~ the gap between p1 and p2
    log22 is ~ the gap between p2 and p3 and so on

    therefore is you sum up all the gaps between the first n primes the sum will be (approx.) the value of the nth prime pn.
    Therefore the Left hand side = pt (approx within the order +/- 1% for large p)
    Now the right hand side log(4^pt) = pt* log 4 = 1.386 * pt
    Therefore this proves the original statement since pt < 1.386 * pt

    Any comments would be welcome

    Last edited by a moderator: Jun 4, 2015
  2. jcsd
  3. Jun 4, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    (I removed the boldface and moved the thread to the homework section)

    That approach suggests that the inequality is true for large numbers, but it is not a mathematical proof. Note that locally the ratio between the two sides can decrease, e.g. between 101 and 103 (both are prime, and 103 > 16).
    You'll need some upper limit on the density of primes, probably together with a manual check of the smaller numbers (this part is unproblematic).
  4. Jun 4, 2015 #3
    Hello and thanks for that. I know that it's not a a proof but I think it provides a framework to achieve one. In any event it's nothing of any value. I agree with your suggestions however. I guess I was trying to find some proveable number theory problems and found this one. I suspect without basis that many prime number conjectures are true but not proveable. If you have any difficult but proveable suggestions I'd like to hear them.
    Many thanks for replying it's my first day here and it's good to get feedback.
  5. Jun 5, 2015 #4


    User Avatar
    2017 Award

    Staff: Mentor

    I'm sure it is possible to prove that inequality.

    I would expect the same inequality to hold for 3n.
    I guess for every number w>e there are at most a finite set of elements where the product exceeds wn. Which also means there is (a) no product of primes that exceeds en or (b) there is a largest w>e where the inequality is violated somewhere.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted