Les scripts du chapitre

Tous les scripts du cours (section 6) et de la feuille d’exercices (partie VI, exercices 28 à 30), rassemblés, exécutés et vérifiés. Chaque bloc se copie tel quel dans votre éditeur ; les lignes print ajoutées pour rendre la sortie visible sont signalées par un commentaire.

1. Variables et types (cours, § 6.1)

Les quatre types de base de l’année : entier, flottant, booléen (en écho à Boole) et chaîne de caractères.

n = 41              # int
x = 1.5             # float
premier = True      # bool : Boole, 1 et 0, VRAI et FAUX
nom = "Euler"       # str

Sortie : aucune. Quatre affectations, la machine range les étiquettes en silence.

2. Tests et connecteurs (cours, § 6.2)

L’instruction conditionnelle, avec les connecteurs du chapitre : and, or, not.

n = 41                        # la valeur du script 1

if n % 2 == 0 and n > 2:      # n pair ET n > 2
    print("pair, superieur a 2")
elif not (n % 2 == 0):        # negation : n impair
    print("impair")
else:
    print("n vaut 2")

Sortie :

impair

3. Les lois de De Morgan à la machine (cours, § 6.2, note de marge)

La note de marge du cours propose de vérifier not (a and b) == ((not a) or (not b)) sur les quatre valeurs possibles du couple : le voici en boucle.

for a in (True, False):
    for b in (True, False):
        print(a, b, (not (a and b)) == ((not a) or (not b)))

Sortie :

True True True
True False True
False True True
False False True

Quatre lignes, quatre True en dernière colonne : la première loi de De Morgan est vraie dans tous les cas.

4. Boucles for et while (cours, § 6.3)

La boucle for pour les sommes (ici la somme des carrés de 1 à 100), la boucle while pour les seuils (le premier $n$ tel que $2^n \geqslant 10^6$).

S = 0
for k in range(1, 101):       # k parcourt 1, 2, ..., 100
    S = S + k**2              # somme des carres

n = 1
while 2**n < 10**6:           # tant que 2^n < 1 000 000
    n = n + 1                 # a la sortie : 2^n >= 10^6

print(S)                      # ajoute pour l'affichage
print(n)                      # ajoute pour l'affichage

Sortie :

338350
20

Et en effet $2^{20} = 1\,048\,576 \geqslant 10^6$, alors que $2^{19} = 524\,288$ ne suffit pas.

5. est_premier, la version naïve (cours, § 6.4 et exercice 28)

La première brique de l’année : tester tous les diviseurs de $2$ à $n - 1$. C’est aussi la version que l’exercice 28 demande de réécrire de mémoire.

