NombrePrimer10001.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aKw0NywJXwU3"
   },
   "source": [
    "# <span class=\"tema\">(Numèrics)</span> El nombre primer que ocupa la posició 10001"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NA0OTp6sXwU3"
   },
   "source": [
    "<p style=\"font-family:Arial;font-size:1em\">\n",
    "Si llistem els primers 6 nombres primers: 2, 3, 5, 7, 11, i 13, podem veure que el 6è primer és el 13. Quin és el primer que ocupa la posició 10001?\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Ni44Ihx3XwU4"
   },
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "1. Quin algorisme hem d'aplicar? Revisa els algorismes vistos a teoria\n",
    "1. Explica els passos que fa l'algorisme en el cas primer(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explicació de l'algortime emprat\n",
    "\n",
    "#### `nth_prime_upper_bound(n)`\n",
    "Retorna una fita superior del $n$-èssim número primer. [Referència](https://stackoverflow.com/questions/1042717/is-there-a-way-to-find-the-approximate-value-of-the-nth-prime#25440642).\n",
    "\n",
    "#### `sieve(n)`\n",
    "Computa una fita superior del $n$-èssim primer utilitzant `upper_n = nth_prime_upper_bound(n)`.\n",
    "Després utilitza l'algoritme sieve of Eratosthenes per retornar un generator amb tots els primers menors a `upper_bound`.\n",
    "\n",
    "#### `primer(n)`\n",
    "Donada un generator generat per `sieve(n)`, retorna l'element en la $n-1$ posició d'aquest. S'utilitza la funció `next` per a iterar sobre un generator.\n",
    "\n",
    "### Memoització\n",
    "\n",
    "#### `nth_prime_upper_bound(n)` \n",
    "Es cacheja els resultats en forma de diccionari normal.\n",
    "\n",
    "#### `sieve(n)`\n",
    "Es realitza un cache especial per a generators. D'aquesta manera, si tenim guardat un generator per a calcular el primer $n$-èssim, i ens demanen el primer $m$-èssim (tal que $m < n$), llavors s'agafa el generator en cache. \n",
    "\n",
    "Per a poder realitzar aquest tipus de cache, s'utilitza la funció `itertools.tee`.\n",
    "\n",
    "### Cas `primer(6)`\n",
    "\n",
    "El procés d'execució és el següent:\n",
    "\n",
    "1. Es crida a `nth_prime_upper_bound(6)` que retorna el valor per defecte `primes_small[6] = 13`.\n",
    "2. Es computa l'alagoritme de sieve of Eratosthenes per a `upper_n = 13`, i es retorna un generator `g` amb tots els primers més petits o iguals a `upper_n`.\n",
    "3. S'executa la comanda de return en `primer(6)`, iterant sobre el generator `g` i retornant el valor en la posició `6 - 1 = 5`, que és `13`.\n",
    "\n",
    "En aquest cas, donat que el nombre demanat (`6`) és prou petit no es pot assegurar l'eficiència. Per a valors més grans, com per exemple `10001`, es poden apreciar millor les optimitzacions.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Rr581aV1XwU4"
   },
   "source": [
    "### Implementació"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time\n",
    "from math import sqrt, log, ceil\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memo_bound(f):\n",
    "    memo = {}\n",
    "    def helper(x):\n",
    "        if x not in memo:\n",
    "            memo[x] = f(x)\n",
    "        return memo[x]\n",
    "    return helper\n",
    "\n",
    "@memo_bound\n",
    "def nth_prime_upper_bound(n):\n",
    "    primes_small = [0, 2, 3, 5, 7, 11, 13, 17, 19,\\\n",
    "                    23, 29, 31, 37, 41, 43, 47, 53,\\\n",
    "                    59, 61, 67, 71, 73, 79, 83, 89, 97]\n",
    "    \n",
    "    fn = n\n",
    "    if n < len(primes_small):\n",
    "        return primes_small[n]\n",
    "    \n",
    "    flogn  = log(n)\n",
    "    flog2n = log(flogn)\n",
    "\n",
    "    if n >= 688383:         # Dusart 2010 page 2\n",
    "        upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn))\n",
    "\n",
    "    elif n >= 178974:       # Dusart 2010 page 7\n",
    "        upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));\n",
    "\n",
    "    elif n >=  39017:       # Dusart 1999 page 14\n",
    "        upper = fn * (flogn + flog2n - 0.9484);\n",
    "\n",
    "    else:                   # Modified from Robin 1983 for 6-39016\n",
    "        upper = fn * (flogn  +  0.6000 * flog2n);\n",
    "\n",
    "    if upper >= 18446744073709551615:\n",
    "        if n <= 425656284035217743:\n",
    "            return 18446744073709551557\n",
    "    \n",
    "        exit(1)\n",
    "\n",
    "    return ceil(upper)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import tee\n",
    "from types import GeneratorType\n",
    "\n",
    "Tee = tee([], 1)[0].__class__\n",
    "\n",
    "def memo_sieve(f):\n",
    "    memo = {}\n",
    "    \n",
    "    def helper(x):\n",
    "        if x not in memo:\n",
    "            memo[x] = f(x)\n",
    "        \n",
    "        if isinstance(memo[x], (GeneratorType, Tee)):\n",
    "            memo[x], r = tee(memo[x])\n",
    "            return r\n",
    "    \n",
    "        return memo[x]\n",
    "    \n",
    "    return helper\n",
    "\n",
    "@memo_sieve\n",
    "def sieve(n):\n",
    "    upper_n = nth_prime_upper_bound(n)\n",
    "    \n",
    "    sieve = [True for _ in range(2, upper_n + 1)]\n",
    "\n",
    "    for j in range(2, ceil(sqrt(upper_n))):\n",
    "        i = j-2\n",
    "        \n",
    "        if sieve[i]:\n",
    "            for k in range(j * j, upper_n + 1, j):\n",
    "                sieve[k-2] = False\n",
    "\n",
    "    return (j for j in range(2, upper_n+1) if sieve[j-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "aKBT0ODXXwU6"
   },
   "outputs": [],
   "source": [
    "def primer(n):\n",
    "    return next((x for i, x in enumerate(sieve(n)) if i == n-1), None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_primer(n):\n",
    "    return f\"El {n}-èssim primer és {primer(n)}.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'El 6-èssim primer és 13.'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pretty_primer(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed time for 10000 computations: 73.3156 s.\n",
      "Mean: 0.00733156 s.\n",
      "Min:  2.86102e-06 s.\n",
      "Max:  1.87212 s.\n"
     ]
    }
   ],
   "source": [
    "N_TESTS = 10**4\n",
    "MIN, MAX = 10**0, 10**4\n",
    "\n",
    "t_total = 0\n",
    "t_max, t_min = 0, 18446744073709551615\n",
    "\n",
    "for _ in range(N_TESTS):\n",
    "    n = randint(MIN, MAX)\n",
    "    \n",
    "    t = time()\n",
    "    p = primer(n)  \n",
    "    t = time() - t\n",
    "    \n",
    "    t_max = t if t > t_max else t_max\n",
    "    t_min = t if t < t_min else t_min\n",
    "    t_total += t\n",
    "\n",
    "print(f\"Elapsed time for {N_TESTS} computations: {t_total:4.6} s.\")\n",
    "print(f\"Mean: {t_total/N_TESTS:2.6} s.\")\n",
    "print(f\"Min:  {t_min:2.6} s.\")\n",
    "print(f\"Max:  {t_max:2.6} s.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vJCmdiKdXwU8"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta eficient | **8** punts\n",
    "Ús correcte algorismes teoria | **+1** punt\n",
    "Solució correcta ineficient | **3** punts \n",
    "Codi comentat i seguint estàndar PEP8 | **+1** punt \n",
    "S'ofereix una funció adicional per mostrar la solució elegantment| **+0.5** punts \n",
    "L'algorisme falla repetidament | **-7** punts \n",
    "L'algorisme falla en algun cas excepcional | **-2** punt\n",
    "No es donen prous exemples d'execució | **-1** punt\n",
    "Codi, noms de variables, solució o comentaris no prou clars | **-1** punt\n",
    "La funció o els paràmetres no s'anomenen com a l'exemple | **-1** punt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "NombrePrimer10001.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}