{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Aula de 30/03 - Um pouco mais de recursão\n",
    "\n",
    "Nessa aula veremos alguns problemas, que vão usar técnicas distintas, mas\n",
    "ainda usando formas simples de recursão\n",
    "\n",
    "Uma das coisas que podemos fazer com números inteiros é separar os seus\n",
    "dígitos um a um. Observe o cógido abaixo:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "imprimedigito (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function imprimedigito(n)\n",
    "    if n <= 9\n",
    "        println(n)\n",
    "        println(\"fim\")\n",
    "    else\n",
    "        println(n % 10)\n",
    "        imprimedigito(n ÷ 10)\n",
    "    end\n",
    "end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "fim\n"
     ]
    }
   ],
   "source": [
    "imprimedigito(123456789)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A função, imprime os dígitos do número de entrada do menos significativo ao mais significativo. Para isso, combina duas operação, o resto por 10, e a divisão por 10.\n",
    "\n",
    "É possível fazer algumas operações úteis com essa técnica, como por exemplo, somar os dígitos de um número. Se um número é divisível por três a soma dos seus dígitos também é divisível por três.\n",
    "\n",
    "Mas, para começar, vamos fazer o teste para uma função __somadigitos(n)__\n",
    "Quais seria casos interessantes a verificar?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "testesd (generic function with 1 method)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function testesd()\n",
    "    if somadigitos(123) != 6\n",
    "        println(\"Não funciona para 123\")\n",
    "    end\n",
    "    if somadigitos(111111111) != 9\n",
    "        println(\"Não funciona para números grandes\")\n",
    "    end\n",
    "    if somadigitos(8) != 8\n",
    "        println(\"Não funciona para 8\")\n",
    "    end\n",
    "    if somadigitos(0) != 0\n",
    "        println(\"Não funciona para zero\")\n",
    "    end\n",
    "    if somadigitos(-128) != -11\n",
    "        println(\"Não funciona para negativos\")\n",
    "    end    \n",
    "    println(\"Fim dos testes\")\n",
    "end\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora sim, vamos pensar em como fazer para somar os dígito de um número, a cada etapa, temos que descascar uma parte (% 10), para em seguida tirar essa parte (div 10)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "somadigitos (generic function with 1 method)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function somadigitos(n)\n",
    "    if -10 < n < 10\n",
    "        return n\n",
    "    else\n",
    "        return n % 10 + somadigitos(n ÷ 10)\n",
    "    end\n",
    "end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fim dos testes\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# aqui é o local para brincar com a função :) por exemplo chamando a função recursivamente\n",
    "testesd()\n",
    "somadigitos(somadigitos(63187268768))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos também verificar se a valem algumas propriedades, como por exemplo, sera que dados um número divisível por 3 a soma dos seus dígitos é divisível por 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 1363286823\n",
    "somadigitos(a) \n",
    "a % 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quem sabe usar números aleatórios __rand(Int)__ pode ajudar nessa verificação"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Acabou\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.046204508"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function testa(n)\n",
    "    if n <= 0\n",
    "        println(\"Acabou\")\n",
    "    else\n",
    "      a = rand(Int)\n",
    "      if a % 3 != somadigitos(a) % 3\n",
    "        println(\"Achei um erro para: \", a)\n",
    "      end\n",
    "      testa(n - 1)\n",
    "    end\n",
    "end    \n",
    "@elapsed testa(1000)    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma outra propriedade interessante que pode ser verificado usando o operador de resto da divisão é a primalidade.\n",
    "Isso é ver se um número $n$ é divisível apenas por ele mesmo e por 1.\n",
    "\n",
    "Mas, como sempre, vamos começar com os estes, assumindo que teremos a função __éprimo(x)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "testeéprimo (generic function with 1 method)"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function testeéprimo()\n",
    "    if !éprimo2(2)\n",
    "        println(\"Falhou para 2\")\n",
    "    end\n",
    "    if éprimo2(57)\n",
    "        println(\"falhou para 57\")\n",
    "    end\n",
    "    if !éprimo2(13)\n",
    "        println(\"falhou para 13\")\n",
    "    end\n",
    "    if !éprimo2(1013)\n",
    "        println(\"falhou para 1013\")\n",
    "    end\n",
    "    if éprimo2(1000000)\n",
    "        println(\"falhou para 1000000\")\n",
    "    end\n",
    "    println(\"Final dos testes\")\n",
    "end   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora sim, vamos pensar em como fazer a função, a forma simples e direta é tentar dividir o número candidato, por número de 2 até n / 2, se algum dividir, temos que o número não é primo. Caso contrário ele é primo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "éprimo (generic function with 1 method)"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function divide(a, n)\n",
    "    if a > n / 2\n",
    "        return false\n",
    "    else\n",
    "        if n % a == 0\n",
    "            return true\n",
    "        else\n",
    "            return divide(a + 1, n)\n",
    "        end\n",
    "    end\n",
    "end\n",
    " \n",
    "function éprimo(n)\n",
    "    if divide(2, n)\n",
    "        return false\n",
    "    else\n",
    "        return true\n",
    "    end\n",
    "end\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora que já temos a nossa primeira função, podemos pensar em como otimizar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "éprimo2 (generic function with 1 method)"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function divide2(a, n)\n",
    "    if a > sqrt(n)\n",
    "        return false\n",
    "    else\n",
    "        if n % a == 0\n",
    "            return true\n",
    "        else\n",
    "            return divide2(a + 2, n)\n",
    "        end\n",
    "    end\n",
    "end\n",
    " \n",
    "function éprimo2(n)\n",
    "    if n == 2\n",
    "        return true\n",
    "    elseif   n % 2 == 0\n",
    "        return false\n",
    "    else    \n",
    "        return  !divide2(3, n)\n",
    "    end    \n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para terminar, vamos imprimir os 100 primeiros primos?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n",
      "23\n",
      "29\n",
      "31\n",
      "37\n",
      "41\n",
      "43\n",
      "47\n",
      "53\n",
      "59\n",
      "61\n",
      "67\n",
      "71\n",
      "73\n",
      "79\n",
      "83\n",
      "89\n",
      "97\n",
      "101\n",
      "103\n",
      "107\n",
      "109\n",
      "113\n",
      "127\n",
      "131\n",
      "137\n",
      "139\n",
      "149\n",
      "151\n",
      "157\n",
      "163\n",
      "167\n",
      "173\n",
      "179\n",
      "181\n",
      "191\n",
      "193\n",
      "197\n",
      "199\n",
      "211\n",
      "223\n",
      "227\n",
      "229\n",
      "233\n",
      "239\n",
      "241\n",
      "251\n",
      "257\n",
      "263\n",
      "269\n",
      "271\n",
      "277\n",
      "281\n",
      "283\n",
      "293\n",
      "307\n",
      "311\n",
      "313\n",
      "317\n",
      "331\n",
      "337\n",
      "347\n",
      "349\n",
      "353\n",
      "359\n",
      "367\n",
      "373\n",
      "379\n",
      "383\n",
      "389\n",
      "397\n",
      "401\n",
      "409\n",
      "419\n",
      "421\n",
      "431\n",
      "433\n",
      "439\n",
      "443\n",
      "449\n",
      "457\n",
      "461\n",
      "463\n",
      "467\n",
      "479\n",
      "487\n",
      "491\n",
      "499\n",
      "503\n",
      "509\n",
      "521\n",
      "523\n"
     ]
    }
   ],
   "source": [
    "function first100(i, n)\n",
    "    if i < 100\n",
    "        if éprimo2(n) \n",
    "            println(n)\n",
    "            first100(i + 1, n + 1)\n",
    "        else\n",
    "            first100(i, n + 1)\n",
    "        end\n",
    "    end\n",
    "end\n",
    "\n",
    "first100(1, 2)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se der tempo, vamos imprimir uns primos de Mersenne. Um primo é de Mersenne se ele é da forma $2^n -1$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.1.1",
   "language": "julia",
   "name": "julia-1.1"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.1.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}