RA-LAlgorithmes récurrents et arithmétiques

Suite récurrente : ordre de récurrence, premiers termes, calcul de Un par variables glissantes, remplissage d’un tableau, rang d’un seuil

Idée directrice

Une suite est donnée par ses premiers termes et une relation. L’ordre de récurrence est le nombre de termes précédents dont dépend Un ; c’est aussi le nombre de valeurs initiales et le nombre de variables glissantes du calcul. On calcule quelques termes à la main pour fixer la relation, puis on programme : une boucle Pour qui calcule le nouveau terme puis décale les variables (sans tableau), ou qui remplit T[i] à partir de T[i−1], T[i−2]. Le type suit la relation : Entier si elle ne fait qu’additionner et multiplier, Réel dès qu’il y a une division. Quand on cherche un seuil plutôt qu’un rang donné, la boucle devient un Tant que.

Ce qui aide à reconnaître la démarche

« Soit la suite … définie par » ; « Quel est l’ordre de récurrence de la suite ? Justifier » ; « Déterminer … les valeurs correspondantes aux termes » ; « qui permet de calculer le terme Un » ; « remplir un tableau T … par les N premiers termes de la suite » ; « Compléter l’algorithme de la procédure »

Besoin d’un point de départ ? Voir la méthode

Ordre de récurrence = nombre de termes précédents dans la relation = nombre de valeurs initiales = nombre de variables glissantes.
Calculer deux ou trois termes à la main avant d’écrire l’algorithme : ils servent de trace de contrôle.
Variables glissantes : calculer u, puis décaler du plus ancien vers le plus récent (a ← b, puis b ← u).
Tableau : initialiser autant de cases qu’il y a de termes donnés, boucle Pour de l’ordre jusqu’à N − 1.
Type : Entier si la relation n’a ni division ni racine ; Réel sinon, et jamais Div pour une vraie division. Rang d’un seuil ou stationnarité : Tant que ou Répéter, pas Pour.

Les pièges à vérifier dans ta démarche

Décaler dans le mauvais ordre et perdre un terme. Faire démarrer la boucle à 1 alors que deux termes sont déjà connus, ou aller jusqu’à N au lieu de N − 1 (on sort du tableau et on range N + 1 termes). Oublier le cas n = 0 dans Terme. Donner l’ordre « 1 » parce que la relation « dépend de n » : c’est le nombre de termes précédents qui compte, pas l’indice. Oublier @ devant T dans Remplissage.

Sujet principal

Exercice (5 points) — dans l’esprit des sessions de contrôle 2016 et 2020 et de la principale 2026

5 questionsCorrigé masqué

Soit la suite U définie, pour tout entier naturel n, par :

\begin{cases} U_0 = 2,\quad U_1 = 1 \\ U_n = U_{n-1} + 2\,U_{n-2} \quad (n \ge 2) \end{cases}

Quel est l’ordre de récurrence de la suite U ? Justifier la réponse.
Recopier et compléter le tableau donné après les questions par les valeurs des termes $U_2$ à $U_6$ .
Calcul d’un terme :
1. Écrire l’algorithme d’une fonction Terme(n) qui retourne $U_n$ sans utiliser de tableau : à chaque tour, on calcule le nouveau terme à partir des deux précédents, puis on décale ces deux variables.
2. On définit, pour tout entier naturel n, $V_n = U_{n+1} / U_n$ . Quel doit être le type du résultat d’une fonction qui retourne $V_n$ ? Peut-on calculer $V_n$ avec l’opérateur Div ? Justifier à l’aide de $V_2$ .
On se propose de ranger les N premiers termes de la suite U dans un tableau T (2 ≤ N ≤ 30).
1. Déclarer un nouveau type TAB de 30 entiers.
2. Compléter l’algorithme de la procédure Remplissage donné après les questions.
Écrire l’algorithme d’une fonction Rang(B) qui retourne le plus petit rang n tel que $U_n \ge B$ , pour un entier B ≥ 3. Par exemple, Rang(100) retourne 7.

