A pretty recurrence for the primes

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$$

Cette récurrence repose sur une application non usuelle du crible d’Eratosthène.
Car au lieu de supprimer les multiples des nombres premiers, elle génère l’ensemble des nombres qui réchappent à ce crible pour ensuite en extraire le nombre premier suivant.
Ces nombres rescapés du crible d’Eratosthène sont solutions de $\prod_{i=1}^{n}(p_{i}-1)$ systèmes de n congruences (que l’on sait résoudre par le théorème chinois) et appartiennent à un nombre fini ($\prod_{i=1}^{n}(p_{i}-1)$) de progressions arithmétiques de raison $Q_{n}$:
Prenons quelques exemples:
les nombres qui réchappent au criblage par 2 sont de la forme 2k+1 (c’est trivial);
les nombres qui réchappent au criblage par 2 et 3 sont de la forme 6k+1 ou 6k+5 ;
les nombres qui réchappent au criblage par 2,3 et 5 sont de la forme 30k+a où a $\in \{1,7,11,13,17,19,23,29\}$
etc...
observation: le nombre 1 est toujours un rescapé du criblage.

D’une façon générale, les nombres qui réchappent au criblage par 2,3, jusquà $p_{n}$ sont de la forme $Q_{n}k$ +a où a parcourt $\prod_{i=1}^{n}(p_{i}-1)$ valeurs différentes qui sont chacune une solution particulière des $\prod_{i=1}^{n}(p_{i}-1)$ systèmes de n congruences.

Le nombre premier $p_{n+1}$ se cache dans l’une de ces progressions arithmétiques sans qu’on sache (a priori) laquelle précisément.

En l’absence de cette précision, il faut examiner l’ensemble des progressions arithmétiques.

Pour cela il faut déjà trouver une solution particulière de chacun des $\prod_{i=1}^{n}(p_{i}-1)$ systèmes de n congruences à partir de laquelle on pourra (modulo $Q_{n}$) générer la progression arithmétique.

il apparait que ces solutions particulières s’obtiennent assez simplement, en effet les $\prod_{i=1}^{n}(p_{i}-1)$ entiers définis par :

$\sum_{i=1}^{n}r_{i}\frac{Q_{n}}{p_{i}}$ où $1\leq r_{i}\leq p_{i}-1$

sont forcément des rescapés du criblage par 2,3, jusquà $p_{n}$ puisqu’ils ne sont jamais divisibles par aucun des nombres premiers $\leq p_{n}$ (il y a toujours un terme de cette somme qui n’est pas divisible par $p_{i}$).

De surcroit ces entiers ne peuvent pas appartenir à une même progression arithmétique de raison $Q_{n}$ car si on prend deux entiers correspondant à deux n-uplets différents $(r_{1},r_{2},\cdots r_{n})$ et $(r'_{1},r'_{2},\cdots r'_{n})$ alors il y a au moins un $r_{i}\neq r'_{i}$ de sorte que la différence de ces deux entiers ne peut être un multiple de $p_{i}$ et encore moins de $Q_{n}$.

il y a donc une bijection entre ces entiers et les solutions des $\prod_{i=1}^{n}(p_{i}-1)$ systèmes de n congruences.

Le produit $\prod_{i=1}^{n}\frac{2^{Q_{n}}-2^{Q_{n}/p_{i}}}{2^{Q_{n}/p_{i}}-1}=\prod_{i=1}^{n}(2^{Q_{n}/p_{i}}+2^{2Q_{n}/p_{i}}+2^{3Q_{n}/p_{i}}+\cdots 2^{(p_{i}-1)Q_{n}/p_{i}})$

se développe en $\sum_{k=1}^{\prod_{i=1}^{n}(p_{i}-1)}2^{w_{k}}$ où les $w_{k}$ sont précisement tous les entiers de la forme $\sum_{i=1}^{n}r_{i}\frac{Q_{n}}{p_{i}}$ où $1\leq r_{i}\leq p_{i}-1$

En multipliant $\sum_{k=1}^{\prod_{i=1}^{n}(p_{i}-1)}2^{w_{k}}$ par $\frac{1}{2^{Q_{n}}-1}=\frac{1}{2^{Q_{n}}}+\frac{1}{2^{2Q_{n}}}+\frac{1}{2^{3Q_{n}}}+\cdots$

On génère ainsi (au niveau des exposants de 2) des progressions arithmétiques (décroissantes) de raison $Q_{n}$ à partir de chaque exposant $w_{k}$.

Le produit $\frac{1}{2^{Q_{n}}-1}\prod_{i=1}^{n}\frac{2^{Q_{n}}-2^{Q_{n}/p_{i}}}{2^{Q_{n}/p_{i}}-1}$ a donc une partie fractionnaire $s_{n}$ qui s’écrit $\sum_{k=0}^{+\infty}\frac{1}{2^{r_{k}}}$ où $r_{k}$ parcourt dans le sens croissant l’ensemble des rescapés du crible d’Eratosthène avec $r_{0}=1$ et $r_{1}=p_{n+1}$.

Comme le fait observer visitor dans sa solution, $s_{n}$ peut aussi s’écrire $\sum_{d|Q_{n}}\mu(d)\frac{1}{2^{d}-1}$ (formule publié par le mathématicien Gandhi en 1971) mais d’une part cette expression reprend le principe traditionnel du crible d’Eratosthène en l’appliquant sur les exposants de la somme $\sum_{k=1}^{+\infty}\frac{1}{2^{k}}$ et d’autre part la somme $\sum_{d|Q_{n}}\mu(d)\frac{1}{2^{d}-1}$ , outre le fait d’utiliser la fonction de Mobius, porte sur $2^{n}$ termes alors que l’expression $\frac{1}{2^{Q_{n}}-1}\prod_{i=1}^{n}\frac{2^{Q_{n}}-2^{Q_{n}/p_{i}}}{2^{Q_{n}/p_{i}}-1}$ ne comporte que $n+1$ facteurs et donne $s_{n}$ en n’utilisant que la fonction partie fractionnaire.