My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
numberguru1 is offline  
 
November 6th, 2015, 10:39 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
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.
CRGreathouse is offline  
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.
numberguru1 is offline  
November 6th, 2015, 01:21 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
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 View Post
Thanks for the information though, I had not heard of this theorem before I came to this.
Yes, it's very useful!
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
approximation, counting, function, prime



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
A simple proof of the prime-counting function Rahul k Number Theory 1 May 14th, 2015 06:10 AM
A property of the prime counting function. Jonas Castillo T Number Theory 6 May 9th, 2015 06:26 PM
An equation of prime counting function. jim198810 Number Theory 6 March 26th, 2015 07:31 PM
Question on prime counting function \pi fafa Number Theory 24 June 22nd, 2013 12:55 AM
Lower Bound for the Prime Counting Function guynamedluis Number Theory 2 April 21st, 2012 12:48 PM





Copyright © 2019 My Math Forum. All rights reserved.