Une jolie récurrence pour les nombres premiers

Posons $Q=Q_n$ et $m=p_{n+1}$.
Pour chaque $i$,
$$\frac{2^{Q}-2^{Q/p_i}}{2^{Q/p_i}-1} =\frac{2^{Q}-1}{2^{Q/p_i}-1}-1,$$puisque le membre de droite vaut $\frac{2^{Q}-1-2^{Q/p_i}+1}{2^{Q/p_i}-1}$. En notant
$$u_d=\frac{1}{2^{Q/d}-1}\quad\text{pour } d\mid Q,\qquad\text{de sorte que}\ \frac{2^{Q}-1}{2^{Q/p_i}-1}=\frac{u_{p_i}}{u_1},$$il vient
$$M_n=u_1\prod_{i=1}^{n}\left(\frac{u_{p_i}}{u_1}-1\right).$$Développons : le terme indexé par $S\subseteq\{1,\dots,n\}$ vaut $(-1)^{n-|S|}u_1^{1-|S|}\prod_{i\in S}u_{p_i}$. Or les $Q/p_i$ pour $i\in S$ ont pour pgcd $Q/\prod_{i\in S}p_i$, et l’identité clé
$$\prod_{i\in S}\frac{1}{2^{Q/p_i}-1}\cdot\bigl(2^{Q}-1\bigr)^{|S|-1} \ \equiv\ \frac{1}{2^{Q/d_S}-1}\pmod{1},\qquad d_S=\prod_{i\in S}p_i,$$donne, modulo $1$,
$$M_n\ \equiv\ \sum_{d\mid Q}\frac{\mu(d)}{2^{d}-1}.$$Autrement dit, en posant $\displaystyle T=\sum_{d\mid Q}\frac{\mu(d)}{2^{d}-1}$, on a $s_n=T-\lfloor T\rfloor$.

Pour $d\mid Q$,
$$\frac{1}{2^{d}-1}=\sum_{j\geqslant 1}2^{-jd},$$série géométrique de raison $2^{-d}<1$. Donc
$$T=\sum_{d\mid Q}\mu(d)\sum_{j\geqslant 1}2^{-jd}=\sum_{k\geqslant 1}c_k\,2^{-k}, \qquad c_k=\sum_{d\mid\gcd(k,Q)}\mu(d).$$La somme des $\mu(d)$ sur les diviseurs d’un entier vaut $1$ si cet entier est $1$, et $0$ sinon. Ainsi
$$c_k=\begin{cases}1&\text{si }\gcd(k,Q)=1,\\ 0&\text{sinon,}\end{cases} \qquad\text{d'où}\qquad T=s_n=\sum_{\substack{k\geqslant 1\\ \gcd(k,Q)=1}}2^{-k}.$$Tous les termes étant $<1$ et $c_1=1$ donnant $T\geqslant\frac12$ avec $T<1$, on a bien $\lfloor T\rfloor=0$.

Les deux premiers bits. Les $k\geqslant 1$ premiers à $Q$ sont $1$, puis $m$, donc l’un des $p_i$. Donc
$$s_n=\frac12+\sum_{\substack{k\geqslant m\\ \gcd(k,Q)=1}}2^{-k},$$et cette queue est encadrée par son premier terme et la somme géométrique complète :
$$2^{-m}\ \leqslant\ s_n-\frac12\ \leqslant\ \sum_{k\geqslant m}2^{-k}=2^{1-m}.$$La majoration est stricte car le terme $k=m+1$ manque ($p_{n+1}+1$ est pair pour $m\geqslant 3$). D’où
$$m-1\ \leqslant\ -\log_2\!\left(s_n-\tfrac12\right)\ <\ m,$$la partie entière vaut $m-1$, et
$$1+\left\lfloor-\frac{\ln\bigl(s_n-\frac12\bigr)}{\ln 2}\right\rfloor=p_{n+1}. \qquad\blacksquare$$