# Probability of an integer being a prime

$\Omega=\mathbb{N}^*,P(\omega=n)=\dfrac{1}{2^n}$, let $A_k$ be the event $k\mid\omega$.

1) Find $P(A_k)$

2) Let B be the event "$\omega$ is prime", show that $\frac{13}{32}<P(B)<\frac{209}{504}$

One can see easily that $P(A_k)=\dfrac{1}{2^k-1}$

To find $P(B)$, I did the following :

\begin{align} P(B)&=\displaystyle\sum_{n\in\mathbb{N}^*}P(\omega=n)P\left(\bigcap_{k=2}^{\lfloor\sqrt{n}\rfloor}\overline{A_k}\right) \\&=\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-P\left(\bigcup_{k=2}^{‌​\lfloor\sqrt{n}\rfloor}{A_k}\right)\right) \\&\le\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}P\left(A_k\right)‌​\right) \\&=\sum_{n\in\mathbb{N}^*}\dfrac{1}{2^n}\left(1-\sum_{k=2}^{\lfloor\sqrt{n}\rfloor}\dfrac{1}{2^k-1}\right)\end{align}

However, I cannot find a good simplification of that bound.

For the lower bound, note that the probability of selecting the first three primes is

$$P\left(\omega \in \{2,3,5\}\right) = \frac14 + \frac18 + \frac1{32}=\frac{13}{32}$$

and the desired probability is obviously higher than that.

To get an upper bound, consider the probability of choosing $2$ or an odd number $> 2$.

$$P\left(\omega \in \{2\} \cup \{2k+1, k \in \Bbb{Z^+} \} \right)= \frac14+\sum_{k=1}^{\infty}\frac1{2^{2k+1}} = \frac14+\frac16=\frac5{12} > \frac{209}{504}$$ Because of the last inequality, this bound is not tight enough. So let's try to remove the first non-primes among our odd numbers, i.e. $\{9,15,21\dots\}$.

\begin{align} P\left(\omega \in \{2\} \cup \{2k+1, k \in \Bbb{Z^+} \}\setminus\{6k+3, k \in \Bbb{Z^+} \}\right)&=\frac5{12}-\sum_{k=1}^{\infty}\frac1{2^{6k+3}}\\\\ &=\frac5{12}-\frac1{504}\\\\ &=\frac{209}{504} \end{align}

The desired probability is obviously lower than this. Hence, $$\large\boxed{\frac{13}{32} < P\left(\omega \text{ is prime}\right) < \frac{209}{504}}$$

Calculation of one of the sums: \begin{align} \sum_{k=1}^\infty \frac1{2^{6k+3}} &= \sum_{k=1}^\infty \frac1{2^3 2^{6k}}\\ &= \frac1{2^3} \sum_{k=1}^\infty \left(\frac1{2^6}\right)^k\\ &= \frac18 \left( \sum_{k=0}^\infty \left(\frac1{64}\right)^k -1\right)\\ &= \frac18 \left( \frac1{1-\frac1{64}} - 1 \right) \\ &= \frac18 \left( \frac{64}{63} - 1 \right) \\ &= \frac18 \left(\frac1{63}\right)\\ &= \frac1{504} \end{align}

• $\displaystyle\sum_{k=1}^{\infty}\frac1{2^{3k+6}}=\frac{1}{448}\neq\frac{1}{504}$ – Hippalectryon Nov 27 '14 at 0:16
• (that being said, $\frac{1}{52}-\frac{1}{448}\sim0.41443<\frac{1}{52}-\frac{1}{504}\sim0.41468$) – Hippalectryon Nov 27 '14 at 0:36
• @Hippalectryon It was a typo, it should be $\displaystyle\frac1{2^{6k+3}}$. – Daniel R Nov 27 '14 at 8:31
• I noticed the typo right after I added the step-by-step calculation of the sum, but I'll let it stand. – Daniel R Nov 27 '14 at 8:33