Olympiades · Académique Nantes · 27 mars 2018 · Séries autres que S
Version identique à l'exercice 1 (série S), avec un énoncé légèrement reformulé pour les séries autres que 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 son plus grand diviseur impair. On note \(S_n\) la somme des plus grands diviseurs impairs de tous les entiers entre 1 et \(2^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\), la dernière ligne donne \(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) Donner \(S_4\) et \(S_5\).
2. Quels sont les entiers obtenus sur la dernière ligne, pour \(k\) compris entre \(2^{15}+1\) et \(2^{16}\) ?
3. Conjecturer une relation entre \(S_{16}\), \(S_{15}\) et la somme des entiers impairs \(1+3+5+\cdots+(2^{16}-1)\).
4. a) Compléter l'algorithme (boucle « Tant que \(p\) est pair faire \(p\) prend la valeur … »). b) Donner la valeur de \(S\) en sortie pour \(n=16\).
5. Déterminer l'expression de \(S_n\) en fonction de \(n\).
Voir l'exercice 1 (série S) — le raisonnement et les résultats sont strictement identiques. La seule différence porte sur la question 3, formulée ici directement en termes de \(S_{16}\) et \(S_{15}\) plutôt que sous forme de conjecture générale sur \(S_{n+1}\) et \(S_n\).
1a. Les entiers de la dernière ligne (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=86\) et \(S_5=S_4+256=342\).
2. Les entiers de la dernière ligne pour \(k\) entre \(2^{15}+1\) et \(2^{16}\) sont exactement les entiers impairs \(1,3,5,\dots,2^{16}-1\) (même argument de tiroirs qu'à l'exercice 1).
3. \(S_{16}-S_{15}=1+3+5+\cdots+(2^{16}-1)=4^{15}=1\,073\,741\,824\).
4a. On complète par : p prend la valeur p/2.
4b. \(S_{16}=1\,431\,655\,766\).
5. Comme à l'exercice 1, \(S_{n+1}-S_n=4^n\) et \(S_1=2\) donnent \(S_n=\dfrac{4^n+2}{3}\).