1. Les structures I#

1.1. Exercice 1#

La suite de Fibonacci est définie par

\[ x_0 = 0, \quad x_1 = 1, \quad x_{n+1} = x_n + x_{n-1}, \quad\text{pour } n\geq1.\]

Questions

  1. Ecrivez les 15 premiers termes de la suite de Fibonacci. Vous pouvez stocker tous les termes dans une liste.

  2. Calculez la somme de tous les termes impairs inférieurs à \(4000000\). Veillez à ne pas stocker tous les termes pour cette question…

Hide code cell source 
x = [0, 1]
for _ in range(15-2):
    x.append(x[-1] + x[-2])
print(x)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Hide code cell source 
xold, x = 0, 1
S = 0
while x <= 4000000:
    if x % 2:
        S += x
    xold, x = x, x + xold
print(f"\nLa somme demandée vaut {S}")

La somme demandée vaut 4613732

1.2. Exercice 2#

L’algorithme d’Euclide pour calculer le PGCD de deux nombres entiers repose sur la remarque suivante : Si \(a\) et \(b\) sont deux entiers avec par exemple \(a\geq b\), si \(r\) est le reste de \(a\) par \(b\), alors le PGCD de \(a\) et \(b\) vaut le PGCD de \(b\) et \(r\).

L’algorithme d’Euclide consiste donc à

  • calculer \(r\) le reste de la division euclidienne de \(a\) par \(b\) (on utilisera l’opérateur %)

  • puis affecter \(a\leftarrow b\) et \(b\leftarrow r\). L’algorithme s’arrêre lorsque \(r=0\). Le PGCD vaut alors le dernier reste qui n’est pas \(0\).

Cet algorithme (s’il est bien programmé) s’arrête toujours puisque la suite des restes est strictement décroissante et prend des valeurs entières.

Questions

  1. Programmez l’algorithme d’Euclide qui permet de calculer le PGCD de deux entiers.

  2. Calculez le PGCD de 6132196 et de 222897

Hide code cell source 
a, b = 6132196, 222897
print(f"PGCD({a}, {b}) = ", end='')
while b != 0:
    a, b = b, a%b
print(f"{a}")

PGCD(6132196, 222897) = 389

1.3. Exercice 3#

Dans cet exercice, nous allons fabriquer la liste des \(N\) premiers nombres premiers en utilisant l’algorithme suivant :

  • on commence à créer la liste avec le premier nombre premier l = [2] ;

  • on cherche le prochain nombre premier à mettre dans la liste :

    • on fait une boucle sur les entiers supérieurs au dernier nombre premier trouvé et on teste s’il est divisible par l’un des nombres premiers déjà trouvé

    • s’il est divisible par l’un des nombres, cela signifie qu’il n’est pas premier

    • sinon, on doit l’ajouter à la liste.

Question

Programmez cet algorithme pour fabriquer la liste des 10 premiers nombres premiers

Hide code cell source 
N, l = 10, [2]
n = l[0]
while len(l) < N:
    n += 1
    is_prime = True
    for k in l:
        if n % k == 0:
            is_prime = False
    if is_prime:
        l.append(n)
print(l)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

1.4. Exercice 4#

Dans cet exercice, nous cherchons à déterminer le plus grand facteur premier d’un nombre entier donné (noté \(N\)). L’algorithme proposé consiste à parcourir les entiers en partant de \(2\) et de tester si \(N\) est divisible par cet entier. Si c’est le cas, on divise \(N\) par cet entier. En effet, cela ne modifie pas le plus grand facteur premier de \(N\) et la recherche est simplifié puisque l’algorithme fait décroître \(N\). Ecrit en pseudo-langage, voici l’algorithme :

  • Un entier \(N\) étant donné, on initialise une variable \(p\) à 1 ;

  • on effectue une boucle tant que l’entier \(N\) est strictement supérieur à \(1\) ;

    • on incrémente \(p\) de \(1\) ;

    • on effectue une boucle tant que \(N\) est divisible par \(p\), on divise \(N\) par \(p\) ;

  • la dernière valeur de \(p\) trouvée est exactement le plus grand facteur premier du nombre \(N\) initial.

