Laboratoire 3

Ce laboratoire vise principalement à vous entraîner à manipuler l’arithmétique modulaire. Cette fois, le programme que vous allez développer n’aura pas d’interface graphique, mais il sera capable d’accomplir un calcul difficile.

Faites bien attention à lire en détail toutes les directives de ce tutoriel, en particulier les spécifications précises des fonctions que vous serez amenés à rédiger. C’est la clé de la réussite de cet exercice.

Les cailloux de Thor

Il y a de cela bien longtemps, Thor, dieu du Tonnerre et de la Force, fut mis à l’épreuve par son père Odin, dieu du Savoir et de la Guerre. L’épreuve consistait à compter (sans se tromper sous peine de devoir recommencer!) le nombre total de cailloux présents au Pays de Galles. (Cette histoire est relatée dans The long dark tea-time of the soul , de Douglas Adams.)

Pour être assuré de ne pas oublier de caillou et de ne pas compter certains d’entre eux plusieurs fois, Thor décida de les numéroter, à partir du nombre 1. Mais il fut rapidement embarrassé: Pour écrire les numéros des cailloux, il était parfois amené à utiliser le chiffre “7”, qui comme chacun le sait est sacré. Pour ne pas offenser les autres dieux, il recommença alors sa numérotation depuis le début, cette fois sans utiliser les nombres qui nécessitent un “7” dans leur écriture.

Thor n’était toujours pas satisfait. En effet, bien que le chiffre “7” n’apparaissait plus dans aucun numéro de caillou, il constata que certains de ces numéros étaient quand même des multiples de 7. Pour ne pas attirer sur lui le courroux des dieux, il entreprit de renuméroter à nouveau tous les cailloux, cette fois en se passant aussi de tous les numéros multiples de 7. Et comme il était superstitieux, il en profita pour également écarter tous les multiples de 13.

Après avoir achevé cet ouvrage colossal, Thor put enfin se reposer. Le dernier caillou passé par ses mains portait le numéro 99999999999999999999 (il y a vingt chiffres “9”). Thor fut alors pris d’un doute: Etait-il possible de retrouver, à partir de ce numéro, le nombre total de cailloux présents au Pays de Galles?

Pouvez-vous l’aider? Seriez-vous capable de calculer le nombre total de cailloux qui ont été numérotés, afin que Thor ne doive pas les recompter?

Une première solution simple

Appelons \(N\) le numéro du dernier caillou. Pour résoudre le problème, il suffit de compter parmi les nombres de l’intervalle \([1, N]\) combien d’entre eux satisfont les trois propriétés suivantes:

  • Le chiffre “7” n’apparaît pas dans leur écriture.
  • Ils ne sont pas multiples de 7.
  • Ils ne sont pas multiples de 13.

On peut facilement écrire un programme qui effectue ce comptage. Pour pouvoir le mettre au point, il est utile de pouvoir tester ce programme avec différentes valeurs de \(N\). Le plus simple est de permettre à l’utilisateur de fournir cette valeur en argument du programme.

