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...