{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "18f1a7f8",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 5 -- avancé\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",
    "\n",
    "```{warning} \n",
    "Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d'exercices \"classiques\".\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 6. Entiers de Gauss\n",
    "\n",
    "Un **entier de Gauss** est un nombre complexe de la forme $a + ib$ avec $(a, b) \\in \\mathbb{Z}^2$. On peut vérifier que l'ensemble des entiers de Gauss forme un anneau (avec les opérations usuelles d'addition et de multiplication sur les complexes), que l'on note $\\mathbb{Z}[i]$.\n",
    "\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `est_entier_de_gauss(z)` qui prend en entrée un nombre complexe `z`, et qui teste si `z` est un entier de Gauss. La fonction retournera la valeur logique associée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "482cc6ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_entier_de_gauss(z):\n",
    "    x = z.real_part()\n",
    "    y = z.imag_part()\n",
    "    return (x in ZZ) and (y in ZZ)\n",
    "\n",
    "z1 = 1 + I\n",
    "z2 = e**(2*I*pi/3)\n",
    "z3 = 3/4 + 2*I\n",
    "print(est_entier_de_gauss(z1))\n",
    "print(est_entier_de_gauss(z2))\n",
    "print(est_entier_de_gauss(z3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f50fa570",
   "metadata": {},
   "source": [
    "Étant donné un nombre complexe $z \\in \\mathbb{C}$, on peut calculer son **arrondi dans les entiers de Gauss**, en arrondissant des parties réelles et imaginaires. Par exemple, $z = \\frac{1}{4} - \\frac{5}{3}i$ a pour arrondi $-2i$ dans les entiers de Gauss.\n",
    "\n",
    "\n",
    "**Question 2.** Écrire une fonction `arrondi_de_gauss(z)` qui prend en entrée un nombre complexe `z`, et qui retourne l'arrondi de `z` dans les entiers de Gauss."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60375ef1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def arrondi_de_gauss(z):\n",
    "    x = z.real_part()\n",
    "    y = z.imag_part()\n",
    "    return round(x) + I * round(y)\n",
    "    \n",
    "z1 = 1 + I\n",
    "z2 = 7/6 - (3/2)*I\n",
    "z3 = 3/4 + 2*I\n",
    "print(arrondi_de_gauss(z1))\n",
    "print(arrondi_de_gauss(z2))\n",
    "print(arrondi_de_gauss(z3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c1c8037",
   "metadata": {},
   "source": [
    "**Question 3.** Une fois votre fonction `arrondi_de_gauss` bien programmée (et testée), exécuter la fonction `affiche_arrondi()` écrite ci-dessous, puis observer le résultat. À quoi correspond géométriquement l'arrondi de Gauss ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74e2272a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def affiche_arrondi():\n",
    "    Z = [1 + I,  7/6 - (3/2)*I, 3/4 + 2*I, -I-12/5]\n",
    "    arrZ = [ arrondi_de_gauss(z) for z in Z ]\n",
    "    P = list_plot(Z, color=\"blue\", marker='o', size=35) + list_plot(arrZ, color=\"red\", marker='*', size=40)\n",
    "    P.show(gridlines=True, xmin=-3, xmax=3, ymin=-3, ymax=3)\n",
    "\n",
    "affiche_arrondi()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65baa2bb",
   "metadata": {},
   "source": [
    "L'arrondi de Gauss d'un complexe $z \\in \\mathbb{C}$ correspond à l'entier de Gauss le plus proche (en norme) de $z$, autrement dit le point de la grille le plus proche de $z$.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "On peut démontrer que l'anneau des entiers de Gauss est **euclidien**, autrement dit, qu'il admet une **division euclidienne**. Cette division (avec reste) est définie de la sorte : si $a$ et $b$ sont deux entiers de Gauss, alors le **quotient** $q$ de la division euclidienne de $a$ par $b$ est l'arrondi du complexe $a/b$. Le **reste** de la division est alors $r = a - bq$.\n",
    "\n",
    "\n",
    "Par exemple, le quotient et le reste de la division euclidienne de $a = 8 - 3i$ par $b = 3 + 2i$ sont $q = 1-2i$ et $r = 1+i$, car $\\frac{a}{b} =  \\frac{18}{13} -\\frac{25}{13}i$.\n",
    "\n",
    "**Question 5.** Écrire une fonction `quotient_gauss(a, b)` qui prend en entrée deux nombres complexes `a` et `b`, et qui retourne le quotient de la division euclidienne (dans $\\mathbb{Z}[i]$) de  `a` par `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8223086b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def quotient_gauss(a, b):\n",
    "    if b == 0:\n",
    "        print(\"Erreur : b est nul\")\n",
    "        return None\n",
    "    z = a/b\n",
    "    return arrondi_de_gauss(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1716e9b8",
   "metadata": {},
   "source": [
    "**Question 6.** Écrire une fonction `reste_gauss(a, b)` qui prend en entrée deux nombres complexes `a` et `b`, et qui retourne le reste de la division euclidienne (dans $\\mathbb{Z}[i]$) de  `a` par `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6741848b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reste_gauss(a, b):\n",
    "    q = quotient_gauss(a, b)\n",
    "    return a - b*q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6eeae241",
   "metadata": {},
   "source": [
    "**Question 7.** Testez vos fonctions `quotient_gauss(a, b)`et `reste_gauss(a, b)` avec les paires d'entiers de Gauss suivantes :\n",
    "- $(a, b) = (5 + 2i, 3-4i)$, pour laquelle vous devriez obtienir un quotient $q = i$ et un reste $r = 1-i$ ;\n",
    "- $(a, b) = (5, 2+i)$, pour laquelle vous devriez obtienir un quotient $q = 2-i$ et un reste $r = 0$.\n",
    "\n",
    "*Remarque : suivant ce que vous avez écrit pour les fonctions précédentes, vous pourriez avoir besoin de faire une **coercion** de l'entier $5$ vers les complexes.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c441474d",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 5 + 2*I     # pour écrire a comme un entier\n",
    "b = 3 - 4*I\n",
    "print(\"a =\", a, \"   b =\", b)\n",
    "print(\"q =\", quotient_gauss(a, b))\n",
    "print(\"r =\", reste_gauss(a, b))\n",
    "\n",
    "a = 5 + 0*I       # une manière de faire la coercion dans les complexes\n",
    "b = 2 + I      \n",
    "print(\"\\na =\", a, \"   b =\", b)\n",
    "print(\"q =\", quotient_gauss(a, b))\n",
    "print(\"r =\", reste_gauss(a, b))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75a65817",
   "metadata": {},
   "source": [
    "Enfin, le **pgcd** de deux entiers de Gauss se calcule par l'algorithme d'Euclide, comme pour des entiers de $\\mathbb{Z}$. La seule différence est une étape de **normalisation** pour obtenir un pgcd dans le quadrant supérieur droit du plan complexe (c'est-à-dire, on veut que le pgcd ait une partie réelle strictement positive et une partie imaginaire positive). \n",
    "\n",
    "L'algorithme est donc le suivant :\n",
    "\n",
    "- **Tant que** $b \\ne 0$:\n",
    "  - Calculer $q$ et $r$ le quotient et le reste de la division euclidienne de $a$ par $b$\n",
    "  - Remplacer $a$ par $b$ et $b$ par $r$\n",
    "- Multiplier $a$ par $1$, $-1$, $i$ ou $-i$, afin que ${\\rm Re}(a) \\ge 1$ et ${\\rm Im}(a) \\ge 0$\n",
    "- **Retourner** $a$\n",
    "\n",
    "\n",
    "**Question 8.** Écrire une fonction `pgcd_gauss(a, b)` qui prend en entrée deux nombres complexes `a` et `b`, et qui retourne le pgcd (dans $\\mathbb{Z}[i]$) de  `a` et `b`.\n",
    "\n",
    "*Exemple (pour tester) : ${\\rm pgcd}(3+i, 3-i) = 1+i$ et ${\\rm pgcd}(47+29i,-11+23i) = 7i+1$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40252820",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd_gauss(a, b):\n",
    "    while b != 0:\n",
    "        q = quotient_gauss(a, b)\n",
    "        r = reste_gauss(a, b)\n",
    "        a = b\n",
    "        b = r\n",
    "    if a.real_part() < 0 and a.imag_part() < 0:\n",
    "        return -a\n",
    "    if a.imag_part() < 0:\n",
    "        return I*a\n",
    "    if a.real_part() <= 0:\n",
    "        return -I*a\n",
    "    return a\n",
    "    \n",
    "print(pgcd_gauss(3+I,3-I))\n",
    "print(pgcd_gauss(47+29*I,-11+23*I))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02261515",
   "metadata": {},
   "source": [
    "## Exercice 7. Crible d'Eratosthène\n",
    "\n",
    "Le **crible d'Ératosthène** permet d'obtenir la liste des nombres premiers entre $0$ et $N-1$, pour un certain entier $N \\ge 1$. L'idée du crible est la suivante :\n",
    "- On initialise une liste `T` de longueur `N`, qui ne contient que des valeurs booléennes égales à `True`. La liste `T` a pour vocation de savoir quels sont les nombres premiers. Le but est qu'à la fin de l'algorithme, `T[i]` vaut `True` si `i` est un nombre premier.\n",
    "- On affecte à `T[0]` et `T[1]` la valeur `False` (ce ne sont pas des nombres premiers).\n",
    "- Ensuite, on parcourt la liste de l'indice $i = 2$ à $N-1$. **Pour chaque valeur de $i$**, si `T[i]` est vrai, alors on modifie `T[j]` en `False` **pour tous les $j > i$** tels que $i$ divise $j$. La raison est la suivante : comme $i$ divise strictement $j$, l'entier $j$ ne peut pas être premier.\n",
    "- On retourne la liste des indices $i$ tels que `T[i]` vaut `True`.\n",
    "\n",
    "Pour plus de détails sur le fonctionnement du crible, voir par exemple la page wikipedia :\n",
    "\n",
    "https://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne\n",
    "\n",
    "\n",
    "Dans cet exercice, **on n'utilisera donc pas** la méthode `is_prime()`, acr le but est d'implanter par soi-même une fonction qui liste des nombres premiers.\n",
    "\n",
    "\n",
    "\n",
    "**Question 1 :** Écrire une fonction `initialiser_tableau(N)` qui retourne une liste de longueur $N$ ne comportant que la valeur `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae544657",
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialiser_tableau(N):\n",
    "    return [ True for i in range(N) ]\n",
    "\n",
    "print(initialiser_tableau(12))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ea1d272",
   "metadata": {},
   "source": [
    "**Question 2 :** Écrire une fonction `eliminer_diviseurs(T, p, N)` qui prend en entrée une liste de booléens `T`, un entier $p \\ge 2$ et la taille $N$ de la liste, et qui **modifie** la liste `T` en affectant `False` à `T[j]` pour tous les indices $j$ divisibles par $p$ et strictement supérieurs à $p$. Pour faire cela, on pourra parcourir les indices de la liste par pas de $p$.\n",
    "\n",
    "**Attention :** Votre fonction ne devra **ni créer** de nouvelle liste, **ni retourner** de liste. Elle **modifiera** la liste `T` passée en paramètre.\n",
    "\n",
    "Par exemple, si on donne en entrée de la fonction `eliminer_diviseurs` une liste `T` égale à\n",
    "```\n",
    "[False, False, True, True, False, True, False, True, False, True, False, True, False, True, False, True]\n",
    "``` \n",
    "ainsi qu'une taille `N = 16` et l'entier `p = 3`, alors,  en sortie de la fonction, la liste `T` devient :\n",
    "```\n",
    "T = [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False]\n",
    "```\n",
    "(les valeurs d'indice $6$, $9$, $12$ et $15$ sont égales à `False`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58518b08",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eliminer_diviseurs(T, p, N):\n",
    "    i = 2*p\n",
    "    while i < N:\n",
    "        T[i] = False\n",
    "        i += p\n",
    "\n",
    "N, p = 12, 2\n",
    "T = initialiser_tableau(N)\n",
    "eliminer_diviseurs(T, p, N)\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfa2c37a",
   "metadata": {},
   "source": [
    "**Question 3 :** À l'aide des questions précédentes, implanter le crible d'Eratosthène présenté en début d'exercice, sous la forme d'une fonction `eratosthene(N)` qui retourne la liste des nombres premiers compris entre $2$ et $N$. \n",
    "\n",
    "On vérifiera que pour `eratosthene(100)`, on obtient la liste :\n",
    "```\n",
    "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f62fce3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eratosthene(N):\n",
    "    T = initialiser_tableau(N)\n",
    "    T[0] = False\n",
    "    T[1] = False\n",
    "    p = 2\n",
    "    while p < N:\n",
    "        if T[p]:\n",
    "            eliminer_diviseurs(T, p, N)\n",
    "        p += 1\n",
    "    return [x for x in range(N) if T[x] ]\n",
    "    \n",
    "print(eratosthene(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f875eb9e",
   "metadata": {},
   "source": [
    "On dit que $p$ est un nombre premier de Sophie Germain si $p$ et $2p+1$ sont des nombres premiers.\n",
    "\n",
    "**Question 4 :** Écrire une fonction `premiers_sophie_germain(N)` qui retourne la liste des nombres premiers de Sophie Germain inférieurs ou égaux à `N`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b9df6ea2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def premiers_sophie_germain(N):\n",
    "    T = eratosthene(2*N+1)\n",
    "    return [x for x in T if 2*x+1 in T]\n",
    "\n",
    "print(premiers_sophie_germain(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "179d4eb5",
   "metadata": {},
   "source": [
    "On dit que $p$ et $q$ sont deux nombres premiers jumeaux si $p$ et $q$ sont premiers et si $|p - q| = 2$.\n",
    "\n",
    "**Question 5 :** Écrire une fonction `premiers_jumeaux(N)` qui retourne la liste des nombres premiers jumeaux inférieurs ou égaux à `N`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19184fd6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def premiers_jumeaux(N):\n",
    "    T = eratosthene(N+2)\n",
    "    return [x for x in T if x <= N and (x+2 in T or x-2 in T)]\n",
    "\n",
    "print(premiers_jumeaux(102))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}