#!/usr/bin/env python
# coding: utf-8

# <div class="alert alert-block alert-info">
# <center><font size=5><b>TP 4 (fonctions) : éléments de correction</b></font></center></div>

# ## <u>1. Définir une fonction</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 1 : occurences</b></font>
# </div>

# In[1]:


def Occurrences(a, L):
    """
    Renvoie le nombre d'occurences (i.e. d'apparitions)
    de l'élément a dans la liste L
    """
    n = 0  # initialisation du compteur
    for k in range(len(L)):
        if a == L[k]:  # test d'égalité + confusion entre k et L[k] + oubli des ":"
            n = n + 1
    return n  # mauvaise indentation


# In[2]:


# test avec la liste vide
Occurrences(1, [])


# In[3]:


# test avec plusieurs occurences
Occurrences(1, [1, 2, 3, 4, 1, 2, 3, 4, 1])


# In[4]:


# test sans occurrence
Occurrences(1, [2, 3, 4, 5])


# On pourrait également utiliser un autre type de parcours de liste, qui se fait élément par élément :

# In[5]:


def Occurrences(a, L):
    """
    Renvoie le nombre d'occurences (i.e. d'apparitions)
    de l'élément a dans la liste L
    """
    n = 0
    for elt in L:
        if a == elt:
            n = n + 1
    return n  


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 2 : premières fonctions</b></font>
# </div>

# ### Question 1

# On va utiliser une liste par compréhension :

# In[6]:


import random as rd


# In[7]:


def listealeatoire(n, a, b):
    """
    Renvoie une liste de n entiers aleatoires compris entre a et b.
    """
    return [rd.randint(a, b) for i in range(n)]


# In[8]:


listealeatoire(4, 1, 5)


# In[9]:


listealeatoire(0, 1, 10)


# In[10]:


listealeatoire(3, 2, 2)


# ### Question 2

# On adapte un script du TP précédent pour le transformer en fonction :

# In[11]:


def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    M = L[0]
    for k in range(len(L)):
        if L[k] > M:
            M = L[k]
    return M


# In[12]:


maxi([])


# Notre fonction ne fonctionne pas avec une liste vide...

# In[13]:


def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for k in range(len(L)):
            if L[k] > M:
                M = L[k]
        return M


# In[14]:


maxi([])


# In[15]:


maxi([1, 2, 3, 4, 5, 4, 3, 2, 1])


# In[16]:


maxi([5, 4, 3, 2, 1])


# **Remarque :**
# > on peut également utiliser un parcours des éléments de la liste ```L``` de la façon suivante :

# In[17]:


def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for elt in L:
            if elt > M:
                M = elt
        return M


# ### Question 3

# In[70]:


