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
- Ajouter un test de primalité de
S(A, B)
etD(A, B)
. - Quelle conjecture peut-on émettre ?
- 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)$.