Numero3Condicions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_Q-lxCmW-2ln"
   },
   "source": [
    "# <span class=\"tema\">(Numèrics)</span> Nombre n que compleix tres condicions "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kPFXDF8u-2lo"
   },
   "source": [
    "Fes una funció que trobi el nombre $n$  més gran tal que compleixi les següents tres condicions:  \n",
    "- $n<10000$, \n",
    "- $n=m*m$ per algun $m$ \n",
    "- $n=k!+1$ per algun $k$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wfFjNd4X-2lp"
   },
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "1. Planteja l'algorisme per cadascuna de les solucions per separat de forma eficient. Revisa el significat de factorial si cal.\n",
    "2. Mira si pots ajuntar-les de manera eficient, per tal que una condició ajudi a reduir el cost d'alguna altra."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2Rnx5zod-2lq"
   },
   "source": [
    "### Implementació"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Observacions\n",
    "1. La condició obvia de que $n < 10^4$.\n",
    "2. Que $n = m^2$ significa que $\\sqrt{n} \\in \\mathbb{N}$.\n",
    "3. Donat que $8! = 40320 > n = 10000$, sabem que $0 < k < 8$.\n",
    "\n",
    "#### Algoritme\n",
    "A partir de les observacions aquestes, seguirem el següent procediment:\n",
    "1. Definim `factorial = 2` i iterarem sobre `while factorial < n`, on `n = 10**4` per defecte.\n",
    "2. Comporvarem si `x = math.sqrt(k+1)`, utilitzant aritmètica modular, és enter: `x % 1 == 0.0`.\n",
    "3. La comprovació de 1 no fa falta, ja que queda reduïda per el primer pas de l'algoritme.\n",
    "\n",
    "#### Complexitat\n",
    "La complexitat d'aquest algoritme és de $O(n) = O(10^4) = 7\\cdot 5 = 35$ operacions en el cas de $n = 10^4$.\n",
    "\n",
    "Per a $n$ arbitrari, definim $N$ com el màxim natural tal que $N!+1 < n$. Llavors la complexitat serà $O(n) = 5N$. Donat que el factorial escala a l'ordre de $O(n!)$, aquest algoritme és extremadament eficient.\n",
    "\n",
    "#### Nota\n",
    "Donada la implementació actual, no fa falta l'ús de funcions addicionals. Tampoc s'ha usat cap list comprehension, degut que no fa falta en cap moment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7diTFjey-2lr"
   },
   "outputs": [],
   "source": [
    "# El resultat ha de ser 5041\n",
    "import math\n",
    "\n",
    "def numero3condicions(n=10**4):\n",
    "    target, factorial, i = 0, 2, 3\n",
    "    \n",
    "    while factorial < n:\n",
    "        _tmp = factorial + 1\n",
    "        \n",
    "        # Check if _tmp is an integer\n",
    "        # and swap the target if it is\n",
    "        if math.sqrt(_tmp) % 1 == 0.0:\n",
    "            target = _tmp\n",
    "            \n",
    "        # Compute next factorial\n",
    "        factorial *= i\n",
    "        i += 1\n",
    "            \n",
    "    return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_numero3condicions():\n",
    "    return f\"The number that staisfies the three confitions is {numero3condicions()}.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number that staisfies the three confitions is 5041.\n"
     ]
    }
   ],
   "source": [
    "pretty = pretty_numero3condicions()\n",
    "print(pretty)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "AaLiU-Xv-2lu"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta eficient | **8** punts\n",
    "Inclusio d'una list comprehension | **+1** punt\n",
    "Solució correcta de complexitat > O(n) | **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"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "Numero3Condicions.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
}