Tableau de la question 2 :

 U0 | U1 | U2 | U3 | U4 | U5 | U6
  2 |  1 | .. | .. | .. | .. | ..

Algorithme de la question 4.b :

Procédure Remplissage (N : Entier, ……)
DEBUT
    T[0] ← ……
    T[1] ← ……
    Pour i de …… à …… Faire
        T[i] ← ……
    Fin Pour
FIN

N.B. : N et B sont saisis dans le programme appelant. Chaque algorithme est accompagné de son tableau de déclaration des objets locaux.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : compter les termes précédents qui apparaissent dans la relation. $U_n$ se calcule à partir de $U_{n-1}$ et de $U_{n-2}$ : la suite est récurrente d’ordre 2. C’est pourquoi deux valeurs initiales, $U_0$ et $U_1$ , sont données.

2. $U_2 = U_1 + 2U_0 = 1 + 4 = 5$ ; $U_3 = 5 + 2 = 7$ ; $U_4 = 7 + 10 = 17$ ; $U_5 = 17 + 14 = 31$ ; $U_6 = 31 + 34 = 65$ .

 U0 | U1 | U2 | U3 | U4 | U5 | U6
  2 |  1 |  5 |  7 | 17 | 31 | 65

3.a Idée : a contient $U_{i-2}$ , b contient $U_{i-1}$ ; après le calcul de u, on décale dans cet ordre : a ← b, puis b ← u. Inverser ces deux affectations écraserait $U_{i-1}$ avant de le recopier.

Fonction Terme (n : Entier) : Entier
DEBUT
    Si n = 0 Alors
        Retourner 2
    Sinon
        a ← 2
        b ← 1
        Pour i de 2 à n Faire
            u ← b + 2 * a
            a ← b
            b ← u
        Fin Pour
        Retourner b
    FinSi
FIN

TDOL de Terme :

a, b — Type/Nature : Entier — les deux derniers termes calculés
u — Type/Nature : Entier — nouveau terme
i — Type/Nature : Entier — rang du terme calculé

Trace de Terme(5) : i = 2 : u = 5, a = 1, b = 5 ; i = 3 : u = 7, a = 5, b = 7 ; i = 4 : u = 17, a = 7, b = 17 ; i = 5 : u = 31, a = 17, b = 31. Retour $\boxed{31}$ . Pour n = 1, la boucle ne s’exécute pas et la fonction retourne 1. Si l’on écrit b ← u avant a ← b, U₃ devient 5 + 2 × 5 = 15 au lieu de 7.

3.b $V_2 = U_3 / U_2 = 7/5 = 1{,}4$ n’est pas un entier : le résultat doit être de type $\boxed{\text{Réel}}$ et le calcul utilise la division /. Avec Div, on obtiendrait 7 Div 5 = 1, le quotient entier, ce qui est faux.

4.a Tableau de déclaration des nouveaux types : TAB = Tableau de 30 Entiers (cases 0 à 29).

4.b Idée : T est modifié, il est passé par référence (@) ; les deux premières cases reçoivent les termes initiaux, la boucle commence donc à 2 et s’arrête à N − 1 (N termes, de $U_0$ à $U_{N-1}$ ).

Procédure Remplissage (N : Entier, @T : TAB)
DEBUT
    T[0] ← 2
    T[1] ← 1
    Pour i de 2 à N - 1 Faire
        T[i] ← T[i - 1] + 2 * T[i - 2]
    Fin Pour
FIN

TDOL : i — Entier. Pour N = 8, T contient 2, 1, 5, 7, 17, 31, 65, 127. Le tableau garde tous les termes, alors que Terme n’en garde que deux.

