19
$\begingroup$

Is there any way or function to find out the number of primes numbers up to any number? (Say $10^7$ or $10^{30}$ or $200$ or $300$?)

$\endgroup$
  • 1
    $\begingroup$ I really do not understand your question. Please rephrase it and give an example of what you want? From what I understand, you are searching for a way to find a interval of N numbers out of which none is prime? $\endgroup$ – CBenni Dec 24 '12 at 11:52
  • 2
    $\begingroup$ I think you're looking for this en.wikipedia.org/wiki/Prime-counting_function. There is no known expicit formula for this, but we do how this function behaves asymptotically, that is the famous prime-number theorem en.wikipedia.org/wiki/Prime_number_theorem $\endgroup$ – Mohan Dec 24 '12 at 11:54
  • 2
    $\begingroup$ Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;) $\endgroup$ – CBenni Dec 24 '12 at 11:55
18
$\begingroup$

$$\pi(n) \approx \frac{n}{\ln(n)}$$

where $\pi(n)$ is the number of primes less than $n$ and $\ln(n)$ is the natural logarithm of $n$. (Googling 'Prime Number Theorem' will tell you more! But this seems particularly nice for a one-page intro: http://primes.utm.edu/howmany.shtml#pnt )

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So no one till date found out the number of primes less than $n$ can be found out by using square root of $n$ too? and using some other numbers.. $\endgroup$ – Shan Dec 24 '12 at 12:32
  • $\begingroup$ @Shan Short answer: no! $\endgroup$ – Peter Smith Dec 24 '12 at 12:58
  • $\begingroup$ So let me get this straight: If I want to find the number or primes smaller than, say 10^100 - I'd have to first create a list of all primes smaller than 10^10, and then for every number (10^10,10^100) check them mod everything in said list (or against every member > sqrt(n) in that list)? $\endgroup$ – Christofer Ohlsson Jun 12 '15 at 11:09
8
$\begingroup$

The answers above are very correct and state the Prime Number Theorem. Note that below, $\pi(n)$ means the primes less than or equal to $n$. Pafnuty Chebyshev has shown that if $$\lim_{n \to \infty} {\pi(n) \over {n \over \ln(n)}}$$exists, it is $1$. There are a lot of values that are approximately equal to $\pi(n)$ actually, as shown in the table.

enter image description here

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

One of the closest approximations to $\pi(x)$ is the log-integral, $\mathrm{Li}(x)$. The asymptotic expansion is easy to derive using integration by parts: $$ \begin{align} \mathrm{Li}(x) &=\int_2^n\frac{\mathrm{d}t}{\log(t)}\\ &=\frac{n}{\log(n)}+C_1+\int_2^n\frac{\mathrm{d}t}{\log(t)^2}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+C_2+\int_2^n\frac{\mathrm{2\,d}t}{\log(t)^3}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+\frac{2n}{\log(n)^3}+C_3+\int_2^n\frac{\mathrm{3!\,d}t}{\log(t)^4}\\ &=\frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\frac2{\log(n)^2}+\dots+\frac{k!}{\log(n)^k}+O\left(\frac1{\log(n)^{k+1}}\right)\right) \end{align} $$ Thus, using the first two terms in the asymptotic series, $$ \begin{align} \frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\dots\right) &=\frac{n}{\log(n)\left(1-\frac1{\log(n)}+\dots\right)}\\ &\approx\frac{n}{\log(n)-1} \end{align} $$ Therefore, $\dfrac{n}{\log(n)-1}$ is a better approximation than $\dfrac{n}{\log(n)}$ for large $n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why none of these give exact values for $π(x)$ ? $\endgroup$ – Shan Dec 26 '12 at 5:07
  • $\begingroup$ For one, $\pi(x)$ is a discrete function, taking only integer values, whereas $\mathrm{Li}(x)$ is continuous. Similarly, primes clump in certain places; however, $\frac{\mathrm{d}}{\mathrm{d}x}\mathrm{Li}(x)=\frac1{\log(x)}$ is monotonically decreasing. $\endgroup$ – robjohn Dec 26 '12 at 13:30
  • $\begingroup$ @robjohn $\pi(x)$ is continuous also :p. $\endgroup$ – YoTengoUnLCD Oct 3 '16 at 2:25
5
$\begingroup$

There is no known expicit formula for this, but we do know how this function behaves asymptotically, that is the famous prime-number theorem. It states that $$ \pi(n) \approx n/ln(n)$$

