## TP3 -- Premiers programmes



## Exercise 3.1 -- Test de primalité

def isPrime(n):
	if n == 1:
		return False
	else:
		for k in range(2, n):
			if n%k == 0:
				return False
		return True



## Exercise 3.2 -- Calcul d'une somme

def doubleSomme(n):
	S = 0
	for i in range(1, n+1):
		for j in range(i, i**2+1):
			S = S + i/j
	return S



## Exercise 3.3 -- Divergence d'une suite

## question 1)

def doubleSomme(n):
	S = 0
	for i in range(1, n+1):
		for j in range(i, i**2+1):
			S = S + i/j
	return S

## question 2)

def isPrime(n):
	if n == 1:
		return False
	else:
		for k in range(2, n):
			if n%k == 0:
				return False
		return True



## Exercise 3.4 -- Un exemple de série divergente

## question 1)

def S(n):
	S = 0
	for k in range(1, n+1):
		S = S + 1/k**0.5
	return S
	
# Voilà une solution récursive :
def S_rec(n):
	if n == 0:
		return 0
	else:
		return S_rec(n-1) + 1/n**0.5

## question 3)

# Voilà la solution naïve à cette question :
def valeurSeuil(A):
	n = 0
	while S(n) <= A:
		n = n+1
	return n
	
# Voilà une solution beaucoup plus rapide.
# Comme on le verra plus tard,
# la fonction précédente a une complexité en O(n^2) ;
# la suivante a une complexité en O(n)
def valeurSeuil_2(A):
	S = 0
	n = 0
	while S <= A:
		n = n+1
		S = S + 1/n**0.5
	return n



## Exercise 3.5 -- Algorithme de Babylone

## question 1) a)

# Voilà la solution naïve à cette question :
def u(n):
	valeurU = 2
	for k in range(n):
		valeurU = 1/2*(valeurU + 2/valeurU)
	return valeurU
	
# Voilà solution récursive :
def u_rec(n):
	if n == 0:
		return 2
	else:
		x = u_rec(n)
		return  1/2*(x + 2/x)

## question 2) a)

# Voilà la solution naïve à cette question :
def v(n, a):
	valeurV = 2
	for i in range(n):
		valeurV = 1/2*(valeurV + a/valeurV)
	return valeurV
	
# Voilà solution récursive :
def v_rec(n):
	if n == 0:
		return 2
	else:
		x = v_rec(n)
		return  1/2*(x + a/x)

## question 2) b)

def distance(n, a):
	x = 2**0.5
	return abs(v(n, a) - x)

## question 2) c)

L = (distance(150, 2), distance(150, 2e3), distance(150, 2e-3))
print(L)



## Exercise 3.6

## question 1) c)

def w(n):
	if n == 0:
		return 2
	valeurW_0 = 2
	valeurW_1 = 1
	for i in range(n-1):
		valeurW_0, valeurW_1 = valeurW_1, 4/(valeurW_0 + valeurW_1)
	return valeurW_1



## Exercise 3.7 -- Entiers de Syracuse

## question 1) c)

def isSyracuse(n):
	if n == 1:
		return
	elif n%2 == 0:
		isSyracuse(n//2)
	else:
		isSyracuse(3n+1)

## question 2) c)

def areFirstSyracuse(n):
	for k in range(1, n+1):
		isSyracuse(k)
	return True

## question 3) c)

def lengthSyracuse(n):
	if n == 0:
		return 0
	while n > 1:
		if n%2 == 0:
			return lengthSyracuse(n//2) + 1
		elif :
			return lengthSyracuse(3*n+1)

## question 4) c)

def heightSyracuse(n):
	record = 0
	k = n
	while k > 1:
		if k%2 == 0:
			k = k//2
		else:
			k = 3*k+1
		if k > record:
			record = k
	return record



## Exercise 3.8

## question 7) c)

def factorielle(n):
	if n == 0:
		return 1
	else:
		return n*factorielle(n-1)



## Exercise 3.9

## question 1) c)

def binom(n, k):
	if n == k or k == 0:
		return 1
	else:
		return binom(n-1, k) + binom(n-1, k-1)



## Exercise 3.10 -- Algorithme d'Euclide

## question 1) c)

41424241//3333

## question 2) c)

def PGCD(n, m):
	if m > n:
		return PGCD(m, n)
	if m == 0:
		return n
	return PGCD(m, n%m)

## question 3) c)

# Cet algorithme repose sur le calcul suivant :
# si r = n - qm et si u*m + v*r = d, alors d = v*n + (u-q)*m
def bezoutRelation(n, m):
	if m > n:
		(u, v, d) = bezoutRelation(n, m)
		return (v, u, d)
	if m == 0:
		return (1, 0, n)
	r = n%m
	q = n//m
	(u, v, d) = bezoutRelation(m, r)
	return (v, u-q, d)

## question 4) a)

# Cet algorithme repose sur le calcul suivant :
# si r = n - qm et si u*m + v*r = d, alors d = v*n + (u-q)*m
def verifieBezoutRelation(a, b, u, v, d):
	return a*u + b*v == d

## question 4) b)

import random as rd

def testeBezoutRelation(N):
	m = 2*N**0.5
	for _ in range(N):
		a, b = rd.randrange(m), rd.randrange(m)
		u, v, d = bezoutRelation(a, b)
		if not verifieBezoutRelation(a, b, u, v, d):
			return False
	return True
	
testeBezoutRelation(10**4)