Le dernier non effacé

Publié le 30/01/17

On écrit à la suite tous les entiers de {1} jusqu’à {2017}.
On les efface de {3} en {3} : d’abord {1}, puis {4}, puis {7}, etc.
On recommence sur la liste restante 2,3,5,6,8,9,11,\ldots et ainsi de suite.
Quel est le dernier nombre affiché, et au bout de combien d’itérations?
Illustrer tout cela avec Python.
On note {a_n} l’entier qui est en tête après {n} itérations.
Ainsi : {a_0=1,\;a_1=2,\;a_2=3,\;a_3=5,\;a_4=8,\cdots}
On va exprimer {a_{n+1}} en fonction de {a_n}, en discutant suivant la parité de {a_n}.

  • Supposons {a_n=2m}, avec {m\ge1}, et considérons l’entier {3m}.

    Il y a {m} entiers du type {3k+1} dans {[1,3m[}.

    À la première itération, ils sont effacés, et {3m} se retrouve en position {2m=a_n}.

    Cet entier sera donc en tête au bout de {n} itérations supplémentaires.

    On a donc prouvé que si {a_n=2m} alors {a_{n+1}=3m=\dfrac{3a_n}{2}}.

  • Supposons {a_n=2m+1}, avec {m\ge0}, et considérons l’entier {3m+2}.

    Il y a {m+1} entiers du type {3k+1} dans {[1,3m+2[}.

    À la première itération, ils sont effacés.

    L’entier {3m+2} se retrouve alors en position {(3m+2)-(m+1)=2m+1=a_n}.

    L’entier {3m+2} sera donc en tête au bout de {n} itérations supplémentaires.

    On a donc prouvé que si {a_n=2m+1} alors {a_{n+1}=3m+2=\dfrac{3a_n+1}{2}}.

  • Dans tous les cas, {a_{n+1}=\Bigl\lfloor\dfrac{3a_n+1}{2}\Bigr\rfloor} (où {\lfloor x\rfloor} est la partie entière).

    On trouve ainsi : {a_0=1,\;a_1=2,\;a_{10}=93,\;a_{16}=1065,\;a_{17}=1598,\;a_{18}=2397}.

    Puisque {a_{18}>2017}, la liste est complètement effacée à la {18}ième itération.

    On va vérifier avec Python. La fonction efface effectue n passages (un passage consistant en l’effacement d’un terme sur trois) dans la liste {L} fournie en argument (par défaut, n=1):

    Voici une autre solution, plus concise:

    On vait figurer ici le résultat après 13, 14, 15, 16, 17 et 18 itérations: