Exercice 2 — Algorithme de Prabekhar

Sujet

.On considère l'algorithme suivant

Variables : \(n, r, q, d, p\) des entiers naturels
Début
    Lire \(n\)
    \(d \leftarrow n\)
    \(p \leftarrow 0\)
    Tant que \(d \neq 0\) faire
        \(r \leftarrow\) reste de la division euclidienne de \(d\) par 10
        \(q \leftarrow\) quotient de la division euclidienne de \(d\) par 10
        \(d \leftarrow q\)
        \(p \leftarrow p+r^{2}\)
    Fin Tq
    Afficher \(p\)
Fin

Si \(p\) est le résultat de l'algorithme appliqué à \(n\), on notera \(n \rightarrow p\). On dira que \(p\) est l'image de \(n\) ou que \(n\) est un antécédent de \(p\).

Partie A - Description de l'algorithme

1. a) Vérifier que \(157 \rightarrow 75\), puis que \(75 \rightarrow 74\), puis que \(74 \rightarrow 65\).

La suite \(157 \rightarrow 75 \rightarrow 74 \rightarrow 65 \ldots\) sera appelé la trajectoire du nombre 157 .
b) Déterminer l'image de 12345 .
c) Décrire simplement par une phrase ce que fait cet algorithme.
2. a) Montrer que tout entier naturel non nul \(p\) possède une infinité d'antécédents.
b) Montrer que 157 ne peut avoir d'antécédent de trois chiffres.

Trouver un nombre d'au maximum quatre chiffres qui soit un antécédent de 157 .
3. soits un entier naturel donné.
a) Représenter graphiquement les points de coordonnées entières, positives et de somme \(s\).
b) Trouver le(s) nombre(s) de deux chiffres dont la somme des chiffres est \(s\) et ayant une image minimum.

Partie B - Trajectoire des nombres à deux chiffres

On a représenté les trajectoires des nombres de 1 à 9