Procédure à suivre:

  1. Ecrire un programme Python prog-8.py qui lit la valeur de l’argument qui lui est passé lorsqu’il est exécuté, et l’interprète comme un nombre entier \(N\).

    Note: Les mécanismes permettant de lire les arguments fournis au programme et de les convertir en entiers sont expliqués dans le tutoriel du laboratoire 2.

  2. Dans la suite du programme, pour chaque entier \(i\) compris entre 1 et \(N\):

    1. Déterminer si le chiffre “7” intervient ou non dans l’écriture de \(i\). Les mécanismes suivants peuvent vous être utiles:

      • L’expression str(x) convertit le nombre x en une chaîne de caractères contenant son écriture en base 10.
      • Si s1 et s2 sont des chaînes de caractères, alors l’expression s1.find(s2) cherche la première occurrence de s2 à l’intérieur de s1 et en retourne la position. Cette expression retourne -1 si s2 n’apparaît pas dans s1.

      Note: Il existe d’autres façons de réaliser cette opération, notamment par un procédé purement arithmétique plutôt qu’en manipulant des chaînes de caractères. Cette deuxième technique est un peu plus compliquée à mettre en oeuvre, mais plus efficace.

    2. Déterminer si \(i\) est un multiple de 7 ou de 13.

    3. Si les réponses aux points a, et b sont négatives, incrémenter un compteur. Afficher la valeur finale de celui-ci au terme de l’exécution du programme.

  3. Tester votre programme. Pour \(N = 20\), vous devriez obtenir la valeur 16, puisque parmi les entiers dans l’intervalle \([1, 20]\), les nombres 7, 13, 14 et 17 doivent être écartés.

    D’autres résultats permettant de tester votre programme sont donnés ci-dessous.

    N Résultat attendu
    99 64
    999 576
    9999 5189
    99999 46729
    999999 420504

    Note: Comme 999999 est un multiple de 7, ce nombre ne peut pas correspondre au numéro d’un caillou. Mais le problème consistant à compter le nombre de valeurs dans l’intervalle \([1, 999999]\) qui s’écrivent sans “7” et ne sont ni multiples de 7, ni multiples de 13 reste parfaitement défini.

  4. En utilisant la commande time, vous pouvez également mesurer le temps nécessaire à l’exécution du programme. Par exemple, la commande

    time python3 prog-8.py 20

    exécute le programme avec un argument égal à 20, et affiche ensuite des statistiques sur son temps d’exécution. Dans ces statistiques, la somme des deux premières valeurs (notées « u » et « s ») fournit le temps CPU consommé.

    En observant l’évolution du temps d’exécution en fonction de \(N\), seriez-vous capable d’extrapoler et d’obtenir un ordre de grandeur du temps de calcul nécessaire pour \(N = 10^{20} - 1\) (correspondant au dernier caillou numéroté par Thor)?

  5. Déposer votre programme dans le répertoire centralisé, sous le suffixe prog-8.py.

Vers une solution plus efficace

Comme il n’est pas raisonnable d’attendre la fin du calcul pendant des milliers ou des millions d’années, nous allons chercher à obtenir une solution plus performante.

Si vous trouvez une piste permettant de résoudre ce problème, vous n’êtes pas obligé de suivre la suite de ce tutoriel! Rédigez un programme qui met en oeuvre votre solution, et déposez-le dans le répertoire centralisé, sous le suffixe prog-9.py. Vous pouvez ensuite directement attaquer le problème abordé dans cette section. De même, si vous pensez avoir une bonne stratégie pour arriver à une solution, n’hésitez pas à en discuter avec un encadrant avant de lire celle qui est proposée ci-dessous.

Pour développer un programme capable d’effectuer le calcul en une fraction de seconde, l’idée consiste à utiliser l’arithmétique modulaire. Celle-ci va nous permettre de compter, parmi les nombres entiers qui s’écrivent sans le chiffre “7”, combien d’entre eux sont des multiples d’un nombre \(m\) donné. Plus précisément, pour un ensemble d’entiers \(S_i\) donné, nous allons construire un tableau \(t_i\) à \(m\) cases tel que:

  • \(t_i[0]\) contient le nombre d’entiers de l’ensemble qui sont égaux à un multiple de \(m\).
  • \(t_i[1]\) contient le nombre d’entiers de l’ensemble qui sont égaux à un multiple de \(m\) plus 1.
  • \(t_i[2]\) contient le nombre d’entiers de l’ensemble qui sont égaux à un multiple de \(m\) plus 2.
  • …
  • \(t_i[m-1]\) contient le nombre d’entiers de l’ensemble qui sont égaux à un multiple de \(m\) plus \(m-1\) (c’est-à-dire à un multiple de \(m\) moins 1).

Par exemple, pour \(m = 7\), si l’on considère l’ensemble \(S_1\) des nombres de 0 à 9 qui s’écrivent sans le chiffre “7”, on obtient

\(t_1 = [ 1, 2, 2, 1, 1, 1, 1 ]\).

En effet, cet ensemble contient deux multiples de 7 plus 1 (les nombres 1 et 8), deux multiples de 7 plus 2 (les nombres 2 et 9), et un seul multiple de 7 plus \(p\) pour \(p \in \{ 0, 3, 4, 5, 6 \}\).

Considérons maintenant l’ensemble \(S_2\) des nombres qui peuvent s’écrire sur deux chiffres sans utiliser “7”. Ces nombres forment l’intervalle \([0, 99]\) dont on a oté 7, 17, 27, …, 67, 70, 71, 72, … (Note: Les nombres 0, 1, 2, … font partie de cet ensemble car on peut les écrire 00, 01, 02, …) En généralisant, on définit de la même manière les ensembles \(S_k\), pour \(k = 1, 2, 3, ...\) contenant les nombres qui s’écrivent sur \(k\) chiffres sans utiliser “7”.