def est_premier(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False      # diviseur trouve
    return True               # aucun diviseur

print(est_premier(41))        # ajoute pour l'affichage
print(est_premier(40))        # ajoute pour l'affichage
print(est_premier(1))         # ajoute pour l'affichage

Sortie :

True
False
False

6. Listes, all et any : les quantificateurs retrouvés (cours, § 6.5)

all est un $\forall$ exécutable, any un $\exists$. La liste teste les valeurs de $n^2 - n$ pour $n$ de $0$ à $99$.

valeurs = [n**2 - n for n in range(100)]     # n^2 - n

print(all(v % 2 == 0 for v in valeurs))   # forall : ajoute pour l'affichage
print(any(v > 9000 for v in valeurs))     # exists : ajoute pour l'affichage

Sortie :

True
True

Le all dit vrai car pour tout $n \in \mathbb{N}$, l’entier $n^2 - n = n(n-1)$ est pair ; le any dit vrai car $99^2 - 99 = 9\,702 > 9\,000$.

7. La machine à contre-exemples et le polynôme d’Euler (cours, § 6.6)

Le script final du cours : chercher un témoin qui réfute une conjecture. Le polynôme $n^2 + n + 41$ d’Euler, premier de $n = 0$ à $n = 39$, tombe en une milliseconde. Nécessite la fonction est_premier du script 5.

def contre_exemple(P, N):
    """Cherche n < N tel que P(n) soit fausse."""
    for n in range(N):
        if not P(n):
            return n          # temoin : refutee !
    return None               # aucun temoin trouve

# Le polynome d'Euler tombe en une milliseconde :
print(contre_exemple(lambda n: est_premier(n**2 + n + 41), 100))   # ajoute pour l'affichage

Sortie :

40

Le témoin est $n = 40$ : en effet $40^2 + 40 + 41 = 41^2$, qui n’est pas premier.

8. est_premier, version racine carrée (exercice 28, question 2)

L’exercice démontre (par l’absurde) que tout entier non premier admet un diviseur non trivial inférieur ou égal à $\sqrt{n}$ : il suffit donc de tester jusqu’à $\sqrt{n}$. Pour $n = 10\,007$, une centaine de tests au lieu d’environ dix mille.

def est_premier_v2(n):
    if n < 2:
        return False
    for d in range(2, int(n**0.5) + 1):
        if n % d == 0:
            return False
    return True

print(est_premier_v2(10007))  # ajoute pour l'affichage
print(int(10007**0.5))        # dernier diviseur teste : ajoute pour l'affichage

Sortie :

True
100

$10\,007$ est premier, et la boucle s’est arrêtée à $d = 100$ au lieu de $10\,006$.

9. est_premier, version all (exercice 28, question 3)

La version en une ligne de l’énoncé : son test traduit mot à mot « $n \geqslant 2$ et pour tout $d$ compris entre $2$ et $n - 1$, $d$ ne divise pas $n$ », c’est-à-dire la définition de la primalité.

def est_premier(n):
    return n >= 2 and all(n % d != 0 for d in range(2, n))

print(est_premier(41), est_premier(40))   # ajoute pour l'affichage

Sortie :

True False

10. Le plus petit nombre premier au-delà de 1000 (exercice 28, question 4)

La question 4 demande d’utiliser l’une des trois versions pour trouver le plus petit premier strictement supérieur à $1\,000$. Nécessite est_premier_v2 du script 8 (ou l’une des deux autres versions).

n = 1001
while not est_premier_v2(n):
    n = n + 1
print(n)

Sortie :

1009

Conforme au corrigé : $1\,001$, $1\,003$ et $1\,007$ sont composés ($1\,001 = 7 \times 11 \times 13$), et $1\,009$ est premier.

11. Trois vérifications en une ligne (exercice 29, questions 2 et 3)

Python calcule sur des entiers exacts de taille arbitraire : les trois contre-exemples historiques du chapitre se vérifient instantanément, là où une calculatrice à dix chiffres arrondit et ne prouve rien.

# Euler contre Fermat (1732) : 641 divise F5 = 2^32 + 1
print(641 * 6700417 == 2**32 + 1)

# Lander et Parkin contre Euler (1966)
print(27**5 + 84**5 + 110**5 + 133**5 == 144**5)

# Roger Frye (1988), plus petit exposant connu
print(95800**4 + 217519**4 + 414560**4 == 422481**4)

Sortie :

True
True
True

12. La machine face à $4^n + 5$ (exercice 29, question 1)

L’exercice pose P = lambda n: (4**n + 5) % 3 == 0 et affirme que contre_exemple(P, 10**6) renvoie None. Le script ci-dessous reproduit l’expérience avec $N = 10\,000$ : au-delà, les entiers $4^n$ deviennent gigantesques (plus de six cent mille chiffres pour $n$ proche du million) et l’attente est longue, sans que la conclusion change d’un iota. Nécessite contre_exemple du script 7.

P = lambda n: (4**n + 5) % 3 == 0
print(contre_exemple(P, 10_000))   # ajoute pour l'affichage

Sortie :

None

Aucun témoin parmi les dix mille premiers entiers. Rappel de la maxime du chapitre : ce None ne démontre rien, c’est votre récurrence de l’exercice 16 qui prouve l’énoncé pour tout $n$. L’ordinateur réfute ; seule la démonstration prouve.

13. Le vol du planeur de Syracuse (exercice 30)

Les trois fonctions du corrigé : la liste des termes de la suite de Syracuse jusqu’à $1$, puis le temps de vol et l’altitude maximale. La boucle while ne termine que si le vol atteint $1$ : faire tourner ce programme, c’est déjà parier sur la conjecture.

def vol(a):
    termes = [a]
    while termes[-1] != 1:
        u = termes[-1]
        if u % 2 == 0:
            termes.append(u // 2)
        else:
            termes.append(3*u + 1)
    return termes

def temps_de_vol(a):
    return len(vol(a)) - 1

def altitude_max(a):
    return max(vol(a))

print(vol(6))                 # ajoute pour l'affichage
print(temps_de_vol(27))       # ajoute pour l'affichage
print(altitude_max(27))       # ajoute pour l'affichage

Sortie :

[6, 3, 10, 5, 16, 8, 4, 2, 1]
111
9232

Le vol depuis $6$ est celui calculé à la main dans l’exercice ; le départ $a = 27$ confirme les valeurs de l’énoncé : temps de vol $111$, altitude maximale $9\,232$.