Recherche de rep-units

Publié le 12/04/17

(cet exercice est issu de l’oral Ensam Psi 2015)
On admet que tout {n\in\mathbb{N}} impair non multiple de {5} a un multiple {N} ne s’écrivant (en base {10}) qu’avec des {1}.

  1. Définir une fonction \texttt{QueDesUn(n)} renvoyant le plus petit {N} correspondant.
  2. Afficher les couples {(n,N)} pour {n} variant de {1} à {100}.
  3. Définir une fonction donnant le nombre de chiffres (en base {10}) d’un entier.
    Pour {n \le 1000}, chercher les couples {(n,N)} avec {N} de longueur maximale.

  1. Il y a une solution à éviter absolument (car elle conduit à des temps de calculs catastrophiques) qui consisterait à former les multiples successifs de {n} jusqu’à en trouver un dont l’écriture décimale ne contienne que des {1}.

    Le mieux de trouver le plus petit {\mathbf{1}_{k}=\dfrac{10^{k}-1}{9}} (répétition de {k} fois {1}) divisible par {n}.

    Le test permet de ne lancer la recherche que si {n} est un entier strictement positif impair et non divisible par {5}. Dans le cas contraire, le résultat renvoyé par \texttt{QueDesUn} est \texttt{None}.

  2. On affiche {n} puis {N}, pour {1\le n\le 100}.

    Si {n} est invalide, donc si \texttt{QueDesUn} renvoie \texttt{None}, on n’affiche rien! :

    Voici le résultat (on a affiché le début et la fin, c’est suffisant pour se rendre compte que la longueur de l’entier N varie de façon très irrégulière en fonction de l’entier n) :

  3. Pour la fonction \texttt{longueur}, il y a plusieurs méthodes, selon ce qu’on connaît du langage Python.

    La fonction \texttt{records(n)} renvoie la liste \texttt{L} formée de tous les entiers {k} de {[[ 1,n]]} qui ont produit une longueur maximum pour {N}, ainsi que la valeur de ce maximum (mais en général il n’y a qu’un entier {n} qui réalise ce maximum).

    Ici l’expression \texttt{records(1000)} renvoie le résultat \texttt{([983],982)}.