Questions

  1. Programmez en python l’algorithme proposé.

  2. Déterminez le plus grand facteur premier du nombre 123.

  3. Déterminez le plus grand facteur premier du nombre 600851475143.

Indication

La division entière est obtenue à l’aide de l’opérateur //.

Hide code cell source 
N = 600851475143
print(f"Le plus grand facteur premier de {N} est ", end='')
p = 1
while N > 1:
    p += 1
    while N % p == 0:
        N //= p
print(f"{p}")

Le plus grand facteur premier de 600851475143 est 6857

1.5. Exercice 5#

Un nombre palindromic est un nombre qui peut se lire de gauche à droite ou de droite à gauche de la même manière. Le plus grand nombre palindromic qui est produit de deux nombres à 2 chiffres est \(9009 = 91 \times 99\).

Question

Trouvez le plus grand nombre palindromic qui s’écrit comme produit de deux nombres à 3 chiffres.

Indication 1

Pour trouver les chiffres d’un nombre écrit en base 10, il est possible de le convertir en chaîne de caractères à l’aide de la commande str. Voici un exemple :

s = str(123)
print("Les chiffres de 123 sont")
for k in s:
    print(k)

Indication 2

Vous utiliserez les algorithmes suivants écrit en python comme briques de base :

test si le nombre \(p\) est palindromique:

str(p) == str(p)[::-1]

parcours de tous les nombres qui s’écrivent comme produit de 2 nombres à 3 chiffres:

for k in range(100, 1000):
    for l in range(100, 1000):
        p = k*l
Hide code cell source 
n, kn, ln = 1, 1, 1
for k in range(100, 1000):
    for l in range(k, 1000):
        p = k*l
        if p > n and str(p) == str(p)[::-1]:
            n, kn, ln = p, k, l
print(f"{n} = {kn}x{ln} est le plus grand nombre palindromic à 3 chiffres")

906609 = 913x993 est le plus grand nombre palindromic à 3 chiffres

1.6. Exercice 6#

Un nombre parfait est un nombre qui est égal à la somme de tous ces diviseurs sauf lui-même. Par exemple \(28 = 1 + 2 + 4 + 7 + 14\).

Question

Trouvez les 4 premiers nombres parfaits.

Indication

Pour déterminer si un nombre est parfait, vous pourrez utiliser l’algorithme écrit en pseudo-langage suivant :

  • Etant donné un entier \(N\),

  • initialisez une variable \(S\) à \(0\) qui contiendra la somme des diviseurs de \(N\);

  • faites une boucle pour \(k\) allant \(1\) à \(N-1\);

    • si \(k\) divise \(N\), ajoutez \(k\) à \(S\);

  • Après la boucle, si \(S\) et \(N\) ont la même valeur, \(N\) est parfait.

Hide code cell source 
liste_parfaits = []
N = 0
while len(liste_parfaits) < 4:
    N += 1
    S = 0
    for k in range(1, N):
        if N % k == 0:
            S += k
    if S == N:
        liste_parfaits.append(N)
print(liste_parfaits)

[6, 28, 496, 8128]

1.7. Exercice 7#

Question

Calculez le nombre de possibilités pour faire 1 euro avec des pièces de \(1\), \(2\), \(5\), \(10\), \(20\), \(50\) centimes. Il n’est pas nécessaire d’afficher les possibilités.

Solution brutale mais pas si mauvaise que ça

