{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f3c73b16",
   "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": "37d6fa64",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5eb69dc0",
   "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": "40a2be6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3272052c",
   "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": "9f2605c2",
   "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": "d1199fc8",
   "metadata": {},
   "source": [
    "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": "57db6da6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a26339f",
   "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": "b43bf03e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e1757d9",
   "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": "31caac0a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97401ccb",
   "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": "229786cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90c9c923",
   "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": "fbd1c543",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2075a4ba",
   "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": "f635775e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6dc0005",
   "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": "29502e13",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f24561f0",
   "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": "19d42f3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7c1d61a",
   "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": "55c2fceb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}