Has anyone seen my formula that approximates the number of primes up to n?

133 Views Asked by At

For closed formulas, a formula that approximates the numbers of primes less than or equal to $n$ is $\dfrac{n}{\ln(n)}$.

A formula that gets much closer to the exact values, at least for $n < 3000$, is $\dfrac{n}{\ln(n) - 1}$.

I discovered $\dfrac{n}{\log_{10}(n^2)}$, which gives values many times within 2 of the actual value for $n < 3000$.

Has anyone seen my formula before? (I looked for it on the Internet.)

3

There are 3 best solutions below

7
On

Nice work! Yep, $\frac{n}{\ln n}$ in particular is the prime number theorem. The other two formulas, $\frac{n}{\ln(n) - 1}$ and $\frac{n}{\log_{10}(n^2)}$, look like over-fitting to small values. Note that $\log_{10}(n^2)=2\log_{10}(n)=\frac{2}{\ln 10}\ln(n)\approx 0.868\ln(n)$. So that formula will be off by a constant factor for very large $n$.

0
On

Your approximation is

$\begin{array}\\ \dfrac{n}{\log_{10}(n^2)} &=\dfrac{n}{2\log_{10}n}\\ &=\dfrac{n}{2\ln(n)/\ln(10)}\\ &=\dfrac{\ln 10}{2}\dfrac{n}{\ln(n)}\\ &\approx 1.15\dfrac{n}{\ln(n)}\\ \end{array} $

which is about 15% high for large $n$.

2
On

If you look on Mathworld, you will find some formulas that look a lot like yours. Specifically Equation $1$: $$\pi(n) \sim \frac{n}{\log n + B}$$ with $B = -1.08366$, which, as it turns out, is very close to your $B = -1$ (I like to use "$\log$" instead of $\ln$").

Have you studied calculus, at least cursorily? The prime number theorem is an excellent example of the concept of a limit. With $B = 0$, the formula gets more accurate as $n$ goes to infinity.