5. Idée : le nombre de tours dépend de B et non d’un rang connu : Tant que le terme courant est inférieur à B, on calcule le suivant en comptant les rangs. Comme B ≥ 3, $U_0 = 2$ et $U_1 = 1$ sont inférieurs à B : on peut démarrer au rang 1.

Fonction Rang (B : Entier) : Entier
DEBUT
    n ← 1
    a ← 2
    b ← 1
    Tant que b < B Faire
        u ← b + 2 * a
        a ← b
        b ← u
        n ← n + 1
    Fin Tant que
    Retourner n
FIN

TDOL : n, a, b, u — Entier — rang courant, deux derniers termes, nouveau terme. Pour B = 100 : b prend les valeurs 5, 7, 17, 31, 65, 127 aux rangs 2 à 7 ; 127 ≥ 100 arrête la boucle, retour $\boxed{7}$ .

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : $S_n = S_{n-1} + 3$ , remplissage d’un tableau puis recherche dichotomique (principale 2026, sections Mathématiques, Sciences expérimentales et Sciences techniques) ; $U_n = 1 + 1/U_{n-1}$ : choix parmi des séquences proposées et en-tête de type réel (principale 2019) ; suite de Kaprekar rangée dans un tableau jusqu’à stationnarité (principale 2015) ; ordre de récurrence puis module Suite avec division (contrôle 2020) ; en section Sciences de l’informatique : suite de Perrin d’ordre 3 et propriété de primalité (contrôle 2016), termes de Fibonacci (principales 2016 et 2018), suite de Thue-Morse par deux méthodes (contrôle 2021), ordre de la suite de Héron (principale 2022), Fibonacci et suite de Stern à partir du triangle de Pascal (principale 2026).

Exercices d'entraînement — une nuance à la fois

1 Drill RA-L.1 — récurrence d’ordre 3 : trois variables glissantes, termes jusqu’à une borne

Entraînement 01 / 05

Drill RA-L.1 — récurrence d’ordre 3 : trois variables glissantes, termes jusqu’à une borne

4 questionsCorrigé masqué

Soit la suite U définie par $U_0 = U_1 = U_2 = 1$ et $U_n = U_{n-1} + U_{n-3}$ pour tout entier naturel n ≥ 3.

Quel est l’ordre de récurrence de la suite U ? Justifier.
Calculer les termes $U_3$ à $U_8$ .
Écrire l’algorithme d’une fonction Terme3(n) qui retourne $U_n$ en utilisant trois variables glissantes. Préciser l’ordre des affectations de décalage.
Écrire l’algorithme d’un module AfficheBorne(B) qui affiche tous les termes de la suite inférieurs ou égaux à B (B ≥ 1). Pour B = 50, elle affiche 1 1 1 2 3 4 6 9 13 19 28 41.

Voir la correction commentéeAprès avoir posé votre démarche

1. $U_n$ dépend de $U_{n-1}$ et de $U_{n-3}$ : le terme le plus ancien utilisé est trois rangs plus tôt, l’ordre est 3 (d’où trois valeurs initiales), même si $U_{n-2}$ n’apparaît pas dans la relation.

2. $U_3 = 1 + 1 = 2$ , $U_4 = 2 + 1 = 3$ , $U_5 = 3 + 1 = 4$ , $U_6 = 4 + 2 = 6$ , $U_7 = 6 + 3 = 9$ , $U_8 = 9 + 4 = 13$ .

3. Idée : a, b, c contiennent $U_{i-3}$ , $U_{i-2}$ , $U_{i-1}$ ; on calcule u = c + a puis on décale du plus ancien vers le plus récent : a ← b, b ← c, c ← u.

Fonction Terme3 (n : Entier) : Entier
DEBUT
    a ← 1
    b ← 1
    c ← 1
    Pour i de 3 à n Faire
        u ← c + a
        a ← b
        b ← c
        c ← u
    Fin Pour
    Retourner c
FIN

