Exercice 2 — Super premiers

\(\pi(0) = 0\) : aucun premier \(\leq 0\).
\(\pi(5) = 3\) : les premiers \(\leq 5\) sont 2, 3, 5.

\(n\)	0	1	2	6	29	46	47
\(\pi(n)\)	0	0	1	3	10	14	15

\(\pi(29) = 10\) car \(p_{10} = 29\). \(\pi(47) = 15\) car \(p_{15} = 47\). \(\pi(46) = 14\) car 46 n’est pas premier.

Tout premier \(\leq n\) est aussi \(\leq n+1\) : l’ensemble des premiers \(\leq n\) est inclus dans celui des premiers \(\leq n+1\).

L’ensemble \(\{p \text{ premier} : p \leq n\} \subseteq \{p \text{ premier} : p \leq n+1\}\).
Donc \(\pi(n) \leq \pi(n+1)\). ✓

Utiliser que \(q\) est premier et \(q > p\) donc \(q\) est compté dans \(\pi(q)\) mais pas dans \(\pi(q-1)\).

Puisque \(p < q\), on a \(\pi(p) \leq \pi(q-1)\) par croissance.
De plus \(q\) est premier donc \(\pi(q) = \pi(q-1) + 1 > \pi(q-1) \geq \pi(p)\).
Donc \(\pi(p) < \pi(q)\). ✓

Les premiers \(\leq n\) sont des éléments de \(\{1, \ldots, n\}\) qui contient au plus \(n\) éléments.

Les premiers \(\leq n\) appartiennent à \(\{1, \ldots, n\}\) qui a \(n\) éléments. Donc \(\pi(n) \leq n\). ✓

\(\pi(n) = n\) ssi tous les entiers de 1 à \(n\) sont premiers. Or 1 n’est pas premier, donc c’est impossible pour \(n \geq 1\).
Pour \(n=0\) : \(\pi(0) = 0\). ✓
\(\pi(n) = n\) uniquement pour \(n = 0\).

\(m = 5\) :
\(5 \to \pi(5)=3 \to \pi(3)=2 \to \pi(2)=1 \to \pi(1)=0 \to 0 \to 0\)
Suite : 5, 3, 2, 1, 0, 0, 0

\(m = 11\) :
\(11 \to \pi(11)=5 \to \pi(5)=3 \to \pi(3)=2 \to \pi(2)=1 \to 0 \to 0\)
Suite : 11, 5, 3, 2, 1, 0, 0

Montrer que \(\pi(n) < n\) pour tout \(n \geq 1\). En déduire que la suite est strictement décroissante jusqu’à atteindre 0.

Décroissance : Pour \(n \geq 1\), 1 n’est pas premier donc \(\pi(n) \leq n-1 < n\).
Ainsi chaque terme est strictement inférieur au précédent tant qu’il est \(\geq 1\). ✓

Nullité : La suite est une suite d’entiers naturels strictement décroissants, donc elle atteint 0 en temps fini. Une fois à 0, \(\pi(0)=0\) donc elle reste à 0. ✓

\(m\)	Suite des itérés	Super premier ?
2	2, 1, 0, …	✓ (2 est premier)
3	3, 2, 1, 0, …	✓ (3 et 2 sont premiers)
5	5, 3, 2, 1, 0, …	✓ (5, 3, 2 sont premiers)
7	7, 4, 2, 1, 0, …	✗ (4 n’est pas premier)
11	11, 5, 3, 2, 1, 0, …	✓ (11, 5, 3, 2 premiers)

Super premiers parmi ces nombres : 2, 3, 5, 11

Le prochain super premier doit être premier et son premier itéré \(\pi(p)\) doit être super premier. Le plus petit choix est \(\pi(p) = s_n\).

Soit \(p\) le premier tel que \(\pi(p) = s_n\), c’est-à-dire \(p = p_{s_n}\) (le \(s_n\)-ième nombre premier).

