Olympiades · Académique Nantes · 27 mars 2018 · Série S
Soit \(n\) un entier naturel non nul. On écrit en ligne les entiers de 1 à \(2^n\) ; on divise successivement chaque nombre pair par 2 jusqu'à obtenir un nombre impair, ce qui donne sous chaque entier \(k\) son plus grand diviseur impair \(d_k\). On note \(S_n\) la somme des \(d_k\) pour \(k\) de 1 à \(2^n\). Le but est de déterminer \(S_n\) en fonction de \(n\).
On donne \(S_1=2\), \(S_2=6\), \(S_3=22\).
1. En partant de la liste des entiers de \(2^3+1\) à \(2^4\), les entiers de la seconde ligne sont \(9,5,11,3,13,7,15,1\). a) Quels entiers apparaîtront pour la liste de \(2^4+1\) à \(2^5\) ? Calculer leur somme. b) En déduire \(S_4\) et \(S_5\).
2. Déterminer l'ensemble des valeurs de \(d_k\) lorsque \(k\) varie entre \(2^n+1\) et \(2^{n+1}\).
3. Conjecturer une relation entre \(S_{n+1}\) et \(S_n\).
4. a) Compléter l'algorithme (boucle « Tant que \(p\) est pair faire \(p\) prend la valeur … ») calculant \(S_n\). b) Donner la valeur de \(S\) en sortie pour \(n=16\).
5. Déterminer l'expression de \(S_n\) en fonction de \(n\) (on pourra utiliser les sommes des termes d'une suite arithmétique et d'une suite géométrique).
1-2. Un entier \(k\) entre \(2^n+1\) et \(2^{n+1}\) s'écrit \(k=2^n+j\) avec \(1\le j\le 2^n\) ; regrouper les \(k\) pairs et impairs séparément et remarquer que diviser les pairs par 2 ramène à une situation déjà connue, en plus petit.
3. Comparer directement la liste des diviseurs impairs obtenus entre \(2^n+1\) et \(2^{n+1}\) (question 2) à la somme des entiers impairs de 1 à \(2^{n+1}-1\).
5. Utiliser la relation de récurrence de la question 3 pour écrire \(S_n\) comme une somme de puissances de 4, puis appliquer la formule de la somme géométrique.
1a. Les entiers de la dernière ligne (pour la liste 17 à 32) sont \(17,9,19,5,21,11,23,3,25,13,27,7,29,15,31,1\), de somme \(256\).
1b. \(S_4=1+1+3+1+5+3+7+1+9+5+11+3+13+7+15+1=86\) et \(S_5=S_4+256=342\).
2. Les valeurs de \(d_k\) pour \(k\) entre \(2^n+1\) et \(2^{n+1}\) sont exactement les entiers impairs \(1,3,5,\dots,2^{n+1}-1\) (principe des tiroirs : deux entiers de cet intervalle ayant le même plus grand diviseur impair \(d\) s'écriraient \(2^n+1\le 2^ad\) et \(2^bd\le 2^{n+1}\) avec \(a\ne b\), ce qui est impossible car cela forcerait \(2^{n+1}\le 2\times(2^n+1)-2\), absurde).
3. On en déduit \(S_{n+1}-S_n=1+3+5+\cdots+(2^{n+1}-1)=2^n\times 2^n=4^n\) (somme des \(2^n\) premiers impairs).
4a. On complète par : p prend la valeur p/2.
4b. \(S_{16}=1\,431\,655\,766\).
5. De \(S_{n+1}-S_n=4^n\) et \(S_1=2\), on obtient \(S_n = 2+4+4^2+\cdots+4^{n-1} = 2+\dfrac{4^n-4}{3}=\dfrac{4^n+2}{3}\).