1. Not finding help here? Sign up for a free 30min 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!

Primorial: asymptotics and bounds

  1. Sep 14, 2006 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I was wondering if anyone knew of good approximations of the primorial function for large numbers, or of reasonable bounds for it. By primorial I mean:

    [tex]n\#=\prod_{p\le n}p[/tex] for p prime.

    All I know is [tex]n\#\sim e^n[/tex] and the trivial [tex]\pi(n)!\le n\#\le n![/tex].

    For small numbers (n < 1,000,000,000), e^n is larger than n#. Does this hold generally?

    Obviously, the crude upper limit can be hacked slightly: take out the evens from the factorial and multiply by 2, take out the multiples of 3 and divide by 3, etc. In the extreme case this is just calculating the primorial itself, so not very useful. The lower bound can be improved to

    [tex]p_n\#\le n!\prod^n_{k=5}\ln k+\ln\ln k-1[/tex]

    using lower bounds on the primes, but this is unwieldy, and I'm pretty sure [tex]\lim_{n\rightarrow\infty}\frac{p_n\#}{n!\Pi}=0[/tex] where the product is as above. Using the best bounds out there (by Dusart) improves the result slightly at the cost of complicating it further.
     
    Last edited: Sep 14, 2006
  2. jcsd
  3. Sep 15, 2006 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Well, I did some 'research' online:

    Chris Caldwell's page says that [tex]n\#\sim e^n[/tex] is equivilent to the PNT. I knew the formula already, but at least this gives me a different way of thinking about it.

    I found the asymptotic expression [tex]\exp((1 + o(1))\cdot n\cdot\log(n))=n^n(1+o(1))^{n\log(n)}[/tex] on Sloane's OEIS. This is larger than e^n, which already appears to be an upper bound... any ideas about this?
     
    Last edited: Sep 15, 2006
  4. Sep 16, 2006 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I forgot that Pierre Dusart worked on this already. He shows that [tex]\vartheta(x)<x[/tex] for x < 10^{11} (100 billion, better than I was able to calculate by a factor of 50) and gives some explicit bounds.
     
  5. Sep 16, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    This isn't true though. if n#~e^n then n#/e^n->1, which means log n#-n->0, i.e. [tex]\vartheta(n)-n\rightarrow 0[/tex]. This is false, the difference gets arbitrarily large.

    What is true is log(n#)~n is equivalent to the prime number theorem.

    That asymptotic from Sloanes appears to be for a(n), the nth primorial, a(1)=1,a(2)=2,a(3)=6,a(4)=30 etc. I don't believe this asymptotic for the same reasons, unless I misunderstand what they mean.
     
  6. Sep 16, 2006 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    :blushing: Sorry, I've been converting between the two much too readily. This is the second mistake I've made between theta and # in as many days (the last was writing one for the other!).

    I don't trust it. I can get the upper bound

    [tex]x\#<x^{\frac{x}{\ln x-1.1}}[/tex] for x >= 4

    from Dusart's bounds on primes and the trivial observation that [tex]\vartheta(x)\le\pi(x)\ln x[/tex].
     
  7. Sep 16, 2006 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I'd be lying if I said I've never made this mistake myself.


    It looks fine if you take logs, log a(n)~n*log(n). Remember a(n)=p(n)#, where p(n) is the nth prime and p(n)~nlog(n).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primorial: asymptotics and bounds
  1. Primorial, (n#) (Replies: 3)

  2. Bounded Operators (Replies: 3)

Loading...