Mixing
Is there an intuitive reason why the natural logarithm shows up in the Prime Number Theorem? [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
7
down vote
favorite
This question already has an answer here:
Intuition for the prime number theorem
1 answer
I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.
number-theory prime-numbers
asked Jul 16 at 20:20
Tyler Litch
412
marked as duplicate by Mostafa Ayaz, MathematicsStudent1122, Xander Henderson, Adrian Keister, Trần Thúc Minh Trà Jul 17 at 2:33
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
7
down vote
favorite
This question already has an answer here:
Intuition for the prime number theorem
1 answer
I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.
number-theory prime-numbers
asked Jul 16 at 20:20
Tyler Litch
412
marked as duplicate by Mostafa Ayaz, MathematicsStudent1122, Xander Henderson, Adrian Keister, Trần Thúc Minh Trà Jul 17 at 2:33
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
1
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
This question already has an answer here:
Intuition for the prime number theorem
1 answer
I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.
number-theory prime-numbers
asked Jul 16 at 20:20
Tyler Litch
412
This question already has an answer here:
Intuition for the prime number theorem
1 answer
I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.
This question already has an answer here:
Intuition for the prime number theorem
1 answer
number-theory prime-numbers
asked Jul 16 at 20:20
Tyler Litch
412
edited Jul 18 at 10:46
asked Jul 16 at 20:20
Tyler Litch
412
asked Jul 16 at 20:20
Tyler Litch
412
asked Jul 16 at 20:20
Tyler Litch
412
412
marked as duplicate by Mostafa Ayaz, MathematicsStudent1122, Xander Henderson, Adrian Keister, Trần Thúc Minh Trà Jul 17 at 2:33
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Mostafa Ayaz, MathematicsStudent1122, Xander Henderson, Adrian Keister, Trần Thúc Minh Trà Jul 17 at 2:33
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
1
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28
add a comment |Â
2
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
1
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28
2
2
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
1
1
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
9
down vote
Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $frac1p$, hence the probability that it's not divisible by $p$ is $1 - frac1p$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is
$$prod_p < n left( 1 - frac1p right).$$
So we want to explain why this grows like $frac1ln n$. Well, let's invert it, getting
$$prod_p < n frac11 - frac1p = prod_p < n left( 1 + frac1p + frac1p^2 + dots right).$$
Expanding this out produces a sum over terms of the form $frac1k$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is
$$sum_k < n frac1k sim ln n$$
by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $frac1p$, hence the probability that it's not divisible by $p$ is $1 - frac1p$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is
$$prod_p < n left( 1 - frac1p right).$$
So we want to explain why this grows like $frac1ln n$. Well, let's invert it, getting
$$prod_p < n frac11 - frac1p = prod_p < n left( 1 + frac1p + frac1p^2 + dots right).$$
Expanding this out produces a sum over terms of the form $frac1k$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is
$$sum_k < n frac1k sim ln n$$
by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
add a comment |Â
up vote
9
down vote
Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $frac1p$, hence the probability that it's not divisible by $p$ is $1 - frac1p$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is
$$prod_p < n left( 1 - frac1p right).$$
So we want to explain why this grows like $frac1ln n$. Well, let's invert it, getting
$$prod_p < n frac11 - frac1p = prod_p < n left( 1 + frac1p + frac1p^2 + dots right).$$
Expanding this out produces a sum over terms of the form $frac1k$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is
$$sum_k < n frac1k sim ln n$$
by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
add a comment |Â
up vote
9
down vote
up vote
9
down vote
Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $frac1p$, hence the probability that it's not divisible by $p$ is $1 - frac1p$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is
$$prod_p < n left( 1 - frac1p right).$$
So we want to explain why this grows like $frac1ln n$. Well, let's invert it, getting
$$prod_p < n frac11 - frac1p = prod_p < n left( 1 + frac1p + frac1p^2 + dots right).$$
Expanding this out produces a sum over terms of the form $frac1k$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is
$$sum_k < n frac1k sim ln n$$
by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $frac1p$, hence the probability that it's not divisible by $p$ is $1 - frac1p$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is
$$prod_p < n left( 1 - frac1p right).$$
So we want to explain why this grows like $frac1ln n$. Well, let's invert it, getting
$$prod_p < n frac11 - frac1p = prod_p < n left( 1 + frac1p + frac1p^2 + dots right).$$
Expanding this out produces a sum over terms of the form $frac1k$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is
$$sum_k < n frac1k sim ln n$$
by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
edited Jul 16 at 20:52
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
answered Jul 16 at 20:41
Qiaochu Yuan
269k32564900
269k32564900
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
add a comment |Â
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum?
– Tyler Litch
Jul 17 at 10:52
add a comment |Â
2
One would be surprised by an unnatural logarithm!
– Lord Shark the Unknown
Jul 16 at 20:24
Could you expand "PNT"? What is PNT?
– Rolazaro Azeveires
Jul 16 at 20:26
1
@RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/ln(x)$.
– Arthur
Jul 16 at 20:27
math.stackexchange.com/questions/2144940/…
– Alex R.
Jul 16 at 20:28