(* Exercice 1 *)
let rec s n =
  match n with
    | 0 -> 0
    | n -> n + s(n-1)
;;

let rec sRecTerminale n =
  let rec sRecTerminaleAux n acc = match n with
    | 0 -> acc
    | n -> sRecTerminaleAux (n-1) (acc+n)
  in sRecTerminaleAux n 0
;;

sRecTerminale 9 ;;

(* Exercice 2 *)

(* Q1 *)
let rec puissance x n = match n with
  | 0 -> 1
  | _ -> x * puissance x (n-1)
;;

puissance 10 5 ;;

(* Q2 *)
let puissance_terminale x n =
  let rec puissance_acc x n acc = match n with
    | 0 -> acc
    | _ -> puissance_acc x (n-1) (x*acc)
  in puissance_acc x n 1
;;

puissance_terminale 10 5 ;;

(* Q3 *)
let rec expo_rapide x n = match n with
  | 0 -> 1
  | n when n mod 2 = 0 -> expo_rapide (x*x) (n/2)
  | _ -> x * expo_rapide (x*x) ((n-1)/2)
;;

let expo_rapide_terminale x n  =
  let rec exp_aux x n acc = match n with
    | 0 -> acc
    | n when n mod 2 = 0 -> exp_aux (x*x) (n/2) acc
    | _ -> exp_aux (x*x) ((n-1)/2) (x*acc)
  in exp_aux x n 1
;;

expo_rapide 3 40000000000000 ;;

expo_rapide_terminale 3 40000000000000 ;;

(* Exercice 3 *)
let rec u n = match n with 
  | 0 -> 1.
  | _ -> (u(n-1)) /. (3. +. u(n-1))
;;

let rec u' n = match n with 
  | 0 -> 1.
  | _ -> let v = u'(n-1) in v /. (3. +. v)
;;

u 28 ;;

u' 28 ;;

u' 600 ;;

(* Exercice 4 *)

let rec u n = match n with
  | 0 -> 2
  | 1 -> 1
  | _ -> u(n-1) - 2*u(n-2)
;;

u 6 ;;

(* Exercice 5 *)

let rec pgcd u v = match v with
  | 0 -> u
  | _ -> pgcd v (u mod v)
;;

pgcd 12 42 ;;

(* Exercice 6 *)

let rec nb_chiffres n b = match n with
  | 0 -> 0
  | n when n < b -> 1
  | _ -> 1 + nb_chiffres (n/b) b
;;

nb_chiffres 1242 10 ;;

(* Exercice 7 *)
let rec mystere f n m = match n with
  | n when n > m -> 1.
  | _ -> f(float_of_int n) *. mystere f (n+1) m
;;

mystere sin 1 100 ;;

(* Exercice 8 *)
let rec fibo n = match n with
  | 0 -> 1
  | 1 -> 1
  | _ -> fibo(n-1) + fibo(n-2)
;;

#trace fibo ;;

fibo 6 ;;

#untrace fibo ;;

(* Exercice 9 : Algorithme de Floyd *)

let f x = (x*x + 92) mod 32069 ;;

f 8 ;;

(* Q1 *)
let rec itere f x0 n = match n with
  | 0 -> x0
  | _ -> f(itere f x0 (n-1))
;;

(* Q2 *)
let rec itereBis f x0 n = match n with
  | 0 -> x0
  | _ -> itereBis f (f x0) (n-1)
;;

(* Q3 *)
let floyd1 f x0 =
  let rec floydAux f x y = match x,y with
    | x,y when x=y -> x
    | x,y -> floydAux f (f(x)) (f(f(y)))
  in floydAux f (f(x0)) (f(f(x0)))
;;

floyd1 f 33 ;;

(* Q4 *)
let floyd2 f x0 =
  let rec floydAux f x y acc = match x,y with
    |x,y when x=y -> acc
    |x,y -> floydAux f (f(x)) (f(f(y))) (acc+1)
  in floydAux f (f(x0)) (f(f(x0))) 1 ;;

floyd2 f 33 ;;

(* Q6 *)
let periode f x0 =
  let i = floyd2 f x0 in
  floyd2 f (itere f x0 i)
;;

periode f 33 ;;

(* Q7 *)
let prePeriode f x0 =
  let xi = floyd1 f x0 in
  let rec aux mu x y = match x,y with
    | x,y when x= y-> mu
    | x,y-> aux (mu+1) (f x) (f y)
  in aux 0 x0 xi
;;

prePeriode f 33 ;;

(* Q8 *)
let brent f x0 =
  let rec brentAux f i j xi xj = match j with
    | j when xi = xj -> (i,j)
    | j when j <= 2*i -> brentAux f i (j+1) xi (f xj)
    | j -> brentAux f j (j+1) xj (f xj)
  in brentAux f 0 1 x0 (f x0)
;;

brent f 33 ;;