TDOL : a, b, c, u, i — Type/Nature : Entier — trois derniers termes, nouveau terme, rang. Pour n ≤ 2 la boucle ne tourne pas et la fonction retourne 1, ce qui est juste. Écrire c ← u avant b ← c perdrait $U_{i-1}$ .

4. Idée : le nombre de termes affichés dépend de B : on calcule le terme suivant et on continue tant qu’il ne dépasse pas B.

Procédure AfficheBorne (B : Entier)
DEBUT
    Ecrire(1, " ", 1, " ", 1)
    a ← 1
    b ← 1
    c ← 1
    u ← c + a
    Tant que u ≤ B Faire
        Ecrire(" ", u)
        a ← b
        b ← c
        c ← u
        u ← c + a
    Fin Tant que
FIN

TDOL : a, b, c, u — Entier. Pour B = 50, les termes 2, 3, 4, 6, 9, 13, 19, 28, 41 sont affichés ; le suivant, 60, arrête la boucle.

2 Drill RA-L.2 — terme réel : choisir la bonne séquence parmi trois (Div, borne de boucle), en-tête de type Réel

Entraînement 02 / 05

Drill RA-L.2 — terme réel : choisir la bonne séquence parmi trois (Div, borne de boucle), en-tête de type Réel

4 questionsCorrigé masqué

Soit la suite U définie par $U_0 = 1$ et $U_n = \dfrac{1}{1 + U_{n-1}}$ pour tout entier n ≥ 1.

Quel est l’ordre de récurrence de la suite U ?
Calculer $U_1$ , $U_2$ , $U_3$ et $U_4$ sous forme de fractions, puis en valeur décimale arrondie au millième.
Les trois séquences suivantes prétendent calculer $U_n$ (n ≥ 0 est déjà saisi). Pour chacune, dire si elle est correcte ; sinon, expliquer l’erreur.
1. Séquence A : u ← 1, puis Pour i de 1 à n Faire u ← 1 Div (1 + u).
2. Séquence B : u ← 1, puis Pour i de 0 à n Faire u ← 1 / (1 + u).
3. Séquence C : u ← 1, puis Pour i de 1 à n Faire u ← 1 / (1 + u).
Écrire l’en-tête et l’algorithme d’une fonction Suite(n) qui retourne $U_n$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. $U_n$ ne dépend que de $U_{n-1}$ : ordre 1, une seule valeur initiale.

2. $U_1 = \frac{1}{2} = 0{,}5$ ; $U_2 = \frac{1}{1 + 1/2} = \frac{2}{3} \approx 0{,}667$ ; $U_3 = \frac{3}{5} = 0{,}6$ ; $U_4 = \frac{5}{8} = 0{,}625$ .

3. Idée : exécuter chaque séquence pour une petite valeur de n et comparer avec la question 2.

A est fausse : Div est la division entière. 1 Div 2 = 0, puis 1 Div 1 = 1, puis 0… la séquence ne produit jamais 0,5 ni 0,667.
B est fausse : la boucle fait n + 1 tours et retourne $U_{n+1}$ . Pour n = 3, elle donne 0,625 au lieu de 0,6.
C est correcte : n tours à partir de $U_0$ ; pour n = 0 aucun tour, la valeur 1 est bien $U_0$ .

4. Le résultat est un quotient non entier : type Réel.

Fonction Suite (n : Entier) : Réel
DEBUT
    u ← 1
    Pour i de 1 à n Faire
        u ← 1 / (1 + u)
    Fin Pour
    Retourner u
FIN

TDOL : u — Type/Nature : Réel — terme courant ; i — Type/Nature : Entier — rang. Déclarer u entier tronquerait chaque terme, comme la séquence A.

3 Drill RA-L.3 — suite générée jusqu’à stationnarité : routine de Kaprekar à trois chiffres rangée dans un tableau

Entraînement 03 / 05

Drill RA-L.3 — suite générée jusqu’à stationnarité : routine de Kaprekar à trois chiffres rangée dans un tableau

4 questionsCorrigé masqué

