Python
Arithmétique
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Fiches de cours Python
Retrouvez toutes les fiches de cours téléchargeables au format pdf en cliquant sur les liens suivants :
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
1Test de primalité optimisé
→
→
→
→
→
1. Compléter la fonction premier qui prend en argument un nombre entier strictement positif et qui retourne True si ce nombre est premier et False sinon.
2. Expliquer la ligne 7 de cette fonction.
3. Justifier pourquoi cette ligne peut être remplacée par for i in range(2, int(sqrt(n)) + 1).
4. À l'aide de l'instruction clock du module time, qui permet de chronométrer un programme, évaluer le gain de temps obtenu avec cette modification sur différents nombres premiers. On pourra par exemple introduire les lignes suivantes.
→
→
→
→
1. Compléter la fonction premier qui prend en argument un nombre entier strictement positif et qui retourne True si ce nombre est premier et False sinon.
2. Expliquer la ligne 7 de cette fonction.
3. Justifier pourquoi cette ligne peut être remplacée par for i in range(2, int(sqrt(n)) + 1).
4. À l'aide de l'instruction clock du module time, qui permet de chronométrer un programme, évaluer le gain de temps obtenu avec cette modification sur différents nombres premiers. On pourra par exemple introduire les lignes suivantes.
def premier(n):
if n == 1:
return False
if n == 2:
return True
else:
for i in range(2, n):
if ... :
return False
return True
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
2Fréquence des carrés modulo 7
→
→
→
1. À l'aide d'une feuille de calcul, déterminer le reste dans la division euclidienne par 7 de chacun des carrés des nombres entiers compris entre 0 et 100. Certains restes semblent-ils apparaître plus souvent que d'autres ?
2. Le programme suivant calcule la fréquence de chaque congruence modulo 7 parmi les carrés des nombres entiers strictement positifs. Compléter les lignes 4 et 8 de ce programme.
3. Après avoir lancé ce programme, pouvez vous confirmer le résultat de la question 1 ?
→
→
1. À l'aide d'une feuille de calcul, déterminer le reste dans la division euclidienne par 7 de chacun des carrés des nombres entiers compris entre 0 et 100. Certains restes semblent-ils apparaître plus souvent que d'autres ?
2. Le programme suivant calcule la fréquence de chaque congruence modulo 7 parmi les carrés des nombres entiers strictement positifs. Compléter les lignes 4 et 8 de ce programme.
3. Après avoir lancé ce programme, pouvez vous confirmer le résultat de la question 1 ?
N = 1000 congruence = [0, 0, 0, 0, 0, 0, 0] for i in range(N): reste = ... congruence[reste] = congruence[reste] + 1 # calcul des fréquences for k in range(len(congruence)): congruence[k] = ... print(congruence)
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
3Calcul du \text{PGCD} par l'algorithme d'Euclide
→
→
→
Les fonctions euclide_iteratif et euclide_recursif permettent de calculer le \text{PGCD} de deux nombres entiers naturels a et b donnés en arguments.
1. Compléter la fonction euclide_iteratif.
2. Compléter la fonction euclide_recursif.
→
→
Les fonctions euclide_iteratif et euclide_recursif permettent de calculer le \text{PGCD} de deux nombres entiers naturels a et b donnés en arguments.
1. Compléter la fonction euclide_iteratif.
2. Compléter la fonction euclide_recursif.
def euclide_iteratif(a, b):
a, b = max(a, b), min(a, b)
reste = b
while a%b … :
reste = a%b
a, b = ... , ...
return ...
def euclide_recursif(a, b):
a, b = max(a, b), min(a, b)
if a%b == 0:
return ...
else:
return ...
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
4Calcul du \text{PGCD} par balayage
→
→
→
→
La fonction pgcd_balayage renvoie le \text{PGCD} de deux nombres entiers a et b donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à a et b et conserve, parmi ceux qui divisent a et b, le plus grand. Compléter la fonction.
→
→
→
La fonction pgcd_balayage renvoie le \text{PGCD} de deux nombres entiers a et b donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à a et b et conserve, parmi ceux qui divisent a et b, le plus grand. Compléter la fonction.
def pgcd_balayage(a, b):
for i in range(...):
if a%i == 0 and ... :
pgcd = ...
return pgcd
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
5Conjectures
→
→
→
Dans un manuel, Jérôme a lu que, pour tout n \in \mathbb{N}, 7n+4 et 5n+3 étaient premiers entre eux.
1. À l'aide de la fonction euclide_recursif de l'exercice 3 (à compléter), écrire une fonction permettant de tester cette affirmation pour tous les nombres entiers inférieurs à une valeur \text{N} \in \mathbb{N} donnée en argument.
2. Démontrer cette conjecture.
3. Par ailleurs, Jérôme a lu que, pour tout entier naturel non nul n, \dfrac{2n+1}{n(n+1)} est irréductible. En modifiant la fonction de la question 1, estimer la validité de cette conjecture.
4. Prouver cette conjecture.
→
→
Dans un manuel, Jérôme a lu que, pour tout n \in \mathbb{N}, 7n+4 et 5n+3 étaient premiers entre eux.
1. À l'aide de la fonction euclide_recursif de l'exercice 3 (à compléter), écrire une fonction permettant de tester cette affirmation pour tous les nombres entiers inférieurs à une valeur \text{N} \in \mathbb{N} donnée en argument.
2. Démontrer cette conjecture.
3. Par ailleurs, Jérôme a lu que, pour tout entier naturel non nul n, \dfrac{2n+1}{n(n+1)} est irréductible. En modifiant la fonction de la question 1, estimer la validité de cette conjecture.
4. Prouver cette conjecture.
def euclide_recursif(a, b):
a, b = max(a, b), min(a, b)
if a%b == 0:
return ...
else:
return ...
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
6Nombre de diviseurs
→
→
→
→
→
1. Écrire une fonction nombre_diviseurs qui prend en argument un nombre entier non nul n et qui retourne le nombre de ses diviseurs.
2. Écrire une fonction max_diviseurs qui prend en argument un nombre entier n non nul et qui retourne le nombre entier k\leqslant n ayant le plus grand nombre de diviseurs. Si deux nombres ou plus ont le même nombre de diviseurs, la fonction renverra le plus petit de ces nombres.
3. Modifier le programme pour qu'en cas d'égalité sur le nombre de diviseurs, la fonction retourne le plus grand des nombres concernés.
→
→
→
→
1. Écrire une fonction nombre_diviseurs qui prend en argument un nombre entier non nul n et qui retourne le nombre de ses diviseurs.
2. Écrire une fonction max_diviseurs qui prend en argument un nombre entier n non nul et qui retourne le nombre entier k\leqslant n ayant le plus grand nombre de diviseurs. Si deux nombres ou plus ont le même nombre de diviseurs, la fonction renverra le plus petit de ces nombres.
3. Modifier le programme pour qu'en cas d'égalité sur le nombre de diviseurs, la fonction retourne le plus grand des nombres concernés.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
7Théorème de Wilson
→
→
→
Le théorème de Wilson affirme qu'un entier p strictement plus grand que 1 est un nombre premier si, et seulement si, il divise (p -1)! + 1, c'est-à-dire si, et seulement si, \displaystyle (p-1)!+1\equiv 0 [p].
1. En utilisant éventuellement la fonction factorial du module math, écrire à l'aide du théorème de Wilson, une fonction estPremier qui prend en argument un entier naturel n supérieur ou égal à 2 et renvoie True si l'entier est premier et False sinon.
2. Vérifier pour les entiers inférieurs ou égaux à 10\,000 que le test de primalité présenté dans l' et celui du théorème de Wilson donnent les mêmes résultats.
3. Expliquer pourquoi ce test, malgré sa simplicité apparente, n'est pas utilisé dans les tests de primalité informatiques.
→
→
Le théorème de Wilson affirme qu'un entier p strictement plus grand que 1 est un nombre premier si, et seulement si, il divise (p -1)! + 1, c'est-à-dire si, et seulement si, \displaystyle (p-1)!+1\equiv 0 [p].
1. En utilisant éventuellement la fonction factorial du module math, écrire à l'aide du théorème de Wilson, une fonction estPremier qui prend en argument un entier naturel n supérieur ou égal à 2 et renvoie True si l'entier est premier et False sinon.
2. Vérifier pour les entiers inférieurs ou égaux à 10\,000 que le test de primalité présenté dans l' et celui du théorème de Wilson donnent les mêmes résultats.
3. Expliquer pourquoi ce test, malgré sa simplicité apparente, n'est pas utilisé dans les tests de primalité informatiques.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
8Nombres pseudo-aléatoires
→
→
→
Pour générer une suite de nombres pseudo‑aléatoires, c'est-à-dire une suite de nombres présentant certaines propriétés du hasard, on peut utiliser des suites d'entiers définies, pour tout entier naturel n, par u_{n+1} = au_n+ c [m], où a, c et m sont trois nombres entiers appelés respectivement le multiplicateur, l'incrément et le module. Le premier terme u_0, nombre entier compris entre 0 et m-1, est appelé graine.
1. Dans cette question, on choisit a=25, c=16 et m=256. En utilisant des graines égales à 125, 96, 50 et 10, expliquer pourquoi les suites générées ne conviennent pas comme suites de nombres pseudo‑aléatoires.
2. Expliquer pourquoi une suite générée par cette méthode est nécessairement périodique. Préciser quelle valeur la période ne peut pas dépasser.
3. Écrire une fonction Python nommée periode qui prend en arguments a, c, m et u_0 et retourne la période de la suite.
→
→
Pour générer une suite de nombres pseudo‑aléatoires, c'est-à-dire une suite de nombres présentant certaines propriétés du hasard, on peut utiliser des suites d'entiers définies, pour tout entier naturel n, par u_{n+1} = au_n+ c [m], où a, c et m sont trois nombres entiers appelés respectivement le multiplicateur, l'incrément et le module. Le premier terme u_0, nombre entier compris entre 0 et m-1, est appelé graine.
1. Dans cette question, on choisit a=25, c=16 et m=256. En utilisant des graines égales à 125, 96, 50 et 10, expliquer pourquoi les suites générées ne conviennent pas comme suites de nombres pseudo‑aléatoires.
2. Expliquer pourquoi une suite générée par cette méthode est nécessairement périodique. Préciser quelle valeur la période ne peut pas dépasser.
3. Écrire une fonction Python nommée periode qui prend en arguments a, c, m et u_0 et retourne la période de la suite.
def u(n, a, c, m, u_0):
if (n == 0):
return u_0
else:
return (a*u(n-1, a, c, m, u_0) + c)%m
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
9Décomposition en produit de facteurs premiers
→
→
→
La fonction decomposition_vers_nombre ci-dessous permet de calculer un nombre à partir de sa décomposition en produit de facteurs premiers.
1. En étudiant la fonction, sous quelle forme doit être écrite la décomposition en produit de facteurs premiers d'un nombre pour que le script fonctionne correctement ?
2. Tester cette fonction avec M=[[2,1],[3,2],[5,3]].
3. Écrire une fonction qui prend en argument un nombre entier naturel inférieur ou égal à 1\,000 et qui renvoie sa décomposition en produit de facteurs premiers.
→
→
La fonction decomposition_vers_nombre ci-dessous permet de calculer un nombre à partir de sa décomposition en produit de facteurs premiers.
1. En étudiant la fonction, sous quelle forme doit être écrite la décomposition en produit de facteurs premiers d'un nombre pour que le script fonctionne correctement ?
2. Tester cette fonction avec M=[[2,1],[3,2],[5,3]].
3. Écrire une fonction qui prend en argument un nombre entier naturel inférieur ou égal à 1\,000 et qui renvoie sa décomposition en produit de facteurs premiers.
Aide
La liste des nombres premiers inférieurs ou égaux à 1\,000 est fournie ci-dessous.
def decomposition_vers_nombre(M):
nombre = 1
n = len(M)
for facteur in range(n):
nombre = nombre * M[facteur][0]**M[facteur][1]
return nombre
liste_nombres_premiers = [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]
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
10Divisibilité par 24
→
→
→
→
1. Démontrer que si p est un nombre premier supérieur ou égal à 5, alors p^2-1 est un multiple de 24.
2. On choisit un nombre entier naturel n inférieur ou égal à 1\,000 tel que n^2-1 soit divisible par 24. Estimer à l'aide d'une fonction Python la probabilité que n soit un nombre premier.
→
→
→
1. Démontrer que si p est un nombre premier supérieur ou égal à 5, alors p^2-1 est un multiple de 24.
2. On choisit un nombre entier naturel n inférieur ou égal à 1\,000 tel que n^2-1 soit divisible par 24. Estimer à l'aide d'une fonction Python la probabilité que n soit un nombre premier.
Aide
On pourra utiliser le test de primalité construit dans un exercice précédent.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
11\text{PPCM}
→
→
→
→
Le code ci-dessous permet de déterminer le \text{PGCD} de deux nombres dont on donne la décomposition en produit de facteurs premiers. Utiliser ce code pour écrire une fonction Python permettant de calculer le \text{PPCM} de deux nombres donnés.
→
→
→
Le code ci-dessous permet de déterminer le \text{PGCD} de deux nombres dont on donne la décomposition en produit de facteurs premiers. Utiliser ce code pour écrire une fonction Python permettant de calculer le \text{PPCM} de deux nombres donnés.
Aide
list.index(x) retourne la position du premier élément de la liste list ayant la valeur x.
def pgcd(nb1, nb2):
n1 = len(nb1)
n2 = len(nb2)
out = []
liste1 = []
for i in range(n1):
liste1.append(nb1[i][0])
liste2 = []
for j in range(n2):
liste2.append(nb2[j][0])
for facteur in range(n1):
if liste1[facteur] in liste2:
index = liste2.index(liste1[facteur])
exposant = min(nb1[facteur][1], nb2[index][1])
out.append([liste1[facteur], exposant])
return out
a = [[2,5],[5,3],[7,1]]
b = [[2,3],[3,2],[5,4]]
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
12Nombres de Fermat
→
→
→
→
Pour tout entier naturel n, on appelle n-ième nombre de Fermat le nombre F_n=2^{2^n}+1.
Pierre de Fermat émit la conjecture que ces nombres étaient tous premiers.
Vérifier cette conjecture à l'aide d'un programme Python.
→
→
→
Pour tout entier naturel n, on appelle n-ième nombre de Fermat le nombre F_n=2^{2^n}+1.
Pierre de Fermat émit la conjecture que ces nombres étaient tous premiers.
Vérifier cette conjecture à l'aide d'un programme Python.
Aide
On pourra utiliser la propriété suivante : Tout diviseur premier p de F_n=2^{2^n}+1 est de la forme p=k\times 2^{n+1}+1, où k est un entier.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
13Nombres de Mersenne
→
→
→
→
→
→
Pour tout entier naturel non nul n, on appelle n-ième nombre de Mersenne le nombre \text{M}_n=2^n-1.
Pour que le nombre de Mersenne \text{M}_n soit premier, il est nécessaire, mais pas suffisant, que n soit lui-même premier.
Dresser la liste des huit premiers nombres de Mersenne premiers à l'aide d'une fonction Python.
→
→
→
→
→
Pour tout entier naturel non nul n, on appelle n-ième nombre de Mersenne le nombre \text{M}_n=2^n-1.
Pour que le nombre de Mersenne \text{M}_n soit premier, il est nécessaire, mais pas suffisant, que n soit lui-même premier.
Dresser la liste des huit premiers nombres de Mersenne premiers à l'aide d'une fonction Python.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
j'ai une idée !
Oups, une coquille
