Chargement de l'audio en cours
Plus

Plus

Arithmétique
Page numérique

Mode édition
Ajouter

Ajouter

Terminer

Terminer




Arithmétique





1
Test de primalité optimisé ☆☆

Voir fiche n° 1 : Algorithme en langage naturel
Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées

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.

Python - Arithmétique


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
Voir les réponses

2
Fréquence des carrés modulo 7 ★★

Voir fiche n° 2 : Les variables
Voir fiche n° 2 bis : Les listes
Voir fiche n° 5 : Les boucles bornées

1. À l’aide d’une feuille de calcul, déterminer le reste dans la division euclidienne par de chacun des carrés des nombres entiers compris entre et . 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)
Voir les réponses

3
Calcul du par l’algorithme d’Euclide
☆☆

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 6 : Les boucles non bornées

Les fonctions euclide_iteratif et euclide_recursif permettent de calculer le de deux nombres entiers naturels et 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 ...

4
Calcul du par balayage
☆☆

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées

La fonction pgcd_balayage renvoie le de deux nombres entiers et donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à et et conserve, parmi ceux qui divisent et , le plus grand. Compléter la fonction.

def pgcd_balayage(a, b):
  for i in range(...):
    if a%i == 0 and ... :
      pgcd = ...
  return pgcd

5
Conjectures
★★★

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles


Dans un manuel, Jérôme a lu que, pour tout , et é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 donnée en argument.

2. Démontrer cette conjecture.


3. Par ailleurs, Jérôme a lu que, pour tout entier naturel non nul , 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 ...
Voir les réponses

6
Nombre de diviseurs
★★

Voir fiche n° 1 : Algorithme en langage naturel
Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées


1. Écrire une fonction nombre_diviseurs qui prend en argument un nombre entier non nul et qui retourne le nombre de ses diviseurs.

2. Écrire une fonction max_diviseurs qui prend en argument un nombre entier non nul et qui retourne le nombre entier 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.



7
Théorème de Wilson
★★

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles

Le théorème de Wilson affirme qu’un entier strictement plus grand que est un nombre premier si, et seulement si, il divise , c'est-à-dire si, et seulement si, .

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 supérieur ou égal à et renvoie True si l’entier est premier et False sinon.

2. Vérifier pour les entiers inférieurs ou égaux à que le test de primalité présenté dans l’exercice 1 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.



Voir les réponses

8
Nombres pseudo-aléatoires
☆☆

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles


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 , par , où , et sont trois nombres entiers appelés respectivement le multiplicateur, l’incrément et le module. Le premier terme , nombre entier compris entre et , est appelé graine.

1. Dans cette question, on choisit , et . En utilisant des graines égales à , , et , 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 , , et 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
Voir les réponses

9
Décomposition en produit de facteurs premiers
★★★

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 5 : Les boucles bornées


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 à et qui renvoie sa décomposition en produit de facteurs premiers.

Aide
La liste des nombres premiers inférieurs ou égaux à 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]
Voir les réponses

10
Divisibilité par 24
★★★

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées


1. Démontrer que si est un nombre premier supérieur ou égal à , alors est un multiple de .


2. On choisit un nombre entier naturel inférieur ou égal à tel que soit divisible par . Estimer à l’aide d’une fonction Python la probabilité que soit un nombre premier.

Aide
On pourra utiliser le test de primalité construit dans un exercice précédent.



Voir les réponses

11
★★★

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées

Le code ci-dessous permet de déterminer le 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 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]]

12
Nombres de Fermat ☆☆

Voir fiche n° 2 : Les variables
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 6 : Les boucles non bornées

Pour tout entier naturel , on appelle -ième nombre de Fermat le nombre .
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 de est de la forme , où est un entier.




13
Nombres de Mersenne ☆☆

Voir fiche n° 2 : Les variables
Voir fiche n° 2 bis : Les listes
Voir fiche n° 3 : Les fonctions
Voir fiche n° 4 : Les instructions conditionnelles
Voir fiche n° 5 : Les boucles bornées
Voir fiche n° 6 : Les boucles non bornées

Pour tout entier naturel non nul , on appelle -ième nombre de Mersenne le nombre .
Pour que le nombre de Mersenne soit premier, il est nécessaire, mais pas suffisant, que soit lui-même premier.
Dresser la liste des huit premiers nombres de Mersenne premiers à l’aide d’une fonction Python.