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 8 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 77 de chacun des carrés des nombres entiers compris entre 00 et 100100. 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 PGCD\text{PGCD} 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 PGCD\text{PGCD} de deux nombres entiers naturels aa et bb 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 ...
Voir les réponses

4
Calcul du PGCD\text{PGCD} 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 PGCD\text{PGCD} de deux nombres entiers aa et bb donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à aa et bb et conserve, parmi ceux qui divisent aa et bb, le plus grand. Compléter la fonction.

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

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 nNn \in \mathbb{N}, 7n+47n+4 et 5n+35n+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 NN\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 nn, 2n+1n(n+1)\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 ...
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 nn et qui retourne le nombre de ses diviseurs.

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


Voir les réponses

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 pp strictement plus grand que 11 est un nombre premier si, et seulement si, il divise (p1)!+1(p -1)! + 1, c'est-à-dire si, et seulement si, (p1)!+10[p]\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 nn supérieur ou égal à 22 et renvoie True si l’entier est premier et False sinon.

2. Vérifier pour les entiers inférieurs ou égaux à 1000010\,000 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 nn, par un+1=aun+c[m]u_{n+1} = au_n+ c [m], où aa, cc et mm sont trois nombres entiers appelés respectivement le multiplicateur, l’incrément et le module. Le premier terme u0u_0, nombre entier compris entre 00 et m1m-1, est appelé graine.

1. Dans cette question, on choisit a=25a=25, c=16c=16 et m=256m=256. En utilisant des graines égales à 125125, 9696, 5050 et 1010, 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 aa, cc, mm et u0u_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
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 à 10001\,000 et qui renvoie sa décomposition en produit de facteurs premiers.

Aide
La liste des nombres premiers inférieurs ou égaux à 10001\,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]
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 pp est un nombre premier supérieur ou égal à 55, alors p21p^2-1 est un multiple de 2424.


2. On choisit un nombre entier naturel nn inférieur ou égal à 10001\,000 tel que n21n^2-1 soit divisible par 2424. Estimer à l’aide d’une fonction Python la probabilité que nn soit un nombre premier.

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



Voir les réponses

11
PPCM\text{PPCM} ★★★

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 PGCD\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 PPCM\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]]
Voir les réponses

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 nn, on appelle nn-ième nombre de Fermat le nombre Fn=22n+1F_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 pp de Fn=22n+1F_n=2^{2^n}+1 est de la forme p=k×2n+1+1p=k\times 2^{n+1}+1, où kk est un entier.



Voir les réponses

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 nn, on appelle nn-ième nombre de Mersenne le nombre Mn=2n1\text{M}_n=2^n-1.
Pour que le nombre de Mersenne Mn\text{M}_n soit premier, il est nécessaire, mais pas suffisant, que nn soit lui-même premier.
Dresser la liste des huit premiers nombres de Mersenne premiers à l’aide d’une fonction Python.


Voir les réponses
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.