Python en mathématiques - Niveau 1

Un peu d'arithmétique

Plus tard ! Les exercices de cette page peuvent (doivent) être réservés à une seconde lecture.

Décomposition en facteurs premiers

É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.

  • Une solution

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]

Algorithme (crible) d'Ératosthène

Principe du crible

On dispose d'une liste L des entiers de 2 à n.

  1. On entoure 2 et on barre ses multiples dans la liste.
  2. On entoure le premier entier non barré et on barre ses multiples dans la liste.
  3. On renvoie au point 2 tant qu'il reste des entiers non entourés ou non barrés dans la liste.

Questions

  1. Quels sont les entiers entourés en fin de procédure ?
  2. Programmer cet algorithme en langage Python.
  • Question 1
  • Question 2
  • Question 2, code modifié

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 retourné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) :


		
		

Liste des chiffres d'un entier

Écrire une fonction en Python 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]
	
  • Concaténation de liste
  • Une solution
  • Une solution avec astuce
  • Encore une solution

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.


		
		

Remarques

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 :


		
		

Variante

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]

Énigme

  1. Écrire une fonction en Python 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
  2. Le facteur apporte le courrier à madame Gtroifi.
    • Le facteur : "Quels âges ont vos trois filles ?"
    • Madame Gtroifi : "Le produit de leurs âges est égal à 36. Et la somme de leurs âges est égale au numéro de la maison."
    • Le facteur : "Hum, il me manque des données."
    • Madame Gtroifi : "L'aînée joue de la guitare."
    • Le facteur : "Je connais maintenant leurs âges."

    Quels sont les âges des trois filles ?

  3. A l'aide d'un programme, déterminer les entiers 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.
  4. Modifier le programme de la question précédente pour ne retenir que les cas où la somme répétée présente de plus des "jumelles" dans l'un des triplets de décomposition.
  • Question 1
  • Question 2
  • Question 3
  • Question 4

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 a \( a^3 \leqslant n \) car si \(a^3 > n\) alors \( abc \geqslant a^3 > n \).
  • On a \( b^2 \leqslant n \) car si \(b^2 > n\) alors \( abc \geqslant 1\times b^2 > n \).

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]