Comment peut-on calculer \(t_{2}\)? Bien sûr, on pourrait énumérer les 100 nombres de l’intervalle \([0, 99]\), et pour ceux qui s’écrivent sans “7”, incrémenter la case appropriée du tableau. L’inconvénient de cette approche est que le calcul de \(t_k\) deviendrait rapidement très coûteux pour de grandes valeurs de \(k\).

Il existe une bien meilleure solution. Pour obtenir un nombre à \(k+1\) chiffres, il suffit évidemment d’ajouter un nouveau chiffre à un nombre comportant déjà \(k\) chiffres. Supposons par exemple que le chiffre que l’on ajoute est “5”. Essayons de répondre aux questions suivantes:

  • Si l’on ajoute le chiffre “5” à un multiple de 7, qu’obtient-on?

    Un multiple de 7 est un nombre \(n\) tel que \(n =_7 0\), où “\(=_7\)” désigne l’égalité modulo 7.

    Ajouter le chiffre 5 à \(n\) fournit le nombre \(10n + 5\).

    Si \(n =_7 0\), alors

    \[\begin{split}10n + 5 &=_7 10 \times 0 + 5\\ &=_7 5.\end{split}\]

    On obtient donc dans ce cas un multiple de 7 plus 5.

  • Si l’on ajoute le chiffre “5” à un multiple de 7 plus 1, qu’obtient-on?

    Un multiple de 7 plus 1 est un nombre \(n\) tel que \(n =_7 1\).

    Si \(n =_7 1\), alors

    \[\begin{split}10n + 5 &=_7 10 \times 1 + 5\\ &=_7 15 \\ &=_7 1.\end{split}\]

    On obtient donc dans ce cas un multiple de 7 plus 1.

  • De façon plus générale, si l’on ajoute le chiffre \(d\) à un multiple de \(m\) plus \(p\), qu’obtient-on?

    Si \(n =_m p\), alors

    \[\begin{split}10n + d &=_m 10p + d\\ &=_m r,\end{split}\]

    où \(r\) est le reste de la division de \(10p + d\) par \(m\).

Ces résultats nous permettent de calculer \(t_{2}\) à partir de \(t_{1}\) et même, de façon plus générale, de calculer \(t_{k+1}\) à partir de \(t_{k}\) pour n’importe quelle valeur de \(k.\) L’algorithme est le suivant:

  1. Initialement, \(t_{k+1}\) est un tableau de dimension \(m\) dont toutes les cases sont nulles.

  2. Pour tous les chiffres \(d\) de l’ensemble \(\{ 0, 1, 2, 3, 4, 5, 6, 8, 9 \}\) (on a oté le chiffre “7”), et pour \(p = 0, 1, 2, ..., m - 1\):

    1. Calculer le reste \(r\) de la division de \(10p + d\) par \(m\).

    2. La valeur de \(t_{k}[p]\) représente le nombre de nombres à \(k\) chiffres écrits sans “7” qui sont égaux modulo \(m\) à \(p\).

      Si on leur ajoute un chiffre \(d\), chacun d’entre eux deviendra donc un nombre à \(k + 1\) chiffres écrit sans “7” qui est égal modulo \(m\) à \(r\).

      Pour comptabiliser tous ces nombres, il faut dès lors ajouter à \(t_{k+1}[r]\) la valeur de \(t_{k}[p]\).

Note: En fait, cette procédure permet même de calculer \(t_1\) à partir de données plus simples. Si l’on considère que le chiffre “0” est toujours facultatif en tête de l’écriture d’un nombre, alors le nombre zéro possède une écriture sur 0 chiffre, sous la forme du mot vide. On a dès lors pour \(m = 7\):

\(t_0 = [ 1, 0, 0, 0, 0, 0, 0 ]\)

(car zéro est un multiple de 7). En appliquant l’algorithme, on obtient

\(t_1 = [ 1, 2, 2, 1, 1, 1, 1 ]\)

qui correspond bien à ce que nous avions précédemment calculé.

Programmation de l’algorithme

Votre mission est à présent d’implémenter cet algorithme, afin de calculer successivement les tableaux \(t_0, t_1, t_2, ...\), jusqu’à une borne donnée.

