From: victor@ccr-p.ida.org (Victor Miller) Newsgroups: sci.math Subject: Re: ln(2)+ln(3)+ln(5)+ln(7)+...+ln(p) Date: 21 Jan 1995 17:43:46 GMT >>>>> "John" == John P Lawrence writes: In article <3fjtqf$id9@biostat.mps.ohio-state.edu> jpl@stat.mps.ohio-state.edu (John P Lawrence) writes: John> In article <3fhmbf$186@martha.utk.edu>, Chris Caldwell John> wrote: > I am looking for a pratical, accurate approximation of > > ln(p#) = ln(2)+ln(3)+...+ln(p) > > (where the sum is taken over the primes <= p). My values of p are > about 10^10. Any suggestion? John> Have you tried log(p#)=log(p!) and using stirling's John> approximation for p! ? John> John This is essentially Chebyshev's function. It is the easiest function to work with to prove the Prime Number Theorem. It is asympotic to p. For a practical approximation, you should look in a famous paper by Rosser and Schoenfeld in the Illinois J. of Math about 1959 (I think). It's concerned with exactly those kinds of questions. If p was REALLY big (10^10, believe it or not, isn't these days) the best way to get good approximations is to relate this value to a sum of zeroes of the Riemann Zeta function. This is rather technical. You might look in Alexander Ivic book, the "Riemann Zeta Function". -- Victor S. Miller | " ... Meanwhile, those of us who can compute victor@ccr-p.ida.org | can hardly be expected to keep writing papers CCR, Princeton, NJ 08540 | saying 'I can do the following useless | calculation in 2 seconds', and indeed what | editor would publish them?" -- Oliver Atkin ============================================================================== From: robert@cs.caltech.edu (Robert J. Harley) Newsgroups: sci.math Subject: Re: ln(2)+ln(3)+ln(5)+ln(7)+...+ln(p) Date: 20 Jan 1995 14:44:37 GMT caldwell@unix1.utm.edu (Chris Caldwell) writes: >I am looking for a pratical, accurate approximation of > > ln(p#) = ln(2)+ln(3)+...+ln(p) > >(where the sum is taken over the primes <= p). My values >of p are about 10^10. Any suggestion? How accurate do you need? You could use ln(p#) ~ p. Let q denote primes and pi() the prime counting function: ln(p#) = SUM_{q <= p} ln(q) <= SUM_{q <= p} ln(p) = pi(p).ln(p) ~= p since pi(x) ~ x/ln(x) Conversely, fix c >= 1: ln(p#) = SUM_{q <= p} ln(q) >= SUM_{p/c < q <= p} ln(q) >= SUM_{p/c < q <= p} ln(p/c) = (pi(p)-pi(p/c)).ln(p/c) ~ (p/ln(p)-p/(c.ln(p/c))).ln(p/c) = p(1-ln(c)/ln(p)-1/c) ~ p(1-1/c) And c can be chosen arbitrarily large. The approximation ln(p#) ~ p is not too bad even for "small" p. From numerical tests, it seems that p-sqrt(p) may be a better approximation: p = ln(p#) ~= p-sqrt(p) ~= ------------------------------------------------------------ 11 7.745003 7.683375 101 88.343511 90.950124 1009 963.161980 977.235240 10007 9905.202419 9906.965006 100003 99696.902224 99686.767491 1000003 998497.990539 999002.998500 10000019 9995195.435954 9996856.719336 100000007 99987748.438694 99990006.999650 1000000007 999968999.301105 999968384.223288 10000000019 ? 9999900018.999905 If you want an effective upper bound: ln(p#) < p*ln(4). Bye, Rob. .-. robert@vlsi.cs.caltech.edu .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Question all you are. `-'