Soit $U_0$ un entier de trois chiffres (100 ≤ $U_0$ ≤ 999) dont les chiffres ne sont pas tous égaux. Avec les trois chiffres de $U_i$ — en comptant les zéros : 99 se lit 099 —, on forme le plus grand entier G et le plus petit entier P, et l’on pose $U_{i+1} = G - P$ . On admet que la suite devient stationnaire (deux termes consécutifs égaux) après au plus 7 soustractions.

Exemple : pour $U_0 = 352$ : 532 − 235 = 297 ; 972 − 279 = 693 ; 963 − 369 = 594 ; 954 − 459 = 495 ; 954 − 459 = 495 : la suite est stationnaire à 495.

Donner les termes de la suite pour $U_0 = 100$ .
Écrire l’algorithme d’une fonction Diff(x) qui retourne G − P pour un entier x de 0 à 999, en extrayant ses trois chiffres par Div et Mod.
Écrire l’algorithme d’une procédure Kaprekar(U0, T, nb) qui range dans un tableau T les termes de la suite, de $U_0$ jusqu’au premier terme égal à son prédécesseur, et calcule leur nombre nb.
Justifier l’emploi de Répéter plutôt que de Pour, et la taille de 8 cases pour T.

Voir la correction commentéeAprès avoir posé votre démarche

1. 100 → 100 − 001 = 99 (lu 099) → 990 − 099 = 891 → 981 − 189 = 792 → 972 − 279 = 693 → 963 − 369 = 594 → 954 − 459 = 495 → 495. Termes : 100, 99, 891, 792, 693, 594, 495, 495.

2. Idée : x Div 100, (x Div 10) Mod 10 et x Mod 10 donnent les trois chiffres, zéros compris ; on les range par permutations pour avoir a ≥ b ≥ c, puis G = 100a + 10b + c et P = 100c + 10b + a.

Fonction Diff (x : Entier) : Entier
DEBUT
    a ← x Div 100
    b ← (x Div 10) Mod 10
    c ← x Mod 10
    Si a < b Alors
        aux ← a
        a ← b
        b ← aux
    FinSi
    Si a < c Alors
        aux ← a
        a ← c
        c ← aux
    FinSi
    Si b < c Alors
        aux ← b
        b ← c
        c ← aux
    FinSi
    Retourner (100*a + 10*b + c)
              - (100*c + 10*b + a)
FIN

TDOL : a, b, c, aux — Type/Nature : Entier — les trois chiffres ordonnés, variable d’échange. Remarque : G − P = 99 × (a − c), ce qui explique que tous les termes après $U_0$ soient des multiples de 99.

Procédure Kaprekar (U0 : Entier, @T : TAB,
                    @nb : Entier)
DEBUT
    T[0] ← U0
    nb ← 1
    Répéter
        T[nb] ← Diff(T[nb - 1])
        nb ← nb + 1
    Jusqu'à T[nb - 1] = T[nb - 2]
FIN

TDOL : Diff — Fonction. Nouveau type : TAB = Tableau de 8 Entiers. Pour $U_0 = 352$ , T = [352, 297, 693, 594, 495, 495] et nb = 6.

4. Le nombre de termes n’est pas connu d’avance : il dépend de $U_0$ , d’où une boucle conditionnelle arrêtée par la stationnarité ; Répéter convient car il faut au moins une soustraction pour comparer deux termes. Avec au plus 7 soustractions, T contient au plus 1 + 7 = 8 termes (le cas de 100).

4 Drill RA-L.4 — (section Sciences de l’informatique) une même suite par deux méthodes : construction de chaînes et calcul arithmétique du terme

Entraînement 04 / 05

Drill RA-L.4 — (section Sciences de l’informatique) une même suite par deux méthodes : construction de chaînes et calcul arithmétique du terme

6 questionsCorrigé masqué

