## exercice 1
def racines1(n):
    L = []
    for x in range(1,n):
        if x*x % n == 1:
            L.append(x)
    return L
    
def nbr1(p):
    L = []
    for n in range(2,p+1):
        L.append(len(racines1(n)))
    return L
    
## exercice 2
from math import log

def puis(a,n):
    L = []
    p = 1
    while p <= n:
        L.append(p)
        p = p * a
    return L

def sommes(L,M):
    N = []
    for x in L:
        for y in M:
            N.append(x+y)
    return N
    
def sol(n,a,b):
    L = puis(a,n)
    M = puis(b,n)
    N = sommes(L,M)
    return (n in N)

def sols(n,a,b):
	L = []
	k = 0
	pa = 1
	M = puis(b,n)
	while pa <= n :
		if n - pa in M:
			l = int(log(n-pa)/log(b))
			L.append((k,l))
		pa = pa * a
		k = k + 1
	return L


## exercice 3
def grandnombre(n):
    s = ""
    for k in range(1,n+1):
        s = s + str(k)
    return int(s)

def pgcd(a,b):
    x = a
    y = b
    while y != 0:
        (q,r) = divmod(x,y)
        x = y
        y = r
    return x

def pgcdmax(i,n):
    m = 0
    p = 0
    for k in range(1,n):
        a = grandnombre(k)
        b = grandnombre(k+i)
        d = pgcd(a,b)
        if d > m:
            m = d
            p = k
    return (p,m)
    

## exercice 4
def valeurs(f,n):
    L = []
    for i in range(n):
        L.append(f(i))
    return L


def f(x):
    return 10*sin(x)/(x+1)
    
    
def limite(L):
    n = len(L)
    d = 9*n//10
    Q = L[d:]
    m = min(Q)
    M = max(Q)
    return (m + M)/2
    
    
def convergente(L,e):
    n = len(L)
    d = 9*n//10
    lim = limite(L)
    for i in range(d,n):
        if abs(L[i] - lim) > e:
            return False
    return True


## exercice 5
from math import sqrt

def dist(p,q):
    return sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)


def ppv(x,L):
    n = len(L)
    p = L[0]
    dp = dist(x, L[0])
    for i in range(1,n):
        d = dist(x, L[i])
        if d < dp:
            p = L[i]
            dp = d
    return p



def nplv(x,L):
    n = len(L)
    p = L[0]
    dp = dist(x, L[0])
    np = 0
    for i in range(1,n):
        d = dist(x, L[i])
        if d > dp:
            p = L[i]
            dp = d
            np = i
    return np
    
    
def ppvs(x,k,L):
    n = len(L)
    if n < k:
        return L
    else:
        P = L[0:k]
        # pl : le plus éloigné des k plus proches, dl la distance
        npl = nplv(x,P)
        dl = dist(x, P[npl])
        #
        for i in range(k,n):
            d = dist(x, L[i])
            if d < dl:
                P[npl] = L[i]
                npl = nplv(x,P)
                dl = dist(x, P[npl])
        return P