La suite des itérés de \(p\) est \(p, s_n, \pi(s_n), \ldots\)
Puisque \(s_n\) est super premier, tous les termes \(\neq 0, 1\) de la suite à partir de \(s_n\) sont premiers.
De plus \(p\) est premier par construction. Donc \(p\) est super premier.

C’est le plus petit super premier après \(s_n\) car tout super premier \(q > s_n\) vérifie \(\pi(q) \geq s_n\), et le plus petit premier avec \(\pi(q) = s_n\) est \(p_{s_n}\). ✓

Les 4 premiers super premiers sont \(s_1=2, s_2=3, s_3=5, s_4=11\).
\(s_5 = p_{s_4} = p_{11} = 31\).
Vérification : \(31 \to \pi(31)=11 \to \pi(11)=5 \to \pi(5)=3 \to \pi(3)=2 \to 1 \to 0\).
Tous les termes \(\neq 0, 1\) sont premiers : 31, 11, 5, 3, 2. ✓
Le 5ème super premier est 31.

Considérer \(Q'\) le produit des premiers \(p\) avec \(\sqrt{N} < p \leq N\). Il y a \(\pi(N)-\pi(\sqrt{N})\) tels premiers, chacun \(> \sqrt{N}\). Utiliser le résultat admis.

Notons \(Q'\) le produit des premiers \(p\) avec \(\sqrt{N} < p \leq N\).
Il y a \(\pi(N) - \pi(\sqrt{N})\) tels premiers, chacun strictement supérieur à \(\sqrt{N}\).
Donc \(Q' > (\sqrt{N})^{\pi(N)-\pi(\sqrt{N})}\).

Par le résultat admis : \(Q' \leq Q_N \leq 4^N\).
Donc \((\sqrt{N})^{\pi(N)-\pi(\sqrt{N})} \leq 4^N\).

Pour \(N \geq 4^{2(M+1)}\) : \(\sqrt{N} \geq 4^{M+1}\).
Donc \(4^{(M+1)(\pi(N)-\pi(\sqrt{N}))} \leq (\sqrt{N})^{\pi(N)-\pi(\sqrt{N})} \leq 4^N\). ✓

De la question 10 : \(4^{(M+1)(\pi(N)-\pi(\sqrt{N}))} \leq 4^N\).
En comparant les exposants (la fonction \(x \mapsto 4^x\) est croissante) :
\((M+1)(\pi(N) - \pi(\sqrt{N})) \leq N\)
\(\pi(N) - \pi(\sqrt{N}) \leq \dfrac{N}{M+1}\)
Or \(\pi(\sqrt{N}) \leq \sqrt{N}\) par la question 4.
Donc \(\pi(N) \leq \dfrac{N}{M+1} + \pi(\sqrt{N}) \leq \dfrac{N}{M+1} + \sqrt{N}\). ✓

Utiliser l’encadrement de la question 11. Pour \(N\) grand, \(\sqrt{N}\) est négligeable devant \(N/(M+1)\).

De la question 11 : \(\pi(N) \leq \dfrac{N}{M+1} + \sqrt{N} = N\left(\dfrac{1}{M+1} + \dfrac{1}{\sqrt{N}}\right)\).

Donc \(\dfrac{N}{\pi(N)} \geq \dfrac{1}{\dfrac{1}{M+1} + \dfrac{1}{\sqrt{N}}}\).

Quand \(N \to +\infty\), \(\dfrac{1}{\sqrt{N}} \to 0\) donc \(\dfrac{N}{\pi(N)} \to M+1 > M\).
Il existe donc \(N_0\) tel que pour tout \(N \geq N_0\), \(\dfrac{N}{\pi(N)} \geq M\). ✓

\(s_{n+1} = p_{s_n}\) donc \(\pi(s_{n+1}) = s_n\). Exprimer \(s_{n+1}/s_n\) en fonction de \(s_{n+1}/\pi(s_{n+1})\) et utiliser la question 12.

Par la question 8 : \(s_{n+1} = p_{s_n}\), donc \(\pi(s_{n+1}) = s_n\).

Ainsi \(\dfrac{s_{n+1}}{s_n} = \dfrac{s_{n+1}}{\pi(s_{n+1})}\).

Puisque \(s_n \to +\infty\), on a \(s_{n+1} \to +\infty\).
Par la question 12, pour tout \(M > 0\), dès que \(s_{n+1}\) est assez grand :
\(\dfrac{s_{n+1}}{\pi(s_{n+1})} \geq M\).

Ceci étant vrai pour tout \(M > 0\) :
\(\dfrac{s_{n+1}}{s_n} \to +\infty\) quand \(n \to +\infty\). ✓

Le raisonnement par récurrence permet de démontrer qu’une propriété \(P(n)\) est vraie pour tout entier \(n \geq n_0\). Il se déroule en deux étapes :

1. Initialisation : On vérifie que \(P(n_0)\) est vraie.

2. Hérédité : On suppose \(P(n)\) vraie pour un certain \(n\) (hypothèse de récurrence) et on en déduit que \(P(n+1)\) est vraie.

Conclusion : Ces deux étapes suffisent à conclure que \(P(n)\) est vraie pour tout \(n \geq n_0\).

Analogie : C’est comme des dominos — si le premier tombe et si chaque domino fait tomber le suivant, alors tous tombent.

La récurrence forte est une variante où l’on suppose \(P(k)\) vraie pour tous les \(k < n\) avant de montrer \(P(n)\).

On démontre \(P(N)\) : « \(Q_N \leq 4^N\) » par récurrence forte sur \(N \geq 1\).

Initialisation :
\(N=1\) : \(Q_1 = 1 \leq 4\). ✓   \(N=2\) : \(Q_2 = 2 \leq 16\). ✓

Hérédité : Soit \(N \geq 3\). On suppose \(Q_k \leq 4^k\) pour tout \(k < N\). Montrons \(Q_N \leq 4^N\).

Cas 1 : \(N = 2m\) est pair.
\(2m\) n’est pas premier (pair et \(> 2\)), donc \(Q_{2m} = Q_{2m-1}\).
Par hypothèse de récurrence : \(Q_{2m-1} \leq 4^{2m-1} < 4^{2m}\). Donc \(Q_{2m} \leq 4^{2m}\). ✓

Cas 2 : \(N = 2m+1\) est impair.
On considère \(\binom{2m+1}{m} = \dfrac{(2m+1)!}{m!\,(m+1)!}\).

Étape A : Tout premier \(p\) avec \(m+2 \leq p \leq 2m+1\) divise \((2m+1)!\) mais ni \(m!\) ni \((m+1)!\) (car \(p > m+1\)). Donc \(p\) divise \(\binom{2m+1}{m}\).
Ces premiers étant distincts, leur produit (noté \(P_{m}\) = produit de tous les premiers \(p\) vérifiant \(m+2 \leq p \leq 2m+1\)) divise aussi \(\binom{2m+1}{m}\), donc :
\(P_m \leq \binom{2m+1}{m}\).

Étape B : Les deux termes centraux de \((1+1)^{2m+1} = 2^{2m+1}\) sont \(\binom{2m+1}{m}\) et \(\binom{2m+1}{m+1}\), qui sont égaux. Donc :
\(2\binom{2m+1}{m} \leq 2^{2m+1}\), d’où \(\binom{2m+1}{m} \leq 4^m\).

Étape C : On a \(Q_{2m+1} = Q_{m+1} \times P_m\) car les premiers \(\leq 2m+1\) sont exactement les premiers \(\leq m+1\) plus ceux entre \(m+2\) et \(2m+1\).
Par hypothèse de récurrence \(Q_{m+1} \leq 4^{m+1}\) et par l’étape A \(P_m \leq \binom{2m+1}{m} \leq 4^m\), donc :
\(Q_{2m+1} = Q_{m+1} \times P_m \leq 4^{m+1} \times 4^m = 4^{2m+1}\). ✓

Conclusion : Par récurrence forte, \(Q_N \leq 4^N\) pour tout \(N \geq 1\). ✓