Procédure à suivre:

  1. Dans un nouveau programme prog-9.py, créer une fonction calculer_t(k_max, m) prenant comme arguments:

    • La borne k_max des valeurs de \(k\) à considérer. (En d’autres termes, le programme doit calculer \(t_0, t_1, ..., t_{\mathtt{k\_max}}\).)
    • La valeur m dont on s’intéresse aux multiples. (Dans les exemples précédents, on avait \(m= 7\).)

    Cette fonction doit retourner une matrice t possédant k_max+1 rangées et m colonnes. Chaque élément t[k][p] de cette matrice doit contenir le nombre de nombres à k chiffres écrits sans chiffre “7” qui sont égaux modulo m à p.

  2. Testez ce programme. Pour \(m=7\), les premières rangées de la matrice t devraient contenir les valeurs suivantes:

    \[\begin{split}\begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 2 & 2 & 1 & 1 & 1 & 1\\ 12 & 12 & 11 & 11 & 12 & 12 & 11\\ 104 & 104 & 105 & 104 & 104 & 104 & 104\\ 938 & 938 & 937 & 937 & 937 & 937 & 937\\ 8435 & 8436 & 8436 & 8435 & 8436 & 8436 & 8435\\ 75921 & 75920 & 75920 & 75920 & 75920 & 75920 & 75920\\ 683281 & 683282 & 683282 & 683281 & 683281 & 683281 & 683281\\ 6149532 & 6149532 & 6149531 & 6149531 & 6149532 & 6149532 & 6149531\\ 55345784 & 55345784 & 55345785 & 55345784 & 55345784 & 55345784 & 55345784 \end{array}\end{split}\]

Solution du problème

Vous avez maintenant tous les outils en main pour résoudre le problème des cailloux de Thor. Pour rappel, il s’agit de déterminer, pour \(N = 10^{20} - 1\), quels sont les nombres de l’intervalle \([1, N]\) s’écrivant sans le chiffre “7” qui ne sont ni multiples de 7, ni multiples de 13.

Pour mettre au point le programme, il est une fois de plus utile de pouvoir le tester à l’aide de différentes valeurs de \(N\). Un mécanisme simple consiste à fournir au programme un argument entier \(K\), qui déterminera la valeur de \(N\) selon la formule \(N = 10^K - 1\).

L’algorithme qui sera mis en oeuvre est le suivant:

  1. En exploitant la fonction calculer_t() obtenue au point précédent, calculer les matrices t7, t13 et t91 correspondant respectivement à \(m = 7\), \(m = 13\) et \(m = 91\), pour une valeur de k_max au moins égale à celle de \(K\).

  2. Des ces matrices, extraire le nombre de valeurs dans l’intervalle \([1, N]\) s’écrivant sans le chiffre “7” qui sont respectivement:

    • non-multiples de 7.

      (Rappel: Chaque élément t7[k][p] de t7 contient le nombre de nombres à k chiffres s’écrivant sans “7” qui sont égaux modulo 7 à p.)

    • multiples de 13.

    • multiples de 91.

    (A l’issue de cette étape, on aura donc obtenu trois nombres.)

  3. Calculer le nombre de valeurs dans l’intervalle \([1, N]\) s’écrivant sans le chiffre “7” qui ne sont ni multiples de 7, ni multiples de 13. Pour obtenir ce nombre, il suffit de retirer des non-multiples de 7 les nombres multiples de 13, en faisant bien attention au cas de ceux qui sont à la fois multiples de 7 et de 13.