On plie k fois une bande de papier en deux, toujours dans le même sens, puis on la déplie : la suite des plis, notée 1 (pli vers le haut) ou 0 (pli vers le bas), forme une chaîne binaire $S_k$ de $2^k - 1$ caractères. Deux méthodes permettent de l’obtenir.

Méthode 1 (construction) : $S_1$ = "1" et $S_{k+1} = S_k$ + "1" + R( $S_k$ ), où R(ch) est la chaîne obtenue en renversant ch puis en remplaçant chaque "0" par "1" et chaque "1" par "0". Ainsi $S_2$ = "110" et $S_3$ = "1101100".
Méthode 2 (arithmétique) : le i-ème caractère (i ≥ 1) s’obtient en remplaçant i par i Div 2 tant que i Mod 2 = 0 ; si le nombre impair m obtenu vérifie m Mod 4 = 1, le caractère est "1", sinon "0". Par exemple i = 6 donne m = 3 et le caractère "0".

Donner $S_4$ par la méthode 1, puis retrouver ses 10ᵉ et 12ᵉ caractères par la méthode 2.
Écrire l’algorithme d’une fonction Methode1(k) qui retourne $S_k$ selon la méthode 1.
Écrire l’algorithme d’une fonction Methode2(k) qui retourne $S_k$ selon la méthode 2.
Une chaîne contenant au plus 255 caractères, quelle est la plus grande valeur de k autorisée ?

Voir la correction commentéeAprès avoir posé votre démarche

1. R("1101100") : renversée "0011011", complémentée "1100100". $S_4$ = "1101100" + "1" + "1100100" = "110110011100100" (15 caractères). Méthode 2 : i = 10 → 5, 5 Mod 4 = 1 : "1" ; i = 12 → 6 → 3, 3 Mod 4 = 3 : "0". Ce sont bien les 10ᵉ et 12ᵉ caractères de $S_4$ .

2. Idée : construire R(ch) caractère par caractère en parcourant ch de la fin vers le début.

Fonction Methode1 (k : Entier) : Chaîne
DEBUT
    s ← "1"
    Pour j de 2 à k Faire
        r ← ""
        L ← Long(s)
        Pour i de L - 1 à 0 (Pas = -1) Faire
            Si s[i] = "1" Alors
                r ← r + "0"
            Sinon
                r ← r + "1"
            FinSi
        Fin Pour
        s ← s + "1" + r
    Fin Pour
    Retourner s
FIN

TDOL : s, r — Type/Nature : Chaîne — terme courant, chaîne R(s) ; i, j, L — Type/Nature : Entier.

3. Idée : chaque caractère se calcule indépendamment des autres, à partir de son rang seul.

Fonction Methode2 (k : Entier) : Chaîne
DEBUT
    s ← ""
    L ← 1
    Pour j de 1 à k Faire
        L ← L * 2
    Fin Pour
    Pour i de 1 à L - 1 Faire
        m ← i
        Tant que m Mod 2 = 0 Faire
            m ← m Div 2
        Fin Tant que
        Si m Mod 4 = 1 Alors
            s ← s + "1"
        Sinon
            s ← s + "0"
        FinSi
    Fin Pour
    Retourner s
FIN

TDOL : s — Chaîne ; L, i, j, m — Entier — $2^k$ , rang du caractère, compteur, partie impaire de i.

4. La longueur vérifie $L_{k+1} = 2L_k + 1$ avec $L_1 = 1$ , donc $L_k = 2^k - 1$ . $2^8 - 1 = 255$ et $2^9 - 1 = 511$ : $\boxed{k \le 8}$ .

5 Drill RA-L.5 — (section Sciences de l’informatique) primalité par une propriété de suite : suite de Lucas calculée modulo n

Entraînement 05 / 05

Drill RA-L.5 — (section Sciences de l’informatique) primalité par une propriété de suite : suite de Lucas calculée modulo n

4 questionsCorrigé masqué

