show/hide this revision's text 3 corrected typo

I'm not an expert in this area, but this may be a start.

Rather than $\prod_{p\lt n}$, you can use $\prod_{p\le \sqrt n}$.

$\log\log \sqrt n + \gamma \lt \log\log \sqrt n +\log 2 = \log\log n $

That gets you a little closer, since now you are off by $\log 2 - \gamma \approx 0.116$.

The heuristic probability that $n$ is prime is not

$$\prod_{p\lt n} (1-Pr(p|n))$$

It is the product of probabilities

$$\prod_{p\lt n} (1-Pr(p|n \text{ given no smaller prime divides } n))$$

For $p$ small, the term you get may be close to $(1-1/p)$, but I that's not the case for $p$ large.

For $\sqrt n \lt p$, the term corresponding to $p$ in the product is just $1$.

For $\sqrt[3]n \lt p \le \sqrt n$, if $p$ is the smallest prime dividing $n$, then $n/p$ must be prime, too. Perhaps that means that by strong induction, we should discount these terms by the probability $n/p$ is prime, about $\log 1/\log \frac np$, so that those terms in the product are $(1-1/(p \log \frac np))$.

It looks to me like you get some sums/integrals if you try to extend this to more terms, and I don't know whether you can expect to get the desired accuracy at the end.
show/hide this revision's text 2 Deleted incorrect line. Improved text.

I'm not an expert in this area, but this may be a start.

Rather than $\prod_{p\lt n}$, you can use $\prod_{p\le \sqrt n}$.

$\log\log \sqrt n + \gamma \lt \log\log \sqrt n +\log 2 = \log\log n $

That gets you a little closer, since now you are off by $\log 2 - \gamma \approx 0.116$.

The heuristic probability that $n$ is prime is not

$$\prod_{p\lt n} (1-Pr(p|n))$$

It is the product of probabilities

$$\prod_{p\lt n} (1-Pr(p|n \text{ given no smaller prime divides } n))$$

$$= \prod_{p\lt n} Pr(p \text{ is not the smallest prime factor of } n)$$

For $p \le \sqrt[k]n$, there is the possibility that $n$ is the product of $k$ primes, the smallest of which is $p$. For $p$ small, the term you get may be close to $(1-1/p)$, but I believe that's not the case for $p$ large.

For $\sqrt[3]n \sqrt n \lt p$, the term corresponding to $p$ in the product is just $1$.

For $\sqrt[3]n \lt p \le \sqrt n$, if $p$ is the smallest prime dividing $n$, then $n/p$ must be prime, too. Perhaps that means that by strong induction, we should discount these terms by the probability $n/p$ is prime, about $\log \frac np$, so that those terms in the product are $(1-1/(p \log \frac np))$.

It looks to me like you get some sums/integrals if you try to extend this to more terms, and I don't know whether you can expect to get the desired accuracy at the end.
show/hide this revision's text 1

I'm not an expert in this area, but this may be a start.

Rather than $\prod_{p\lt n}$, you can use $\prod_{p\le \sqrt n}$.

$\log\log \sqrt n + \gamma \lt \log\log \sqrt n +\log 2 = \log\log n $

That gets you a little closer, since now you are off by $\log 2 - \gamma \approx 0.116$.

The probability that $n$ is prime is not

$$\prod_{p\lt n} (1-Pr(p|n))$$

It is the product of probabilities

$$\prod_{p\lt n} (1-Pr(p|n \text{ given no smaller prime divides } n))$$

$$= \prod_{p\lt n} Pr(p \text{ is not the smallest prime factor of } n)$$

For $p \le \sqrt[k]n$, there is the possibility that $n$ is the product of $k$ primes, the smallest of which is $p$. For $p$ small, the term you get may be close to $(1-1/p)$, but I believe that's not the case for $p$ large.

For $\sqrt[3]n \lt p$, if $p$ is the smallest prime dividing $n$, then $n/p$ must be prime, too. Perhaps that means that by strong induction, we should discount these terms by the probability $n/p$ is prime, about $\log \frac np$, so that those terms in the product are $(1-1/(p \log \frac np))$. It looks to me like you get some sums/integrals if you try to extend this to more terms, and I don't know whether you can expect to get the desired accuracy at the end.