Suppose there is a function $f(x)$ which is the "probability" that the integer $x$ is prime. The integer $x$ is prime with probability $f(x)$, and then divides the larger integers with probability $1/x$; so as $x$ changes from $x$ to $x+1$, $f(x)$ changes to (roughly)
$$f(x)\left(1-f(x)/{x} \right).$$
How do I show that? I can go on to show
$$\frac{df}{dx} + \frac{f^2}{x}=0$$
and thus $\frac{1}{\log{x}} + c$ is solution but I can't show that step on how $f(x)$ changes. please advise
Best Answer
First of all, I assume you understand that this is meant to be a nonrigorous argument, so there will be a limit to how rigorous I can make my answer.
The intuition here is that $n$ is prime if and only if it is not divisible by any prime $<n$. So we "should" have $$f(n) \approx \prod_{p < n} \left( 1-1/p \right).$$ Similarly $$f(n+1) \approx \prod_{p<n+1} \left( 1-1/p \right) = \prod_{p < n} \left( 1-1/p \right) \cdot \left\{ \begin{matrix} \left( 1-1/n \right) \ \mbox{if}\ n\ \mbox{is prime} \\ 1 \ \mbox{if}\ n\ \mbox{is not prime} \end{matrix} \right.$$ $$\approx f(n) \cdot \left\{ \begin{matrix} \left( 1-1/n \right) \ \mbox{if}\ n\ \mbox{is prime} \\ 1 \ \mbox{if}\ n\ \mbox{is not prime} \end{matrix} \right. .$$ Since $n$ is prime with "probability $f(n)$", we interpolate between the two cases next to the brace by writing: $$f(n+1) \approx f(n) \left( 1-f(n)/n \right).$$ One might argue that it would be better to interpolate with a factor of $(1-1/n)^{f(n)}$, but this will make no difference in the asymptopics as $(1-1/n)^{f(n)} = 1-f(n)/n+O(1/n^2)$.
This argument is famously fishy, because it gives the right answer, but the intermediate point is wrong! The actual asymptopics of $\prod_{p<n} \left( 1-1/p \right)$ do not look like $1/\log n$, but like $e^{-\gamma} /\log n$. I've never seen a good intuitive explanation for why we get the wrong estimate for $\prod_{p<n} \left( 1-1/p \right)$, but the right estimate for the density of the primes.