Vous pouvez maintenant modifier votre programme prog-9.py de façon à y incorporer cet algorithme. Voici la marche à suivre:

  1. Ecrire une fonction compter_multiples(k, m, t) prenant comme arguments:

    • Le nombre k de chiffres des nombres à examiner.
    • La valeur m dont on s’intéresse aux multiples.
    • La matrice t précédemment calculée par calculer_t() pour la même valeur de m, et une valeur de k_max au moins égale à k.

    Cette fonction doir retourner une paire (c1, c2), où:

    • c1 est le nombre de nombres s’écrivant sur k chiffres sans “7” qui sont multiples de m.
    • c2 est le nombre de nombres s’écrivant sur k chiffres sans “7” qui ne sont pas multiples de m.

  2. Ecrire une fonction compter_nombres_valides(k) qui retourne le nombre de valeurs s’écrivant sur k chiffres sans utiliser “7” qui ne sont ni multiples de 7, ni multiples de 13. Cette fonction doit:

    1. Calculer les matrices t7, t13 et t91.
    2. Invoquer la fonction compter_multiples() afin d’obtenir le nombre de multiples et de non-multiples de 7, 13 et 91 dans l’ensemble considéré.
    3. En déduire le résultat final.

  3. Faire lire à votre programme un argument permettant de spécifier la valeur de \(K\).

  4. Tester votre programme en vérifiant que ses résultats sont bien identiques à ceux fournis par prog-8.py. (Attention, si vous avez respecté les consignes, alors l’argument de ces deux programmes n’est pas identique: prog-8.py 9999 correspond à prog-9.py 4.)

  5. Etes-vous maintenant à même d’attaquer le cas \(N = 10^{20} - 1\)? Combien de temps faut-il désormais à votre programme pour effectuer le calcul? Serait-il envisageable de le pousser jusqu’à \(N = 10^{100} - 1\)? Voire même \(N = 10^{1000} - 1\)?

  6. Déposer votre programme dans le répertoire centralisé, en utilisant le suffixe prog-9.py.

Généralisation

Le problème de cailloux de Thor a pu être résolu parce que son énoncé représentait à un cas particulier qui facilitait grandement les calculs. En effet, le numéro inscrit sur le dernier caillou correspondait exactement au plus grand nombre qu’il est possible d’écrire à l’aide de 20 chiffres.

Nous allons maintenant tenter de résoudre le même problème, mais pour une valeur quelconque de \(N\). Par exemple, si le dernier caillou portait le numéro 1135049636560561108316, comment pourrait-on en déduire le nombre total de cailloux?

Pour arriver à une solution, nous allons procéder en deux étapes. Appelons nombre admissible un nombre qui s’écrit sans chiffre “7”, et qui n’est ni multiple de 7, ni multiple de 13.

  1. En exploitant les résultats de la section précédente, nous allons compter les nombres admissibles dont l’écriture est composée d’un préfixe \(f\) donné, suivi par \(k\) chiffres quelconques.

    Par exemple, si \(f = 42\) et \(k = 3\), le problème consistera à compter les nombres admissibles dans l’intervalle \([42000, 42999]\).

  2. Pour pouvoir compter les nombres admissibles dans \([1, N]\), on va décomposer l’intervalle \([0, N]\) en une union d’intervalles pour lesquels il existe des valeurs de \(f\) et de \(k\). Par exemple, pour \(N = 2654\), cette décomposition produira les intervalles suivants:

    Intervalle \(f\) \(k\)
    [0, 999] 0 3
    [1000, 1999] 1 3
    [2000, 2099] 20 2
    [2100, 2199] 21 2
    [2200, 2299] 22 2
    [2300, 2399] 23 2
    [2400, 2499] 24 2
    [2500, 2599] 25 2
    [2600, 2609] 260 1
    [2610, 2619] 261 1
    [2620, 2629] 262 1
    [2630, 2639] 263 1
    [2640, 2649] 264 1
    [2650, 2650] 2650 0
    [2651, 2651] 2651 0
    [2652, 2652] 2652 0
    [2653, 2653] 2653 0
    [2654, 2654] 2654 0

Notes:

  • Dans un souci d’efficacité, on cherche à ce que le nombre d’intervalles qui interviennent dans cette décomposition soit le plus petit possible.
  • A l’issue de cette décomposition, seul le nombre 0 aura été compté en trop; il sera facile de le retirer puisqu’il s’agit d’un multiple de 7 (ainsi que de 13).