Hide code cell source 
S, N = 100, 0
pieces = [50, 20, 10, 5, 2, 1]
for n0 in range(S//pieces[0] + 1):  # piece de 50
    Sn0 = S - pieces[0] * n0
    for n1 in range(Sn0//pieces[1] + 1):  # piece de 20
        Sn1 = Sn0 - pieces[1] * n1
        for n2 in range(Sn1//pieces[2] + 1):  # piece de 10
            Sn2 = Sn1 - pieces[2] * n2
            for n3 in range(Sn2//pieces[3] + 1):  # piece de 5
                Sn3 = Sn2 - pieces[3] * n3
                for n4 in range(Sn3//pieces[4] + 1):  # piece de 2
                    N += 1
print(f"Il y a {N} façons de faire {S} avec des pièces de {pieces}")

Il y a 4562 façons de faire 100 avec des pièces de [50, 20, 10, 5, 2, 1]

Solution plus génériques mais très lente

Hide code cell source 
S, N = 50, 0
pieces = [1, 2, 5, 10, 20, 50]
parcours = [0]*len(pieces)
while parcours[-1] < S//pieces[-1] + 1:
    parcours[0] += 1
    for k in range(len(pieces)-1):
        if parcours[k] > S//pieces[k]:
            parcours[k] = 0
            parcours[k+1] += 1
    Sloc = 0
    for k in range(len(pieces)):
        Sloc += parcours[k] * pieces[k]
    if Sloc == S:
        N += 1
print(f"Il y a {N} façons de faire {S} avec des pièces de {pieces}")

Il y a 451 façons de faire 50 avec des pièces de [1, 2, 5, 10, 20, 50]

On améliore l’algorithme en traitant plus vite les pieces de 1…

Hide code cell source 
S, N = 100, 1
pieces = [1, 2, 5, 10, 20, 50]
parcours = [0]*len(pieces)
while parcours[-1] < S//pieces[-1] + 1:
    parcours[1] += 1
    for k in range(1, len(pieces)-1):
        if parcours[k] > S//pieces[k]:
            parcours[k] = 0
            parcours[k+1] += 1
    Sloc = 0
    for k in range(len(pieces)):
        Sloc += parcours[k] * pieces[k]
    if Sloc <= S:
        N += 1
print(f"Il y a {N} façons de faire {S} avec des pièces de {pieces}")

Il y a 4562 façons de faire 100 avec des pièces de [1, 2, 5, 10, 20, 50]

Et finalement une solution plus intelligente (et plus rapide) :)

Hide code cell source 
target = 100000
coinSizes = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [0] * (target + 1)
ways[0] = 1
for c in coinSizes:
    for i in range(c, target+1):
        ways[i] += ways[i-c]
print(f"Il y a {ways[-1]} façons de faire {target} avec des pièces de {coinSizes}")

Il y a 10056050940818192726001 façons de faire 100000 avec des pièces de [1, 2, 5, 10, 20, 50, 100, 200]

1.8. Exercice 8#

Le crible d’Eratosthène est une méthode rapide qui permet de déterminer tous les nombres premiers inférieurs à une certaine borne. Le principe en est le suivant :

  1. Création d’un tableau T de taille \(N+1\) contenant le booléen True. La case T[i] servira à renseigner si l’entier i est premier ou non.

  2. Les entiers \(0\) et \(1\) étant non premiers, on corrige les valeurs T[0]=T[1]=False.

  3. On fait ensuite une boucle sur tous les éléments du tableau : pour l’indice i,

    • si T[i] est égal à False, on ne fait rien

    • si T[i] est égal à True (qui signifie que \(i\) est premier), on modifie tous les multiples de \(i\) qui ne sont pas premiers, c’est-à-dire que l’on met à False tous les T[k*i] pour \(k\) entier supérieur ou égal à 2.

Vous pouvez trouver des indications sur ce crible sur la page wikipedia suivante.

https://fr.wikipedia.org/wiki/Crible_d’Ératosthène

Un dessin valant mieux qu’un long discours :

Eratosthene sieve

Questions

  • Programmez le crible d’Eratosthène et affichez tous les nombres premiers inférieurs à \(1000\).

  • Réfléchissez à accélérer l’algorithme en évitant de parcourir la fin du tableau (à partir d’un certain indice i, tous les multiples que l’on pourrait enlever ont déjà été enlevés lors d’une étape précédente).

Indication

Si vous avez besoin de la fonction \(\sqrt{\cdot}\), vous pouvez vous aider de ce petit bout de code qui calcule et affiche \(\sqrt{2}\) :

from math import sqrt
print(sqrt(2))
Hide code cell source 
import math
N = 1000
Tab = [False, False] + [True]*(N-1)
for n in range(2, int(math.sqrt(N))+1):
    if Tab[n]:
        Tab[2*n::n] = [False]*(N//n-1)
for k in range(len(Tab)):
    if Tab[k]:
        print(f"{k:3d} ", end='')
print("...")

  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 ...

1.9. Exercice 9#

Un nombre est dit pandigital s’il est composé des chiffres \(1, 2, \ldots, 9\) exactement une fois. Par exemple, le nombre \(531297846\) est pandigital.

Comme il y a \(9!\) pandigital en base \(10\), nous allons plutôt travailler en base 5. On dira qu’un nombre est \(5\)-pandigital si son écriture en base 6 est composé exactement des chiffres \(1, 2, \ldots, 5\).

Questions

  1. Trouvez tous les nombres \(5\)-pandigitaux et écrivez les en base 6.

  2. Modifiez votre code pour les afficher en base 10.

Indication

Vous pourrez avoir besoin de la commande permutations du module itertools qui vous retourne un itérateur sur toutes les permutations sans répétition d’un ensemble donné. Egalement la fonction int bien utilisée permet de convertir une chaine de caractères représentant un nombre en base \(b\) en un entier en base \(10\)…

Hide code cell source 
from itertools import permutations
base = 6
s0 = ''.join([str(k) for k in list(range(1, base))])
for s in permutations(s0, base-1):
    n_b = ''.join(s)
    print(f"{n_b} est un {base-1}-pandigital qui vaut {int(n_b, base)}")

12345 est un 5-pandigital qui vaut 1865
12354 est un 5-pandigital qui vaut 1870
12435 est un 5-pandigital qui vaut 1895
12453 est un 5-pandigital qui vaut 1905
12534 est un 5-pandigital qui vaut 1930
12543 est un 5-pandigital qui vaut 1935
13245 est un 5-pandigital qui vaut 2045
13254 est un 5-pandigital qui vaut 2050
13425 est un 5-pandigital qui vaut 2105
13452 est un 5-pandigital qui vaut 2120
13524 est un 5-pandigital qui vaut 2140
13542 est un 5-pandigital qui vaut 2150
14235 est un 5-pandigital qui vaut 2255
14253 est un 5-pandigital qui vaut 2265
14325 est un 5-pandigital qui vaut 2285
14352 est un 5-pandigital qui vaut 2300
14523 est un 5-pandigital qui vaut 2355
14532 est un 5-pandigital qui vaut 2360
15234 est un 5-pandigital qui vaut 2470
15243 est un 5-pandigital qui vaut 2475
15324 est un 5-pandigital qui vaut 2500
15342 est un 5-pandigital qui vaut 2510
15423 est un 5-pandigital qui vaut 2535
15432 est un 5-pandigital qui vaut 2540
21345 est un 5-pandigital qui vaut 2945
21354 est un 5-pandigital qui vaut 2950
21435 est un 5-pandigital qui vaut 2975
21453 est un 5-pandigital qui vaut 2985
21534 est un 5-pandigital qui vaut 3010
21543 est un 5-pandigital qui vaut 3015
23145 est un 5-pandigital qui vaut 3305
23154 est un 5-pandigital qui vaut 3310
23415 est un 5-pandigital qui vaut 3395
23451 est un 5-pandigital qui vaut 3415
23514 est un 5-pandigital qui vaut 3430
23541 est un 5-pandigital qui vaut 3445
24135 est un 5-pandigital qui vaut 3515
24153 est un 5-pandigital qui vaut 3525
24315 est un 5-pandigital qui vaut 3575
24351 est un 5-pandigital qui vaut 3595
24513 est un 5-pandigital qui vaut 3645
24531 est un 5-pandigital qui vaut 3655
25134 est un 5-pandigital qui vaut 3730
25143 est un 5-pandigital qui vaut 3735
25314 est un 5-pandigital qui vaut 3790
25341 est un 5-pandigital qui vaut 3805
25413 est un 5-pandigital qui vaut 3825
25431 est un 5-pandigital qui vaut 3835
31245 est un 5-pandigital qui vaut 4205
31254 est un 5-pandigital qui vaut 4210
31425 est un 5-pandigital qui vaut 4265
31452 est un 5-pandigital qui vaut 4280
31524 est un 5-pandigital qui vaut 4300
31542 est un 5-pandigital qui vaut 4310
32145 est un 5-pandigital qui vaut 4385
32154 est un 5-pandigital qui vaut 4390
32415 est un 5-pandigital qui vaut 4475
32451 est un 5-pandigital qui vaut 4495
32514 est un 5-pandigital qui vaut 4510
32541 est un 5-pandigital qui vaut 4525
34125 est un 5-pandigital qui vaut 4805
34152 est un 5-pandigital qui vaut 4820
34215 est un 5-pandigital qui vaut 4835
34251 est un 5-pandigital qui vaut 4855
34512 est un 5-pandigital qui vaut 4940
34521 est un 5-pandigital qui vaut 4945
35124 est un 5-pandigital qui vaut 5020
35142 est un 5-pandigital qui vaut 5030
35214 est un 5-pandigital qui vaut 5050
35241 est un 5-pandigital qui vaut 5065
35412 est un 5-pandigital qui vaut 5120
35421 est un 5-pandigital qui vaut 5125
41235 est un 5-pandigital qui vaut 5495
41253 est un 5-pandigital qui vaut 5505
41325 est un 5-pandigital qui vaut 5525
41352 est un 5-pandigital qui vaut 5540
41523 est un 5-pandigital qui vaut 5595
41532 est un 5-pandigital qui vaut 5600
42135 est un 5-pandigital qui vaut 5675
42153 est un 5-pandigital qui vaut 5685
42315 est un 5-pandigital qui vaut 5735
42351 est un 5-pandigital qui vaut 5755
42513 est un 5-pandigital qui vaut 5805
42531 est un 5-pandigital qui vaut 5815
43125 est un 5-pandigital qui vaut 5885
43152 est un 5-pandigital qui vaut 5900
43215 est un 5-pandigital qui vaut 5915
43251 est un 5-pandigital qui vaut 5935
43512 est un 5-pandigital qui vaut 6020
43521 est un 5-pandigital qui vaut 6025
45123 est un 5-pandigital qui vaut 6315
45132 est un 5-pandigital qui vaut 6320
45213 est un 5-pandigital qui vaut 6345
45231 est un 5-pandigital qui vaut 6355
45312 est un 5-pandigital qui vaut 6380
45321 est un 5-pandigital qui vaut 6385
51234 est un 5-pandigital qui vaut 6790
51243 est un 5-pandigital qui vaut 6795
51324 est un 5-pandigital qui vaut 6820
51342 est un 5-pandigital qui vaut 6830
51423 est un 5-pandigital qui vaut 6855
51432 est un 5-pandigital qui vaut 6860
52134 est un 5-pandigital qui vaut 6970
52143 est un 5-pandigital qui vaut 6975
52314 est un 5-pandigital qui vaut 7030
52341 est un 5-pandigital qui vaut 7045
52413 est un 5-pandigital qui vaut 7065
52431 est un 5-pandigital qui vaut 7075
53124 est un 5-pandigital qui vaut 7180
53142 est un 5-pandigital qui vaut 7190
53214 est un 5-pandigital qui vaut 7210
53241 est un 5-pandigital qui vaut 7225
53412 est un 5-pandigital qui vaut 7280
53421 est un 5-pandigital qui vaut 7285
54123 est un 5-pandigital qui vaut 7395
54132 est un 5-pandigital qui vaut 7400
54213 est un 5-pandigital qui vaut 7425
54231 est un 5-pandigital qui vaut 7435
54312 est un 5-pandigital qui vaut 7460
54321 est un 5-pandigital qui vaut 7465