{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2a6e4727",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 5\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Introduction à Sagemath\n",
    "* Calcul exact : entiers, rationnels, complexes\n",
    "* Notions sur le calcul symbolique\n",
    "* Notion de méthode et de classe\n",
    "```\n",
    "\n",
    "\n",
    "## Exercice 1. Manipulation élémentaire d'entiers, de rationnels et de complexes\n",
    "\n",
    "\n",
    "**Question 1.** Donner la valeur exacte des quantités suivantes :\n",
    "- $12!$\n",
    "- le rationnel $\\frac{8778}{4557}$\n",
    "- le plus petit nombre premier supérieur à $2^{20}$\n",
    "- $\\cos(2\\pi/5)$\n",
    "- la partie réelle de $3 e^{7 i \\pi/12}$\n",
    "- l'argument de $1+i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a25ecc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(factorial(12))\n",
    "print(8778/4557)\n",
    "print(next_prime(2**20))\n",
    "print(cos(2*pi/5))\n",
    "print((3*e**(7*i*pi/12)).real_part())\n",
    "print(arg(1+I))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38e1061f",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `plus_petit_module(liste)` qui prend en entrée une liste `liste` de nombres complexes, et qui retourne le nombre complexe de plus petit module de cette liste. Si la liste est vide, la fonction devra **afficher** un texte d'erreur, puis **retourner** le mot-clef `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05966453",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plus_petit_module(liste):\n",
    "    if liste == []:\n",
    "        print(\"Erreur : la liste est vide\")\n",
    "        return None\n",
    "    else:\n",
    "        n = len(liste)\n",
    "        element = liste[0]\n",
    "        for i in range(1, n):\n",
    "            if liste[i].abs() < element.abs():\n",
    "                element = liste[i]\n",
    "        return element\n",
    "\n",
    "plus_petit_module([3+2*I, I/2, e**(I*pi/5) - e**(2*I*pi/3)])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fc1562a",
   "metadata": {},
   "source": [
    "## Exercice 2.  Somme de binomiaux\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `somme_newton(n)` qui prend en entrée un entier `n` et qui retourne  la valeur de la somme \n",
    "\n",
    "$$\\sum_{k=0}^n \\binom{n}{k}.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09a4a60e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme_newton(n):\n",
    "    somme = 0\n",
    "    for k in range(n+1):\n",
    "        somme += binomial(n, k)\n",
    "    return somme\n",
    "    \n",
    "somme_newton(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b9098e9",
   "metadata": {},
   "source": [
    "**Question 2.** Vérifier que pour tout $n$ compris entre $0$ et $100$, l'égalité  $\\sum_{k=0}^n \\binom{n}{k} = 2^n$ est bien vérifiée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9277043b",
   "metadata": {},
   "outputs": [],
   "source": [
    "all(somme_newton(n) == 2**n for n in range(101))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "642cb3d7",
   "metadata": {},
   "source": [
    "**Question 3.** Écrire une fonction `somme_binomiaux(n)` qui prend en entrée un entier `n` et qui retourne la valeur de la somme \n",
    "\n",
    "$$\n",
    "\\sum_{k=0}^n \\frac{(-1)^k}{k+1} \\binom{n}{k}.\n",
    "$$\n",
    "\n",
    "Puis, calculer plusieurs valeurs de cette somme, émettre une conjecture, puis la \"vérifier\" sur les valeurs de $n$ comprises en $0$ et $100$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b62f94b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme_binomiaux(n):\n",
    "    somme = 0\n",
    "    for k in range(n+1):\n",
    "        somme += (-1)**k * binomial(n, k) / (k+1)\n",
    "    return somme\n",
    "    \n",
    "print(somme_binomiaux(1))\n",
    "print(somme_binomiaux(4))\n",
    "print(somme_binomiaux(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d82115f4",
   "metadata": {},
   "source": [
    "Notre conjecture est que cette somme vaut toujours $1/(n+1)$. Vérification :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c1b14979",
   "metadata": {},
   "outputs": [],
   "source": [
    "all(somme_binomiaux(n) == 1/(n+1) for n in range(101))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d9c4a71",
   "metadata": {},
   "source": [
    "## Exercice 3. Double boucle\n",
    "\n",
    "\n",
    "Dans cet exercice, on considère une liste $L = (L_0, \\dots, L_{n-1})$ de rationnels distincts, de longueur $n \\ge 2$.\n",
    "\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `produit_differences(L)`, qui prend en entrée la liste `L` de rationnels, et qui retourne la valeur du produit\n",
    "\n",
    "$$\n",
    "\\prod_{0 \\le i < j \\le n-1} \\frac{1}{L_j-L_i}\\,.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fbe0689",
   "metadata": {},
   "outputs": [],
   "source": [
    "def produit_differences(L):\n",
    "    n = len(L)\n",
    "    p = 1\n",
    "    for i in range(n):\n",
    "        for j in range(i+1,n):\n",
    "            p /= (L[j] - L[i])\n",
    "    return p\n",
    "\n",
    "L = [ 3, 1/2, 7/3, -2/3 ]\n",
    "print(produit_differences(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7c468a7",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `plus_proches(L)`, qui prend en entrée la liste `L` de rationnels, et qui retourne la paire $(a, b)$ de rationnels les plus proches parmi toutes les paires d'éléments de la liste `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13a32463",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plus_proches(L):\n",
    "    diff = abs(L[0]-L[1])\n",
    "    n = len(L)\n",
    "    for i in range(n):\n",
    "        for j in range(i):\n",
    "            if abs(L[i] - L[j]) < diff:\n",
    "                paire = [L[i], L[j]]\n",
    "                diff = abs(L[i] - L[j])\n",
    "    return paire\n",
    "    \n",
    "L = [ 3, 1/2, 7/3, -2/3 ]\n",
    "print(plus_proches(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc4d30ce",
   "metadata": {},
   "source": [
    "## Exercice 4.  Triplets pythagoriciens\n",
    "\n",
    "\n",
    "Un **triplet pythagoricien** est un triplet $(p, q, r) \\in \\mathbb{N}^3$ tel que $p^2 + q^2 = r^2$. Observons que, si $(p, q, r)$ est un triplet pythagoricien, alors $p \\le r$ et $q \\le r$.\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `trouve_triplets(r)`, qui prend entrée un entier naturel `r`, et qui retourne la liste de toutes les paires $(p, q)$ telles que $(p, q, r)$ forme un triplet pythagorien."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "527f9f62",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve_triplets(r):\n",
    "    return [ (p, q) for p in range(r+1) for q in range(r+1) if p**2 + q**2 == r**2 ]\n",
    "    \n",
    "trouve_triplets(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b43bcfa",
   "metadata": {},
   "source": [
    "Tout triplet pythagoricien peut être associé à un point du cercle unité dont les coordonnées sont des rationnels. En effet, \n",
    "\n",
    "$$p^2 + q^2 = r^ 2 \\iff (p/r)^2 + (q/r)^2 = 1 \\iff (p/r, q/r) \\, \\text{ est un point rationnel du cercle unité } $$\n",
    "\n",
    "Par ailleurs, si $(\\alpha, \\beta) \\in \\mathbb{Q}^2$ est sur le cercle unité, alors en écrivant $\\alpha = a/n$ et $\\beta = b/n$ sur le même dénominateur $n$, on obtient un triplet pythagoricien $(a, b, n)$.\n",
    "\n",
    "\n",
    "**Question 2.** Écrire une fonction `triplet_vers_point(t, r)` qui transforme un triplet pythagoricien formé de `t=(p,q)` et `r`, en un point du cercle unité (donné comme un couple de rationnels).\n",
    "\n",
    "Pour s'assurer que les valeurs obtenues sont bien des rationnels, on effectuera une **conversion de type** des éléments de `t` vers la classe des entiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "982db734",
   "metadata": {},
   "outputs": [],
   "source": [
    "def triplet_vers_point(t, r):\n",
    "    return (Integer(t[0])/r, Integer(t[1])/r)\n",
    "    \n",
    "triplet_vers_point([3, 4], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a785baae",
   "metadata": {},
   "source": [
    "**Question 3.** Déduire de la question précédente une fonction `trouve_points_rationnels(r_max)`, qui prend entrée un entier naturel `r_max`, et qui retourne la liste de tous les points rationnels $(x, y)$ du cercle unité, dont un dénominateur commun est $r \\le r_{max}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85cdefef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve_points_rationnels(r_max):\n",
    "    liste = []\n",
    "    for r in range(1, r_max+1):\n",
    "        pyth = trouve_triplets(r)\n",
    "        ratio = [ triplet_vers_point(t, r) for t in pyth ]\n",
    "        liste += ratio\n",
    "    return liste\n",
    "    \n",
    "trouve_points_rationnels(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e6bbc51",
   "metadata": {},
   "source": [
    "On pourrait aussi écrire, de manière très compacte :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aaffce90",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve_points_rationnels(r_max):\n",
    "    return [ triplet_vers_point(t, r) for r in range(1, r_max+1) for t in trouve_triplets(r) ]\n",
    "    \n",
    "# trouve_points_rationnels(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "789b188b",
   "metadata": {},
   "source": [
    "**Question 4 (optionnelle).** Éliminer les éventuels doublons (éléments répétés plusieurs fois) de la liste précédente pour obtenir une liste d'éléments distincts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "524996f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Pour r = 10 :\", list(set(trouve_points_rationnels(10))))\n",
    "print(\"Pour r = 30 :\", list(set(trouve_points_rationnels(100))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58c15c7b",
   "metadata": {},
   "source": [
    "## Exercice 5. Transformations complexes\n",
    "\n",
    "\n",
    "**Question 1 :** Créer la liste `L` des nombres complexes $(1, i, -1, -i)$. Puis, exécutez l'instruction `polygon(L).show()`. Qu'observez-vous ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3bdf93b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [1, I, -1, -I]\n",
    "polygon(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba42e51d",
   "metadata": {},
   "source": [
    "**Question 2 :** En adaptant l'instruction de la question précédente, tracer un triangle équilatéral, un pentagone régulier, puis un polygone régulier à $27$ côtés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16afc100",
   "metadata": {},
   "outputs": [],
   "source": [
    "for c in [3, 5, 27]:\n",
    "    L = [e**(2*k*I*pi/c) for k in range(c) ]\n",
    "    polygon(L).show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be553021",
   "metadata": {},
   "source": [
    "**Question 3 :** Effectuer les instructions suivantes :\n",
    "1. Construire `T`, la liste de points correspondant à un triangle équilatéral de côté $1$, dont la base est horizontale, et dont le point \"en bas à gauche\" a pour coordonnées complexes $z = 1$.\n",
    "2. Construire `M`, la liste des points de `T` sur lesquels on a appliqué la transformation complexe $z \\mapsto -2z$. \n",
    "3. Exécuter les $2$ instructions suivantes :\n",
    "```\n",
    "figure1 = polygon(T, color=\"blue\") + polygon(M, color=\"red\")\n",
    "figure1.show()\n",
    "```\n",
    "Quelle transformation géométrique a-t-on opérée sur le triangle bleu ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d5ada22",
   "metadata": {},
   "outputs": [],
   "source": [
    "T = [1, 2, 1.5 + I*sqrt(3)/2]\n",
    "M = [-2*z for z in T]\n",
    "polygon(T, color=\"blue\") + polygon(M, color=\"red\") "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8256a810",
   "metadata": {},
   "source": [
    "**Question 4 (avancée) :** Appliquer successivement (11 fois) la transformation complexe $z \\mapsto e^{-i\\pi/6} z$ à tous les points de la liste `T` de la question 2, puis tracer la figure qui contient ces 11 transformations. Quelle transformation géométrique a-t-on opéré ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15ab6c4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "c = Color(0.3, 0.5, 0.7)                 # pour créer une couleur moins agressive\n",
    "PLOT = polygon(T, color=c)               # on stocke un premier triangle dans PLOT\n",
    "M = [ z for z in T ]\n",
    "for i in range(11):\n",
    "    c = c.lighter(0.1)                   # pour éclaircir la couleur c\n",
    "    M = [exp(-I*pi/6) * m for m in M]\n",
    "    PLOT += polygon(M, color=c)          # on stocke le nouveau triangle dans PLOT\n",
    "PLOT.show()                              # on affiche les 12 triangles de PLOT"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c46d6ec2",
   "metadata": {},
   "source": [
    "<!-- ## Exercice... Cribre d'Eratosthène.  -->\n",
    "\n",
    "<!-- **Question 1.** Écrire une fonction `est_premier(n)` qui prend en entrée un entier `n`, et qui retourne `True` si l'entier `n` est un nombre premier, et `False` sinon. Votre fonction **n'utilisera pas** la méthode `is_prime()` de Sagemath. -->\n",
    "\n",
    "\n",
    "<!-- **Question 2.**  -->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}