Procédure à suivre:

  1. Recopier votre programme prog-9.py dans un nouveau fichier prog-10.py.

  2. Ajouter à ce programme une fonction compter_multiples_avec_prefixe(f, k, m, t) prenant comme arguments:

    • Un préfixe f (fourni sous la forme d’un nombre entier).
    • Un nombre de chiffres k à ajouter à ce préfixe.
    • Un nombre m dont on s’intéresse aux multiples.
    • Une matrice t précédemment calculée par calculer_t(), pour la même valeur de m et une valeur de k_max au moins égale à k.

    Cette fonction doit retourner le nombre de valeurs dont l’écriture correspond au préfixe f suivi de k chiffres, sans utiliser “7”, et qui sont multiples de m.

    Pour calculer cette fonction, il faut à nouveau exploiter l’arithmétique modulaire. Prenons un exemple. Dans le cas où \(f = 24\), \(k = 2\) et \(m = 7\), on procède de la façon suivante:

    1. On a \(2400 =_7 6\). Par conséquent, pour \(n \in [0, 99]\), on a

      \(2400 + n =_7 6 + r\),

      où \(r\) est le reste de la division de \(n\) par 7.

    2. Pour que \(2400 + n\) soit un multiple de 7, il faudrait donc que \(n\) soit un multiple de 7 moins 6, c’est-à-dire un multiple de 7 plus 1.

    3. La valeur recherchée est donc égale au nombre de nombres qui s’écrivent sur 2 chiffres, sans utiliser “7”, et qui sont égaux à un multiple de 7 plus 1. Cette valeur a déjà été calculée et est disponible dans la case t[2][1] de la matrice t.

    Vous avez à présent tout ce qu’il vous faut pour implémenter la fonction compter_multiples_avec_prefixe().

  3. Tester soigneusement votre implémentation de cette fonction. Pour \(m = 7\) et les intervalles obtenus dans l’exemple précédent, vous devriez obtenir ces résultats:

    \(f\) \(k\) Résultat attendu
    0 3 104
    1 3 104
    20 2 11
    21 2 12
    22 2 12
    23 2 11
    24 2 12
    25 2 11
    260 1 1
    261 1 2
    262 1 1
    263 1 2
    264 1 1
    2650 0 0
    2651 0 0
    2652 0 0
    2653 0 1
    2654 0 0

  4. Modifier votre fonction compter_multiples() de façon à y remplacer son argument \(k\) (le nombre de chiffres des nombres à examiner) par \(n\) (le plus grand nombre à examiner): Au lieu d’explorer l’intervalle \([1, 10^K - 1]\), cette fonction travaillera maintenant dans \([1, N]\). La nouvelle version de votre fonction doit effectuer les opérations suivantes:

    1. Enumérer toutes les puissances \(10^k\) inférieures ou égales à \(N\) et, pour chacune d’entre elles, calculer toutes les valeurs appropriées du préfixe \(f\).

      Il est essentiel de bien prendre le temps de vérifier cette étape. pour \(N = 2654\), votre fonction devrait considérer toutes les paires \((p, k)\) figurant dans le tableau précédent. Remarquez bien que le cas \(k = 0\) est un peu particulier.

      Notes:

      • Attention, il ne faut pas oublier d’exclure les préfixes qui comportent le chiffre “7” dans leur écriture! N’oubliez pas de vérifier que c’est bien le cas pour votre implémentation.
      • L’ordre dans lequel on considère les paires \((p, k)\) n’a aucune importance.
      • Etant donné que \(N\) doit correspondre au numéro d’un caillou, il est permis de supposer que son écriture ne comprend pas le chiffre “7”.

    2. Pour chaque paire \((p, k)\) obtenue, invoquer la fonction compter_multiples_avec_prefixe() de façon à déterminer le nombre de multiples de \(f\) figurant dans l’intervalle associé. Totaliser le nombre de multiples et le nombre de non-multiples dans deux compteurs séparés (initialisés à zéro).

    3. A la fin du calcul, retourner une paire contenant le nombre de multiples et le nombre de non-multiples de \(m\), comme le faisait la version précedente de la fonction. Ne pas oublier de retirer 1 au nombre final de multiples, puisque le comptage a aussi considéré le nombre 0 qui ne fait pas partie de l’intervalle \([1, N]\).

  5. Si vous ne l’avez déjà fait, modifier l’argument de votre programme de façon à ce qu’il permette de spécifier \(N\) plutôt que \(K\). Vérifier que la valeur fournie n’est pas un multiple de 7 ou de 13, et que son écriture ne comprend pas le chiffre “7”. (Le cas échéant, le programme doit afficher un message d’erreur.) Modifier également la fonction compter_valides() afin qu’elle prenne \(N\) plutôt que \(K\) comme argument.

  6. Vérifier que le programme fonctionne correctement, en comparant les résultats qu’il fournit avec ceux produits par prog-8.py.

  7. Déposer votre programme dans le répertoire centralisé, avec le suffixe prog-10.py.

Si vous êtes arrivé ici avec un programme capable de résoudre le problème pour \(N = 1135049636560561108316\) (remarquez que ce nombre n’a pas été choisi au hasard!), félicitations. Vous êtes maintenant un “pro” de l’arithmétique modulaire!