La suite de Lucas est définie par $L_0 = 2$ , $L_1 = 1$ et $L_n = L_{n-1} + L_{n-2}$ pour n ≥ 2. On admet la propriété suivante : « pour tout entier n tel que 2 ≤ n ≤ 704, n est premier si et seulement si $L_n$ mod n = 1 » (705 = 3 × 5 × 47 est le premier entier composé qui la met en défaut).

Calculer $L_2$ à $L_9$ , puis appliquer la propriété à n = 7 et à n = 9.
Sachant que $L_{45}$ = 2 537 720 636 dépasse la plus grande valeur du type Entier sur 32 bits (2 147 483 647), expliquer comment calculer $L_n$ mod n sans jamais manipuler $L_n$ .
Écrire l’algorithme d’une fonction LucasMod(n) qui retourne $L_n$ mod n en ne conservant que les restes modulo n de deux termes glissants. Donner la trace pour n = 9.
En utilisant LucasMod, écrire l’algorithme d’un module qui affiche les nombres premiers compris entre a et b (2 ≤ a ≤ b ≤ 704, déjà saisis). Pour a = 50 et b = 70 : 53, 59, 61, 67.

Voir la correction commentéeAprès avoir posé votre démarche

1. 3, 4, 7, 11, 18, 29, 47, 76. $L_7 = 29$ et 29 mod 7 = 1 : 7 est premier. $L_9 = 76$ et 76 mod 9 = 4 ≠ 1 : 9 n’est pas premier.

2. Le reste d’une somme ne dépend que des restes des termes : $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ . On garde donc seulement les restes modulo n des deux derniers termes ; ils restent inférieurs à n et leur somme à 2n.

3. Idée : a et b contiennent les restes modulo n de $L_{i-2}$ et $L_{i-1}$ ; on calcule le nouveau reste, puis on décale a ← b, b ← u.

Fonction LucasMod (n : Entier) : Entier
DEBUT
    a ← 2 Mod n
    b ← 1 Mod n
    Pour i de 2 à n Faire
        u ← (a + b) Mod n
        a ← b
        b ← u
    Fin Pour
    Retourner b
FIN

TDOL : a, b, u, i — Type/Nature : Entier — restes des deux derniers termes, nouveau reste, rang. Trace pour n = 9 : les valeurs successives de b pour i = 2 à 9 sont 3, 4, 7, 2, 0, 2, 2, 4 ; retour $\boxed{4}$ , soit 76 mod 9. Écrire 2 Mod n prépare le cas n = 2 : a = 0, b = 1, puis b = 1, et 2 est bien reconnu premier.

Procédure Premiers_Lucas (a, b : Entier)
DEBUT
    Pour n de a à b Faire
        Si LucasMod(n) = 1 Alors
            Ecrire(n)
        FinSi
    Fin Pour
FIN

TDOL : n — Entier ; LucasMod — Fonction. La borne b ≤ 704 fait partie de l’énoncé : au-delà, le test n’est plus une preuve de primalité.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Suite récurrente : ordre de récurrence, premiers termes, calcul de Un par variables glissantes, remplissage d’un tableau, rang d’un seuil

Exercice (5 points) — dans l’esprit des sessions de contrôle 2016 et 2020 et de la principale 2026

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Drill RA-L.1 — récurrence d’ordre 3 : trois variables glissantes, termes jusqu’à une borne

Drill RA-L.2 — terme réel : choisir la bonne séquence parmi trois (Div, borne de boucle), en-tête de type Réel

Drill RA-L.3 — suite générée jusqu’à stationnarité : routine de Kaprekar à trois chiffres rangée dans un tableau

Drill RA-L.4 — (section Sciences de l’informatique) une même suite par deux méthodes : construction de chaînes et calcul arithmétique du terme

Drill RA-L.5 — (section Sciences de l’informatique) primalité par une propriété de suite : suite de Lucas calculée modulo n

Relier ce raisonnement au bac