Nombre défini par l’énoncé : fonction de test construite sur une brique (chiffres, facteurs premiers), N premiers, filtrage d’un tableau et affichage groupé

À tout entier naturel non nul n, on associe la somme des carrés de ses chiffres, notée SC(n). Par exemple SC(68) = 6² + 8² = 100. En remplaçant n par SC(n) et en recommençant, on admet qu’on obtient toujours, après un nombre fini d’étapes, soit la valeur 1, soit la valeur 4 (qui fait ensuite tourner indéfiniment le cycle 4, 16, 37, 58, 89, 145, 42, 20, 4). L’entier n est dit heureux si l’on aboutit à 1.

Exemples : 19 est heureux car 19 → 82 → 68 → 100 → 1 ; 15 n’est pas heureux car 15 → 26 → 40 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

1. Montrer, en écrivant les valeurs successives, que 7 est heureux.
2. Écrire l’algorithme d’une fonction SC(n) qui retourne la somme des carrés des chiffres de n.
3. En utilisant SC, écrire l’algorithme d’une fonction booléenne Heureux(n). Expliquer pourquoi son exécution se termine toujours.
4. Écrire l’algorithme d’un module qui affiche les N premiers entiers heureux (N est déjà saisi). Pour N = 8, on obtient 1, 7, 10, 13, 19, 23, 28, 31.

Un entier p est dit premier de triplet si les trois entiers p, p + 2 et p + 6 sont tous premiers. Exemples : 11 est premier de triplet car 11, 13 et 17 sont premiers ; 23 ne l’est pas car 25 n’est pas premier ; 9 ne l’est pas car 9 n’est pas premier.

1. Écrire l’algorithme d’une fonction booléenne Premier(n) qui vérifie si un entier n est premier (un nombre premier admet exactement deux diviseurs, 1 et lui-même ; 0 et 1 ne sont pas premiers).
2. En utilisant Premier, écrire l’algorithme d’une fonction booléenne Triplet(p).
3. Écrire l’algorithme d’un module Ranger(T, n, nb) qui place en tête d’un tableau T de n entiers, en permutant, les entiers premiers de triplet, dans l’ordre où ils apparaissent, et calcule leur nombre nb.
4. Donner le contenu de T et la valeur de nb après l’exécution de Ranger(T, 8, nb) pour T = [9, 11, 23, 17, 29, 41, 15, 5].

Un entier n ≥ 2 est dit puissant si, pour tout nombre premier p qui divise n, p² divise aussi n : dans la décomposition de n en facteurs premiers, chaque facteur apparaît avec un exposant au moins égal à 2. Exemples : 72 = 2³ × 3² et 500 = 2² × 5³ sont puissants ; 12 = 2² × 3 et 90 = 2 × 3² × 5 ne le sont pas.

1. Décomposer 1800 en produit de facteurs premiers et dire s’il est puissant.
2. Écrire l’algorithme d’une fonction booléenne Puissant(n) qui vérifie si n est puissant, en calculant l’exposant de chaque facteur premier de n.
3. Écrire l’algorithme d’un module qui affiche les N premiers entiers puissants (N déjà saisi). Pour N = 10, on obtient 4, 8, 9, 16, 25, 27, 32, 36, 49, 64.

Théorème de Wilson : un entier p ≥ 2 est premier si et seulement si (p − 1)! mod p = p − 1. Exemples : 4! = 24 et 24 mod 5 = 4, donc 5 est premier ; 5! = 120 et 120 mod 6 = 0 ≠ 5, donc 6 n’est pas premier.

1. On suppose que le type Entier est codé sur 32 bits (plus grande valeur 2 147 483 647). Sachant que 12! = 479 001 600 et 13! = 6 227 020 800, expliquer pourquoi on ne peut pas calculer (p − 1)! puis son reste dès que p ≥ 14.
2. Écrire l’algorithme d’une fonction FactMod(n, m) qui retourne n! mod m en réduisant modulo m après chaque produit (f ← (f × i) mod m). Donner les valeurs successives de f pour FactMod(6, 7).
3. En utilisant FactMod, écrire l’algorithme d’une fonction booléenne Wilson(p) qui vérifie si p est premier.
4. Écrire l’algorithme d’un module qui affiche, à l’aide de Wilson, les nombres premiers compris entre a et b (2 ≤ a ≤ b ≤ 30000, déjà saisis). Pour a = 20 et b = 40, on obtient 23, 29, 31, 37.

Un entier naturel non nul est dit bipalindrome si son écriture décimale et son écriture binaire sont toutes deux des palindromes (elles se lisent de la même façon dans les deux sens). Exemples : 585 est bipalindrome car 585 = $(1001001001)_2$ ; 33 = $(100001)_2$ l’est aussi. 11 ne l’est pas : il est palindrome en base 10 mais 11 = $(1011)_2$ ; 44 non plus, car 44 = $(101100)_2$.

1. Donner l’écriture binaire de 99 et dire si 99 est bipalindrome.
2. Écrire l’algorithme d’une fonction Binaire(n) qui retourne, sous forme de chaîne, l’écriture binaire de n obtenue par divisions successives par 2.
3. Écrire l’algorithme d’une fonction booléenne Palindrome(ch).
4. Écrire l’algorithme d’une procédure qui affiche tous les bipalindromes inférieurs ou égaux à M (1 ≤ M ≤ 30000, déjà saisi). Pour M = 1000, on obtient 1, 3, 5, 7, 9, 33, 99, 313, 585, 717.

Un entier naturel non nul x est dit triangulaire s’il existe un entier n ≥ 1 tel que x = n(n + 1)/2, et pentagonal s’il existe un entier k ≥ 1 tel que x = k(3k − 1)/2. On admet que :

• x est triangulaire si et seulement si 8x + 1 est le carré d’un entier r, et alors n = (r − 1)/2 ;
• x est pentagonal si et seulement si 24x + 1 est le carré d’un entier r tel que r + 1 soit divisible par 6, et alors k = (r + 1)/6.

Exemples : 8 × 21 + 1 = 169 = 13², donc 21 est triangulaire (n = 6) ; 24 × 21 + 1 = 505 n’est pas un carré, 21 n’est pas pentagonal. 24 × 22 + 1 = 529 = 23² et 24 est divisible par 6, donc 22 est pentagonal (k = 4). 24 × 7 + 1 = 169 = 13², mais 14 n’est pas divisible par 6 : 7 n’est pas pentagonal.

1. Écrire l’algorithme d’une fonction Triang(x) qui retourne n si x est triangulaire et 0 sinon (on pourra utiliser Ent et RacineCarré).
2. Écrire l’algorithme d’une fonction Pent(x) qui retourne k si x est pentagonal et 0 sinon.
3. Vérifier que 210 est à la fois triangulaire et pentagonal, en donnant n et k.
4. En faisant appel aux deux fonctions, écrire l’algorithme d’un module Remplir(T, m) qui remplit un tableau T d’enregistrements par les m premiers entiers à la fois triangulaires et pentagonaux ; chaque enregistrement contient le nombre x, l’entier n et l’entier k. Pour m = 3, on obtient (1, 1, 1), (210, 20, 12) et (40755, 285, 165). m est déjà saisi (1 ≤ m ≤ 3) ; déclarer les nouveaux types.