Python en mathématiques - Défis

Nombres premiers ?

Génère des premiers ?

Un saucissonnage des premiers entiers premiers.

On note $ p_1=2; p_2=3; p_3=5; p_4=7; \dots $ et plus généralement $p_n$ le $n$-ième entier naturel premier.

A partir de l'ensemble $\mathcal{E}= \lbrace p_1; p_2; ...; p_n \rbrace$, on crée deux sous-ensembles $A$ et $B$ disjoints recouvrant $\mathcal{E} $.

On note $p(A)$ le produit des éléments de la partie A (resp. $p(B)$) -- avec la convention: $ p(\varnothing) = 1$.

On note ensuite $s(A, B)= p(A)+p(B)$ et $d(A, B) = \left| p(A)-p(B) \right| $.

Exemples

Avec $ \mathcal{E}= \lbrace p_1; p_2; p_3 \rbrace = \lbrace 2; 3; 5 \rbrace $, créons $A= \lbrace 2; 3; 5 \rbrace $ et $B= \varnothing $. On a dans ce cas $s(A, B) = 2\times 3 \times 5 +1 = 31$ et $d(A ,B) = 2\times 3 \times 5 -1 = 29$.

Avec $ \mathcal{E}= \lbrace 2; 3; 5; 7 \rbrace $, créons $A= \lbrace 2; 5 \rbrace $ et $B= \lbrace 3; 7 \rbrace $. On a dans ce cas $s(A, B) = 2\times 5 + 3\times 7 = 31$ et $d(A, B) = \left|2\times 5 - 3\times 7\right| = 11$.

Programmation

Écrire un programme python qui tire un entier n au hasard puis deux sous-parties A et B au hasard comme expliqué ci-dessus à partir de l'ensemble $\mathcal{E}= \lbrace p_1; p_2; ...; p_n \rbrace$.

On définira une fonction S(A, B) telle que S(A, B)=$s(A, B)$ si $s(A, B) < p_{n+1}^2$ et S(A, B)= $p_{n+1}$ sinon.

On définira de même une fonction D(A, B) telle que D(A, B)=$d(A, B)$ si $d(A, B) < p_{n+1}^2$ et D(A, B)=$p_{n+1}$ sinon.

Conjecture et preuve

  1. Ajouter un test de primalité de S(A, B) et D(A, B).
  2. Quelle conjecture peut-on émettre ?
  3. Démontrer ou infirmer la conjecture.
  • Un script possible
  • Conjecture et preuve

from math import sqrt
from random import randint, shuffle

def est_premier(n):
	"""
	n est un entier > 1.
	La fonction renvoie True si n est premier, False sinon.
	"""
	
	d = 2
	while d <= sqrt(n):
		if n%d == 0 : return False
		d += 1
	return True
	
	
def liste_premiers(n):
	"""
	n est un entier naturel.
	La fonction renvoie la liste des n plus petits entiers premiers.
	"""
	liste = []
	entier = 2
	while len(liste) < n :
		if est_premier(entier): 
			liste.append(entier)
		entier += 1
	return liste
		
	
def decoupe(n):
	"""
	n est un entier naturel non nul.
	Soit L la liste des n plus petits entiers premiers.
	La fonction renvoie deux sous-listes A et B de L, disjointes, recouvrant L et le n+1 ème nombre premier.
	A ou B est éventuellement vide.
	"""
	# liste des n+1 plus petits entiers naturels premiers :
	LL = liste_premiers(n+1)
	# liste des n plus petits entiers naturels premiers :
	L = LL[:-1]
	# on mélange la liste L :
	shuffle(L)
	# choix de la longueur de la sous-liste A au hasard entre 0 et n :
	lg = randint(0,n)
	return L[:lg], L[lg:], LL[-1]
	
	
def produit(liste):
	"""
	liste est une liste d'entiers. 
	La fonction renvoie le produit des éléments de cette liste.
	Le produit des éléments d'une liste vide est égal à 1.
	"""
	p = 1
	for m in liste:
		p *= m
	return p
	
	
def somme(n):
	"""
	n est un entier naturel non nul.
	La fonction construit la liste des n plus petits entiers naturels premiers,
	découpe cette liste en deux sous-listes A et B
	puis renvoie la somme du produit des éléments de A et du produit des éléments de B si cette 
	somme est inférieure au carré du n+1 ème entier premier  et renvoie le n+1 ème nb premier sinon .
	"""
	A, B, p = decoupe(n)
	s = produit(A) + produit(B)
	if s < p*p :
		return s
	else: 
		return p
	
	
def difference(n):
	"""
	n est un entier naturel non nul.
	La fonction construit la liste des n plus petits entiers naturels premiers,
	découpe cette liste en deux sous-listes A et B
	puis renvoie la valeur absolue de la différence du produit des éléments de A et du produit des éléments de B
	si cette valeur est inférieure au carré du n+1 ème entier premier  et renvoie le n+1 ème nb premier sinon .
	"""
	A, B, p = decoupe(n)
	d = abs(produit(A) - produit(B))
	if d < p*p :
		return d
	else: 
		return p
	
 
	
	
	
n = randint(2,5)

s = somme(n)
d = difference(n)

print(s), print(est_premier(s))
print(d), print(est_premier(d))

Conjecture

Les sorties sont toujours des nombres premiers.

Preuve

Lorsque la sortie est $p_{n+1}$, elle est première. Il reste à traiter le cas d'une sortie distincte de $p_{n+1}$.

Chacun des nombres premiers $p_1, p_2, \dots, p_n$ divise A ou B mais pas les deux. Donc aucun ne divise A+B.

Un diviseur premier $p$ de A+B vérifie donc $ p \geqslant p_{n+1}$.

Par ailleurs, si A+B est composé, il possède au moins deux facteurs premiers et on aurait donc $A+B \geqslant p_{n+1}\times p_{n+1} $. Ce que l'on a exclu.

A+B est donc premier.

Le même raisonnement vaut pour $d(A, B)$.