Les exercices de cette page peuvent (doivent) être réservés à une
seconde lecture.
Un peu d'arithmétique
Les exercices de cette page peuvent (doivent) être réservés à une
seconde lecture.
Écrire une fonction en Python
nommée liste_facteurs()
qui respecte le cahier des charges
suivant :
Paramètres | un entier naturel n > 1 |
---|---|
Valeur renvoyée | liste des entiers de la décomposition en facteurs premiers de n |
Recherchez ensuite l'ensemble des facteurs premiers des entiers successifs
de 2
à 30
.
def liste_facteurs(n):
L = [] # contiendra les diviseurs premiers
d = 2 # premier diviseur potentiel
while n > 1 :
while n%d == 0:
L.append(d)
n = n//d
d += 1
return L
>>> for k in range(2, 31): liste_facteurs(k) [2] [3] [2, 2] [5] [2, 3] [7] [2, 2, 2] [3, 3] [2, 5] [11] [2, 2, 3] [13] [2, 7] [3, 5] [2, 2, 2, 2] [17] [2, 3, 3] [19] [2, 2, 5] [3, 7] [2, 11] [23] [2, 2, 2, 3] [5, 5] [2, 13] [3, 3, 3] [2, 2, 7] [29] [2, 3, 5]
On dispose d'une liste L
des entiers de 2
à n
.
Les entiers entourés sont les nombres premiers inférieurs ou égaux à n
.
Voici l'idée générale du programme présenté ci-dessous : la liste renvoyée
contiendra n
booléens. Leur valeur sera True
lorsque l'indice correspondant est un entier entouré dans le crible
ou False
lorsque l'indice est un entier barré.
La condition d'arrêt p*p <= n
s'explique par le fait
que lorsque k*d = n
, l'un ou l'autre des deux diviseurs
k
ou d
est au plus $ \sqrt{n} $ (sinon le
produit k*d
est supérieur à n
).
Même solution que la précédente, mais avec des listes définies par compréhension (au programme de 1ère) :
Écrire une fonction en Python
nommée liste_chiffres
qui respecte la spécification suivante :
Paramètres | un entier naturel |
---|---|
Valeur renvoyée | liste des chiffres de l'entier naturel (en base 10) |
Voici un exemple d'utilisation :
>>> liste_chiffres(123) [1, 2, 3]
Le symbole d'addition « + » permet de concaténer des listes de la même façon qu'il concatène les chaînes de caractères :
Cette solution utilise la concaténation de liste :
Pour n
de type int
, ~n
est
équivalent à -n-1
. Nous utilisons cette opération dans
la solution ci-dessous.
La documentation sur l'opération « ~
»
est disponible via ce lien.
La fonction liste_chiffres()
pouvait aussi être définie
avec une lecture par tranche et à l'envers de la liste
(hors programme de lycée) :
def liste_chiffres(n) :
""" liste avec chiffre poids fort en L[0]."""
L = liste_chiffres_contresens(n)
return L[::-1] # Lecture du dernier au 1er terme
Il est également possible de procéder par changement de type :
En utilisant les listes en compréhension :
def liste_chiffres(n) :
""" liste avec chiffre poids fort en L[0]."""
L = list(str(n))
return [int(x) for x in L]
triplet_produit()
, qui respecte la spécification
suivante :
Paramètres | un entier naturel n non nul |
---|---|
Valeur renvoyée | liste des triplets d'entiers dont le produit est égal à n |
Quels sont les âges des trois filles ?
n
(inférieurs
à une borne M
fixée à l'avance) ayant la propriété
suivante : ils peuvent se décomposer en produit de trois entiers et au
moins deux triplets différents donnent la même somme.
Puisqu'on a lu la deuxième question, on en profite pour tester la fonction en décomposant le nombre 36 :
def triplet_produit(n) :
L = []
for a in range(1, int(n**(1/3))+1) :
for b in range(a, int(n**0.5)+1 ) :
c = n // (a*b)
if a*b*c == n and c >= b:
L.append([a,b,c])
return L
Nous présentons ci-dessous une manière plus agréable de visualiser le contenu d'une liste de listes :
>>> for t in triplet_produit(36): t [1, 1, 36] [1, 2, 18] [1, 3, 12] [1, 4, 9] [1, 6, 6] [2, 2, 9] [2, 3, 6] [3, 3, 4]
On tente d'obtenir les triplets (a, b, c)
tels que
a
$\leqslant$ b
$\leqslant$ c
avec a*b*c = n
.
Les bornes choisies s'expliquent par le raisonnement suivant :
On peut éviter la racine cubique avec les instructions suivantes :
def triplet_produit(n) :
L = []
a = 1
while a*a*a <= n :
for b in range(a, int(n**0.5)+1 ) :
c = n // (a*b)
if a*b*c == n and c >= b :
L.append([a, b, c])
a += 1
return L
On ajoute les sommes des triplets à la fin de la liste renvoyée :
def triplet_produit_plus(n) :
L = []
a = 1
while a*a*a <= n :
for b in range(a, int(n**0.5)+1 ) :
c = n // (a*b)
if a*b*c == n and c >= b :
L.append([a, b, c, a+b+c])
a += 1
return L
On obtient 16 triplets suivis de leur somme :
>>> for t in triplet_produit_plus(36): t [1, 1, 36, 38] [1, 2, 18, 21] [1, 3, 12, 16] [1, 4, 9, 14] [1, 6, 6, 13] [2, 2, 9, 13] [2, 3, 6, 11] [3, 3, 4, 10]
Si le facteur a encore un doute avec la somme, c'est qu'il y a ambiguïté. Le seul cas laissant un doute est le cas de la somme 13. Comme il y a une aînée, on élimine le triplet 1, 6, 6 et les âges des filles de Mme Gtroifi sont 2, 2, 9.
Prenez le temps de bien analyser la ligne 21 de notre proposition de solution.
def triplet_produit_plus(n) :
L = []
a = 1
while a*a*a <= n :
for b in range(a, int(n**0.5)+1 ) :
c = n // (a*b)
if a*b*c == n and c >= b :
L.append([a,b,c, a+b+c])
a += 1
return L
def liste_sommeNonUnique(n) :
""" renvoie la liste des triplets (a,b,c) de produit n en ne gardant que les
triplets donnant une somme obtenue avec un autre triplet."""
L_triplet = triplet_produit_plus(n)
L = []
for i in range(len(L_triplet)) :
if L_triplet[i][3] in [L_triplet[j][3] for j in range(len(L_triplet)) if j!=i] :
L.append(L_triplet[i])
return L
def cas_interessant(M) :
"""renvoie les valeurs de n <= M pouvant se décomposer en produits de trois entiers
de diverses façons avec une même somme."""
L = []
for k in range(2,M+1):
if len(liste_sommeNonUnique(k)) != 0 :
L.append(k)
return L
On teste :
>>> cas_interessant(200) [36, 40, 72, 90, 96, 126, 144, 168, 176, 200]
def triplet_produit_plus(n) :
L = []
a = 1
while a*a*a <= n :
for b in range(a, int(n**0.5)+1 ) :
c = n // (a*b)
if a*b*c == n and c >= b :
L.append([a,b,c, a+b+c])
a += 1
return L
def liste_sommeNonUnique_etDoublon(n) :
""" renvoie la liste des triplets (a,b,c) de produit n en ne gardant que les
triplets donnant une somme obtenue avec un autre triplet."""
L_triplet = triplet_produit_plus(n)
L = []
for i in range(len(L_triplet)) :
if L_triplet[i][3] in [L_triplet[j][3] for j in range(len(L_triplet)) if j!=i] :
if L_triplet[i][0] == L_triplet[i][1] or L_triplet[i][1] == L_triplet[i][2] :
L.append(L_triplet[i])
return L
def cas_interessant(M) :
"""renvoie les valeurs de n <= M pouvant se décomposer en produits de trois entiers
de diverses façons avec une même somme."""
L = []
for k in range(2,M+1):
if len(liste_sommeNonUnique_etDoublon(k)) != 0 :
L.append(k)
return L
On teste :
>>> cas_interessant(1000) [36, 40, 72, 90, 144, 225, 234, 252, 288, 297, 320, 360, 432, 450, 576, 648, 675, 720, 784, 800, 816, 850, 880, 900, 972]