def mini(L):
    """
    Renvoie le minimum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for elt in L:
            if elt < M:
                M = elt
        return M


# In[77]:


def minmax(N, n, a, b):
    """
    genere N listes de n entiers aleatoires compris entre a et b,
    determine le maximum des elements de chacune de ces listes
    et renvoie le minimum de ces maximums.
    """
    if n==0:
        return None
    else:
        Lmax=[]
        for k in range(N):
            L=listealeatoire(n,a,b)
            M=maxi(L)
            Lmax.append(M)
        return mini(Lmax)


# In[78]:


minmax(0, 10, 2, 3)


# In[79]:


minmax(10, 0, 2, 3)


# In[80]:


minmax(10,12,1,5)


# In[ ]:





# In[18]:


def minmax(N, n, a, b):
    """
    genere N listes de n entiers aleatoires compris entre a et b,
    determine le maximum des elements de chacune de ces listes
    et renvoie le minimum de ces maximums.
    """
    if N == 0 or n == 0:
        return None
    else:
        L = listealeatoire(n, a, b)
        M = maxi(L)
        m = M
        for k in range(N - 1):
            L = listealeatoire(n, a, b)
            M = maxi(L)
            if M < m:
                m = M
        return m


# In[19]:


minmax(0, 10, 2, 3)


# In[20]:


minmax(10, 0, 2, 3)


# In[21]:


minmax(10,12,1,5)


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 3 : coefficients binomiaux</b></font>
# </div>

# In[22]:


def factorielle(n):
    """
    Renvoie la factorielle de n.
    """
    f = 1
    for k in range(1, n + 1):
        f = f * k
    return f


# ### Question 1

# In[23]:


def coeff(n, k):
    """
    Renvoie le coefficient binomial "k parmi n"
    """
    return factorielle(n) // factorielle(k) // factorielle(n - k)


# In[24]:


coeff(0, 0)


# In[25]:


coeff(3, 1)


# In[26]:


coeff(9, 6)


# In[27]:


[coeff(4, k) for k in range(5)]


# In[28]:


coeff(50, 13)


# In[29]:


coeff(10000, 9997)


# On peut même afficher le début du triangle de Pascal :

# In[30]:


for n in range(6):
    print([coeff(n, k) for k in range(n + 1)])


# ### Question 2

# In[31]:


def LigneSuivante(L):
    """
    Reçoit une liste de nombres L
    et renvoie la liste M définie comme dans l'énoncé
    """
    M = [L[0]]
    for k in range(1, len(L)):
        M.append(L[k - 1] + L[k])
    M.append(L[len(L) - 1])
    return M


# In[32]:


LigneSuivante([1, 5, 10, 10, 5, 1])


# Une variante, avec une liste par compréhension :

# In[33]:


def LigneSuivante(L):
    """
    Reçoit une liste de nombres L
    et renvoie la liste M définie comme dans l'énoncé
    """
    M = [L[0]] + [L[k - 1] + L[k] for k in range(1, len(L))] + [L[len(L) - 1]]
    return M


# In[34]:


LigneSuivante([1, 5, 10, 10, 5, 1])


# In[35]:


LigneSuivante([1])


# ### Question 3

# In[36]:


def Pascal(N):
    """
    Affiche les N premieres lignes du triangle de Pascal.
    """
    L = [1]
    print(L)
    for k in range(N):
        L = LigneSuivante(L)
        print(L)
    return None


# In[37]:


Pascal(5)


# On pourrait chronométrer les 2 façons de faire pour voir que la 2ème est plus efficace : vous pouvez vous inspirer de l'exercice 6 pour faire des tests chez vous !

# ## <u>2. Nombres premiers</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 4 : algorithme naïf </b></font>
# </div>

# ### Questions 1 et 2

# In[38]:


from math import sqrt


# In[39]:


def estpremier(n):
    """
    Teste si un nombre entier naturel est premier.
    """
    if n == 0 or n == 1:
        return False
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


# In[40]:


for n in range(21):
    if estpremier(n):
        print(n, end=' ')
print()  # pour le retour a la ligne


# ### Question 3

# On peut utiliser un compteur pour chaque nombre premier :

# In[41]:


cpt = 0
for n in range(1001):
    if estpremier(n):
        cpt += 1
print("Il y a {} nombres premiers inférieurs (ou égaux) à 1000.".format(cpt))


# Python est assez souple en ce qui concerne les sommes : il peut sommer des booléens (```True``` vaut alors 1 et ```False``` vaut 0). On peut donc également proposer la version suivante :

# In[42]:


S = sum([estpremier(n) for n in range(1001)])


# In[43]:


print("Il y a {} nombres premiers inférieurs (ou égaux) à 1000.".format(S))


# ### Question 4

# On va utiliser une boucle ```while```, jusqu'à obtenir un nombre premier :

# In[44]:


n = 10**10
while not (estpremier(n)):
    n = n + 1
print("Le plus petit nombre premier supérieur à 10**10 est {}.".format(n))


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 5 : crible d'Ératosthène</b></font>
# </div>

# In[45]:


def Crible(N):
    """
    Implémente le crible d'Eratosthene
    """
    C = [True for k in range(N)]
    C[0] = False
    C[1] = False
    for k in range(2, N):
        if C[k]:
            for i in range(2*k,N,k):
                C[i] = False
    return (C)


# In[46]:


C1 = Crible(20)
for n in range(20):
    if C1[n]:  # Test : n est-il premier ?
        print(n, end=' ')
print()


# On peut également utiliser une liste définie par compréhension (avec une condition) :

# In[47]:


[n for n in range(20) if C1[n]]


# On retrouve également le résultat de la question 3 de l'exercice précédent :

# In[48]:


C2 = Crible(1000)
c = 0
for n in range(1000):
    if C2[n]:
        c += 1
print(c)


# ou bien également :

# In[49]:


sum(C2)


# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 6 : comparaison des algorithmes</b></font>
# </div>

# In[50]:


from time import time


# In[51]:


N = 100

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)


# In[52]:


N = 10**4

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)


# In[53]:


N = 10**5

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)


# ## <u>3. Compléments</u>

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 7 : nombres parfaits et amis</b></font>
# </div>

# ### Question 1

# Dès qu'on le peut, on utilise une liste par compréhension :

# In[54]:


def diviseurs(n):
    """
    reçoit un entier n positif,
    et renvoie la liste de ses diviseurs autres que lui-meme.
    """
    D = [k for k in range(1, n) if n % k == 0]
    return D


# In[55]:


diviseurs(12)


# On peut bien sûr quand même construire la liste élément par élément :

# In[56]:


def diviseurs(n):
    """
    Reçoit un entier n positif,
    et renvoie la liste de ses diviseurs autres que lui-meme.
    """
    D = []
    for k in range(1, n):
        if n % k == 0:
            D.append(k)
    return D


# In[57]:


diviseurs(30)


# ### Question 2 : nombres parfaits

# On dresse la liste de tous les nombres
# parfaits strictement inférieurs à $10^4$ :

# In[58]:


P = []
N = 10**4
for n in range(N):
    D = diviseurs(n)
    if n == sum(D):
        P.append(n)
print(P)


# ### Question 3 : Nombres amis

# Une première version, naïve et peu efficace :

# In[59]:


A = []
N = 10**3
for a in range(N):
    for b in range(a + 1, N):  # pour éviter les doublons
        if a == sum(diviseurs(b)) and b == sum(diviseurs(a)):
            A.append((a, b))
print(A)


# Pour éviter de refaire trop de fois les mêmes calculs, on peut proposer la variante suivante :

# In[60]:


A = []
N = 10**4
for a in range(N):
    Da = sum(diviseurs(a))
    for b in range(a + 1, N):  # pour éviter les doublons
        if b == Da:
            Db = sum(diviseurs(b))
            if a == Db:
                A.append((a, b))
print(A)


# **Remarque :**
# >On pourrait même faire encore moins de calculs en enregistrant chaque calcul de somme des diviseurs dans une variable : ce sera possible avec ce que l'on appelle un "dictionnaire", que nous étudierons dans le prochain TP.

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 8 : nombres premiers jumeaux</b></font>
# </div>

# In[61]:


def jumeaux(n):
    """
    Teste si n et n+2 sont premiers
    """
    C = Crible(n + 3)
    if C[n] and C[n + 2]:
        return True
    else:
        return False


# On peut simplifier la syntaxe pour le ```return``` :

# In[62]:


def jumeaux(n):
    """
    Teste si n et n+2 sont premiers
    """
    C = Crible(n + 3)
    return C[n] and C[n + 2]


# In[63]:


jumeaux(3)


# In[64]:


jumeaux(7)


# In[65]:


N = 2**20
cpt = 0  # compteur
C = Crible(N + 1)
for n in range(N - 2):
    if C[n] and C[n + 2]:
        # print((n,n+2)) # ça prend trop de place à l'affichage
        cpt = cpt + 1
print("Il y a {} couples de nombres premiers jumeaux inférieurs à 2**20.".format(cpt))


# **Remarque :**
# > on n'a pas utilisé la fonction ```jumeaux``` pour ne pas recalculer le crible à chaque fois...

# <div style="border-radius:15px;-webkit-border-radius:15px;-moz-border-radius:15px;width:37%;float:center;background-color:#CBD6E7;margin-left:0;padding:10px;text-align:center;">
#     <font size=3><b>Exercice 9 : conjecture de Goldbach</b></font>
# </div>

# In[66]:


C = Crible(101)  # c'est une variable globale


def sommepremier(n):
    """
    Teste si n peut s'écrire comme somme de 2 nombres premiers
    Affiche le premier couple possible le cas échéant
    """
    assert (n % 2 == 0)
    for k in range(2, n // 2 + 2):
        if C[k] and C[n - k]:
            print("{0} = {1} + {2}".format(n, k, n - k))
            return True
    return False


# In[67]:


for n in range(2, 101, 2):
    sommepremier(n)


# In[68]:


def goldbach(n):
    """
    Teste si n peut s'écrire comme somme de 2 nombres premiers
    """
    assert (n % 2 == 0)
    for k in range(2, n // 2 + 2):
        if C[k] and C[n - k]:
            return True
    return False


# Ici encore, ```C``` est une variable globale. Si on ne souhaite pas utiliser de variable globale, on pourrait la passer en paramètre de la fonction ```goldbach```.

# In[69]:


N = 2**20
C = Crible(N + 2)  # c'est une variable globale
k = 4
conjecture = goldbach(k)
while conjecture and k <= N:
    k += 2
    conjecture = goldbach(k)
print("La conjecture de Goldbach est-elle vérifiée jusqu'au rang N ?",conjecture)