 My Math Forum Approximation for the Prime Counting Function
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 November 6th, 2015, 10:08 AM #1 Member   Joined: Jun 2015 From: Ohio Posts: 99 Thanks: 19 Approximation for the Prime Counting Function I was playing around with some of my sieve work and I came up with this interesting way to approximate the prime counting function (at least for small values, haven't tested larger ones). I wanted to throw it out here to see what you guys think of it compared to other known methods. Say you want to find the number of primes less than some number, 3721 for example. First, take the square root of the number sqrt(3721) = 61 Now take the product of (p - 1)/p for all primes from 3 up to 61 60/61 * 58/59 * 52/53 * ... * 2/3 Subtract 1 from the original number, divide it by 2, then multiply it by that product. (3721 - 1)(60/61 * 58/59 * 52/53 * 46/47 ... * 2/3)/2 You get about 490 compared to an actual answer of 519. As far as I know, the accuracy increases with larger numbers. November 6th, 2015, 10:39 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by numberguru1 I was playing around with some of my sieve work and I came up with this interesting way to approximate the prime counting function (at least for small values, haven't tested larger ones). I wanted to throw it out here to see what you guys think of it compared to other known methods. Say you want to find the number of primes less than some number, 3721 for example. First, take the square root of the number sqrt(3721) = 61 Now take the product of (p - 1)/p for all primes from 3 up to 61 60/61 * 58/59 * 52/53 * ... * 2/3 Subtract 1 from the original number, divide it by 2, then multiply it by that product. (3721 - 1)(60/61 * 58/59 * 52/53 * 46/47 ... * 2/3)/2 You get about 490 compared to an actual answer of 519. As far as I know, the accuracy increases with larger numbers.
$$\pi_\text{approx}(x) := \frac{x-1}{2}\prod_{p\le\sqrt x}\frac{p-1}{p}$$

By Mertens' theorem,
$$\prod_{p\le x}\frac{p-1}{p} \approx \frac{e^{-\gamma}}{\log x}$$

and so
$$\pi_\text{approx}(x) \approx \frac{x-1}{2}\frac{e^{-\gamma}}{\log\sqrt x} \approx \frac{1}{e^{\gamma}}\frac{x}{\log x} = 0.561459\ldots\frac{x}{\log x}.$$

But this doesn't match your numbers: it gives $\pi_\text{approx}(3721)=244.752\ldots,$ as you can verify with this GP script:
Code:
piapprox(x)=(x-1)/2*prodeuler(p=2,sqrt(x),1-1/p)
piapprox(3721)

Last edited by CRGreathouse; November 6th, 2015 at 10:46 AM. November 6th, 2015, 11:39 AM #3 Member   Joined: Jun 2015 From: Ohio Posts: 99 Thanks: 19 You divided by an extra 2 I believe. My exact answer is exactly double that. I only divide by primes 3 to 61, not 2 to 61 so I think that is the issue. Thanks for the information though, I had not heard of this theorem before I came to this. November 6th, 2015, 01:21 PM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by numberguru1 You divided by an extra 2 I believe. My exact answer is exactly double that. I only divide by primes 3 to 61, not 2 to 61 so I think that is the issue.
Ah yes, I missed that. So your approximation is $\frac{2}{e^\gamma}x\log x$ which is off by a factor of, well, $e^\gamma/2$ in the limit.

Quote:
 Originally Posted by numberguru1 Thanks for the information though, I had not heard of this theorem before I came to this.
Yes, it's very useful! Tags approximation, counting, function, prime Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Rahul k Number Theory 1 May 14th, 2015 06:10 AM Jonas Castillo T Number Theory 6 May 9th, 2015 06:26 PM jim198810 Number Theory 6 March 26th, 2015 07:31 PM fafa Number Theory 24 June 22nd, 2013 12:55 AM guynamedluis Number Theory 2 April 21st, 2012 12:48 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      