But there are certain algorithms for calculating this function. One such example is here Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ There is a lot of variation in what counts as an "explicit formula"; a number of them can be seen at wolfram alpha. Of course, algorithms are usually much better than explicit formulas for actually calculating numerical values. $\endgroup$ – user14972 Dec 24 '12 at 13:16
0
$\begingroup$

let

f(x)={ 2x+1 x∈ N }

f(x) contains all positive odd numbers some of them are prime some are composite

now if f(x) is composite as it is odd its factors must be odd means f(x)=f(m)f(n) where m,n∈ N

2x+1=(2m+1)(2n+1)

2x+1=4mn+2m+2n+1

Means x=2mn+m+n

that means if x is of form 2mn+m+n then f(x) will give composite numbers otherwise prime no. so reduce the domain of f(x) from N to N-A where A is set of all no. that can be represented as 2mn+m+n then we will get prime here A can be calculated easily

For example if m=1 n=1

Then 2mn+m+n that is 2(1)(1)+1+1=4

So for f(4)=9 which is composite

But f(1)=3

f(2)=5

f(3)=7

f(5)=11 which are all primes

So for set A given below function f would take composite values and for set N-A which is set of natural no. - set A function f will give all prime values

A∈{4,7,10,12,13,16,17,19,22,24,25,27,28,31,32,34,37,38,40,42,43,45,46,47,49,52,55,57,58,59,60,61,62,64,66,67,70……………………..} so to verify it f(7)=15

f(10)=21

f(45)=91

so N-A∈ {1,2,3,5,6,8,9,11,14,15,18,20,21,23,26,29,33,35,36,39,41,44,48,50,51,53,54,56,63,65,68,69…………………………} again to verify this f(6)=13

f(8)=17

f(9)=19

f(63)=127

f(69)=139 which are all prime

for x∈ N-A range of f(x) will be same as set of prime no.f:(N-A)→p

p∈ {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79………………

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

There is an exact formula, but it requires an enormous amount of computer processing power for large values of $n$.

Starting from the prime indicator function (1 if $n$ is prime, 0 otherwise for integer $n$), which is given by the power series:

$$-8\sum _{h=1}^{\infty} n^{2h}\sum _{i=1}^h \log\zeta(2i)\sum _{v=i}^{h}\frac{(-1)^{h-v}(4\pi )^{2h-2v}}{\zeta(2v-2i)(2h+2-2v)!}$$

the prime counting function, $\pi(x)$, can then be easily derived by summing up the above function over $n$.

$$\pi(x)=-8\sum _{h=1}^{\infty} H_{-2h}(x)\sum _{i=1}^h \log\zeta(2i)\sum _{v=i}^{h}\frac{(-1)^{h-v}(4\pi )^{2h-2v}}{\zeta(2v-2i)(2h+2-2v)!}$$

where $H_{-2h}(x)$ is given by Faulhaber's formulas (not ugly at all, compared to other formulas out there.)

How do you prove the above prime indicator formula? That is the product of two functions, Moebius' $\mu(n)$ and an adjusted Von Mangoldt function, $\Lambda(n)/\log{n}$ (which yields 1/k at the prime powers, $p^k$, otherwise it yields 0, if $n$ is integer), which means $-\mu(n)\Lambda(n)/\log{n}$ is 1 at the primes and 0 otherwise.

Per a theorem known as The inversion formula for Dirichlet series, both these functions can be expressed as a function of the zeta function, and their product results in the function above.

But, there is a trade-off between exactness and computing easiness, the more you have of one the less you have of the other, hence the approximation formulas are more useful for large values.

Reference An exact formula for the prime counting function

I've added a Mathematica formula for the prime indicator function, the reader can test it with values up to 6 ($n=1,...6$), if they have Mathematica. It will be 1 for integer $n$ prime, and 0 otherwise. (If you want to test higher values, T has to be increased.)

$MaxExtraPrecision = 200; T = 110; n = 6; 
  N[-8*Sum[
   n^(2*h)*Sum[
     Log[Zeta[2*i]]*
      Sum[((-1)^(h - v)*(4*Pi)^(2*h - 2*v))/(Zeta[
           2*v - 2*i]*(2*h + 2 - 2*v)!), {v, i, h}], {i, 1, h}], {h, 
    1, T}], 5]
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Hi, as it is your paper doesn't fit the standards, I opened a discussion to show why and give you the opportunity to simplify your formula (and its derivation) $\endgroup$ – reuns Jan 1 at 4:12
  • 1
    $\begingroup$ I gave a two line proof of your formula... The problem is that you don't have the experience about proofs and proof writing (I do because I am on math forums since more than 3 years) math.stackexchange.com/users/276986/reuns?tab=answers $\endgroup$ – reuns Jan 1 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.