2125-Qiang-Ye-devoir 3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <center>Devoir3 IFT2125-A-H19</center>\n",
    "\n",
    "**Student**: Qiang Ye (20139927) \n",
    "\n",
    "**Date**: 24 Jan 2019\n",
    "\n",
    "mailto: samuel.ducharme@umontreal.ca\n",
    "<hr>\n",
    "\n",
    "**Question 1**\n",
    "\n",
    "Provez que $f \\in \\Theta(g)$ si, et seulement si  $g\\in\\Theta(f)$, si, et seulement si $\\Theta (f) = \\Theta (g)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**Answer 1**\n",
    "1. Recall the justification of $f \\in O(g) \\Leftrightarrow g \\in \\Omega(f)$:\n",
    "\\begin{align}\n",
    "f\\in O(g) &\\Leftrightarrow \\exists n_0 \\ge 1, c_0 \\ge 0, \\forall n > n_0, f(n) \\le c_0 g(n) \\\\\n",
    "&\\Leftrightarrow \\exists n_0 \\ge 1, c_0 \\ge 0, \\forall n > n_0, g(n) \\ge \\frac{1}{c_0} f(n)\\\\ \n",
    "&\\Leftrightarrow \\exists n_0 \\ge 1, c_1 = \\frac{1}{c_0} \\ge 0, \\forall n > n_0,  g(n) \\ge c_1 f(n)\\\\\n",
    "&\\Leftrightarrow g\\in \\Omega(f)\\\\\n",
    "\\end{align}\n",
    "\n",
    "Recall the justification of $f \\in \\Theta(f)$:\n",
    "\n",
    "$\\exists n_0 = 1, c_0 = 1, c_0' = 1, \\forall n \\ge n_0, c_0 f(n) \\le f(n) \\le c_0' f(n)$.\n",
    "Obviously, it is true that: $$f \\in \\Theta(f) \\tag{1.0}$$.\n",
    "\n",
    "**Part1**. Prove that $g\\in \\Theta(f) \\Leftrightarrow f\\in \\Theta(g)$.\n",
    "\n",
    "\\begin{align}\n",
    "g\\in \\Theta(f) &\\Leftrightarrow g\\in O(f) \\land g\\in \\Omega(f)\\\\ \n",
    "&\\Leftrightarrow f\\in \\Omega(g) \\land f\\in O(g)\\\\\n",
    "&\\Leftrightarrow f\\in \\Theta(g)\\\\\n",
    "\\end{align}\n",
    "\n",
    "**Part2**. Prove that $g\\in \\Theta(f) \\Leftrightarrow \\Theta(f) = \\Theta(g)$.\n",
    "\n",
    "First, we have:\n",
    "\\begin{align}\n",
    "\\Theta(f) = \\Theta(g) &\\Leftrightarrow (\\forall h \\in \\Theta(f) \\Rightarrow h \\in \\Theta(g)) \\land (\\forall h\\in \\Theta(g)\\Rightarrow h\\in \\Theta(f))\\\\\n",
    "\\end{align}\n",
    "and\n",
    "\\begin{align}\n",
    "f\\in \\Theta(g) &\\Leftrightarrow f \\in O(g) \\land f \\in \\Omega(g)\\\\\n",
    "&\\Leftrightarrow \\exists n_0 \\ge 1, c_0 \\ge 0, c_0' \\ge 0, \\forall n\\ge n_0, c_0, c_0',\\  c_0 g(n) \\le f(n) \\le c_0' g(n) \\\\\n",
    "&\\Leftrightarrow \\exists n_0 \\ge 1, c_0 \\ge 0, c_0' \\ge 0, \\forall n\\ge n_0, c_0, c_0',\\  g(n) \\le \\frac{1}{c_0} f(n) \\land \\frac{1}{c_0'} f(n) \\le g(n) \\tag{1.1}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Suppose any function $h:\\mathbb N \\to \\mathbb R^{\\ge0} \\in \\Theta(g)$:\n",
    "\n",
    "\\begin{align}\n",
    "h\\in \\Theta(g) &\\Leftrightarrow h \\in O(g) \\land h \\in \\Omega(g)\\\\\n",
    "&\\Leftrightarrow \\exists n_1 \\ge 1, c_1 \\ge 0, c_1' \\ge 0, \\forall n\\ge n_1, c_1 g(n) \\le h(n) \\le c_1' g(n) \\tag{1.2}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Based on formular (1.1),(1.2), we have:\n",
    "\n",
    "$\\exists n_2 = \\max\\{n_0, n_1\\} \\ge 1, c_0 \\ge 0, c_0' \\ge0, c_1\\ge 0, \\text{ and } c_1' \\ge0$,\n",
    "\n",
    "$\\forall n\\ge n_2, \\frac{c_1}{c_0'} f(n) \\le h(n) \\le \\frac{c_1'}{c_0} f(n)$.\n",
    "\n",
    "That is, $$h \\in \\Theta(g) \\Rightarrow h \\in \\Theta(f) \\tag{1.3}$$\n",
    "\n",
    "Similarly, we also have: \n",
    "$$ h \\in \\Theta(f) \\Rightarrow h \\in \\Theta(g) \\tag{1.4}$$\n",
    "\n",
    "\n",
    "Based on (1.1),(1.3),(1.4), we have, $$ f\\in \\Theta(g) \\Rightarrow \\Theta(f) = \\Theta(g) \\tag{1.5}$$\n",
    "<br>\n",
    "\n",
    "Based on (1.0), we have:\n",
    "\\begin{align}\n",
    "\\Theta(f) = \\Theta(g) &\\Rightarrow f\\in \\Theta(f) \\\\\n",
    "&\\Rightarrow f\\in \\Theta(g) \\tag{1.6}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Finally, based on (1.5) and (1.6), we proved:\n",
    "\\begin{align}\n",
    "f \\in \\Theta(g) &\\Leftrightarrow \\Theta(f) = \\Theta(g)\\\\\n",
    "\\end{align}\n",
    "\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question2**\n",
    "\n",
    "Donnez un exemple de fonctions $f, g$ telles que $f \\in \\Theta(g)$ et $\\lim_{n\\to \\infty} \\frac{f(n)}{g(n)}$ n'existe pas. Prouvez vos dires. Les meilleurs reponses ont $g(n) > 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer2**\n",
    "\n",
    "Let, $f(n) = 2n + n \\sin(n), \\text{ and } g(n) = n$, where $f, g: \\mathbb N \\to \\mathbb R^{\\ge 0}, f \\in \\Theta(g)$, but $\\lim_{n\\to \\infty} \\frac{f(n)}{g(n)}$ doesn't exist. Here is the proof.\n",
    "\n",
    "\\begin{aligned}\n",
    " -1 \\le  \\sin(n) \\le 1 \n",
    " &\\Rightarrow -n \\le  n\\sin(n) \\le n \\\\ \n",
    " &\\Rightarrow 2n-n \\le 2n + n\\sin(n) \\le 2n+n \\\\\n",
    "&\\Rightarrow n \\le 2n + n\\sin(n) \\le 3n \\\\\n",
    "\\end{aligned}\n",
    "$n_0 = 1, c_0 = 1, \\text{ and } c_1 = 3, \\forall n \\ge n_0$:\n",
    "$$c_0 g(n)   \\le f(n) \\le  c_1 g(n)$$\n",
    "Therefore,\n",
    "$$f\\in \\Theta(g)$$\n",
    "\n",
    "\\begin{aligned}\n",
    "\\lim_{n\\to \\infty} \\frac{f(n)}{g(n)} &= \\lim_{n\\to \\infty} \\frac{2n+n\\sin(n)}{n}\\\\\n",
    "&=\\lim_{n\\to \\infty} (2+\\sin(n))\\\\\n",
    "&= 2 + \\lim_{n\\to \\infty} \\sin(n)\\\\\n",
    "\\end{aligned}\n",
    "Since $\\lim_{n\\to \\infty} \\sin(n)$ doesn't exist, $\\lim_{n\\to \\infty} \\frac{f(n)}{g(n)}$ doesn't exist either.\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question3**\n",
    "\n",
    "Prouvez que $f(n) = \\lg n$, $p(n) = \\sum_{i=0}^{k}a_in^{k-i}, a_i\\in \\mathbb R, i,k \\in \\mathbb N$, sont lisses.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer3**\n",
    "\n",
    "**part1** prove that $f(n) = \\lg n$ is lisse.\n",
    "\n",
    "First, $\\exists n_0 = 1, \\forall n \\ge n_0$\n",
    "\\begin{align}\n",
    "f(n+1) - f(n) &= \\lg(n+1) - \\lg n \\\\\n",
    "&=  \\lg \\frac{n+1}{n} \\\\\n",
    "&= \\lg(1+\\frac{1}{n}) \\\\\n",
    "&\\ge 0 \\tag{3.1}\\\\\n",
    "\\end{align}\n",
    "We can say, function $f(n) = \\lg n$ is **e.n.d.** (éventuellement non-décroissante) \n",
    "\n",
    "Let $b\\in \\mathbb N^{\\ge 2}, c_b \\in \\mathbb R^{> 1} \\subset \\mathbb R^{\\ge 0} \\$,\n",
    "\n",
    "\\begin{align}\n",
    "f(bn) - c_b f(n) \\le 0 &\\Leftrightarrow \\lg(bn) - c_b \\lg n \\le 0 \\\\\n",
    "&\\Leftrightarrow \\lg n + \\lg b - c_b\\lg n \\le 0\\\\\n",
    "&\\Leftrightarrow (1 - c_b) \\lg n + \\lg b \\le 0\\\\\n",
    "&\\Leftrightarrow \\lg n \\ge  \\frac{\\lg b}{c_b - 1}\\\\\n",
    "&\\Leftrightarrow n \\ge  2^{\\frac{\\lg b}{c_b - 1}}  \\\\\n",
    "\\end{align}\n",
    "Which means,\n",
    "\n",
    "$\\exists c_b \\in \\mathbb R^{> 1} \\subset \\mathbb R^{\\ge 0}, n_b = \\lceil 2^{\\frac{\\lg b}{c_b - 1}} \\rceil \\in \\mathbb N, , \\forall n \\ge n_b, \\forall b \\in \\mathbb N^{\\ge 2}$,\n",
    "\n",
    "$$f(bn) \\le c_b f(n) \\tag{3.2}$$\n",
    "\n",
    "Based on (3.1) and (3.2) We can say: $\\lg n$ is lisse.\n",
    "\n",
    "\n",
    "<br>\n",
    "\n",
    "\n",
    "**part2** prove that $p(n) = \\sum_{i=0}^{k}a_i n^{k-i}, a_i\\in \\mathbb R, i,k \\in \\mathbb N$ is lisse.\n",
    "<hr>\n",
    "To prove $p(n) = \\sum_{i=0}^{k} a_i n^{k-i}, a_i \\in \\mathbb R, i,k \\in \\mathbb N$ is lisse,\n",
    "\n",
    "we **need more constrain for $a_i$**: $a_0 > 0$, which is a special case of more general constrains:$$ a_j > 0 \\text{ and }\\forall i<j, a_i = 0, \\text{ where }j < k$$\n",
    "Otherwise, $p(n)$ may not always **e.n.d.** or lisse.\n",
    "\n",
    "We know that, for $x, r_i \\in \\mathbb R, a_0 \\prod_{i=0}^{k}(x-r_i)$ can be expanded to the form of $\\sum_{i=0}^{k} a_i x^{k-i}$, that is:\n",
    "$$\\prod_{i=0}^{k}(x-r_i) = \\frac{1}{a_0} \\sum_{i=0}^{k} a_i x^{k-i}$$\n",
    "where $a_k = a_0 (-1)^k \\prod_{i=0}^{k} |r_i|$.\n",
    "\n",
    "So, $\\exists C \\in \\mathbb R$, satisfies:\n",
    "\n",
    "$$\\sum_{i=0}^{k} a_i x^{k-i} = a_0 \\prod_{i=0}^{k}(x-r_i) + C$$\n",
    "\n",
    "As $n\\in \\mathbb N \\subset \\mathbb R$, it is true that:\n",
    "\n",
    "$$p(n) = \\sum_{i=0}^{k} a_i n^{k-i} = a_0 \\prod_{i=0}^{k}(n-r_i) + C \\tag{3.3}$$\n",
    "\n",
    "$\\exists n_0 = max\\{r_i \\ |\\ i \\in \\mathbb N, i \\le k\\}$, such that: $\\forall n \\ge n_0, n-r_i \\ge 0$, and:\n",
    "\\begin{align}\n",
    "p(n+1) - p(n) &= a_0\\prod_{i=0}^{k}(n+1-r_i) + C - \\Bigl( a_0\\prod_{i=0}^{k}(n-r_i) + C \\Bigr) \\\\\n",
    "&= a_0\\prod_{i=0}^{k}(n+1-r_i) - a_0\\prod_{i=0}^{k}(n-r_i) \\\\\n",
    "&\\ge a_0\\prod_{i=0}^{k}(n-r_i) - a_0\\prod_{i=0}^{k}(n-r_i) \\\\\n",
    "&= 0 \\\\\n",
    "\\end{align}\n",
    "We can say, function $p(n)$ is **e.n.d.** (éventuellement non-décroissante) \n",
    "\n",
    "\n",
    "Let $$n_b = \\lceil max\\{r_i,\\ r_i\\Bigl(1+\\frac{1}{b} \\Bigr) \\ |\\  i \\in \\mathbb N, i \\le k\\} \\rceil \\tag{3.4}$$\n",
    "such that $\\forall n \\ge n_b$, we have:\n",
    "$$n-r_i \\ge 0,\\ bn-r_i \\ge 0,\\ p(bn)>0,\\ p(n)>0 \\tag{3.5}$$, and,\n",
    "$$r_i\\Bigl(1+\\frac{1}{b} \\Bigr) \\le n, \\text{ where } 0 \\le i \\le k \\tag{3.6}$$\n",
    "\n",
    "let $b \\in \\mathbb N^{\\ge 2}, c_b = b^{2k}$, such that: $c_b \\in \\mathbb R^{>0}$.\n",
    "\n",
    "Based on (3.5), we have:\n",
    "\n",
    "\\begin{align}\n",
    "p(bn) - c_b p(n) <= 0 &\\Leftrightarrow \\frac{p(bn)}{c_b p(n)} \\le 1\\\\\n",
    "&\\Leftrightarrow \\frac{\\prod_{i=0}^{k}(bn-r_i) + C}{c_b \\prod_{i=0}^{k}(n-r_i) + C} \\le 1\\\\\n",
    "&\\Leftrightarrow \\frac{\\prod_{i=0}^{k}(bn-r_i)}{b^{2k} \\prod_{i=0}^{k}(n-r_i)} \\le 1\\\\\n",
    "&\\Leftrightarrow \\frac{\\prod_{i=0}^{k}(bn-r_i)}{\\prod_{i=0}^{k}b^{2}(n-r_i)} \\le 1  \\tag{3.7}\\\\\n",
    "\\end{align} \n",
    "\n",
    "To prove (3.7), we only need to prove $\\frac{bn-r_i}{b^2(n-r_i)} \\le 1,$ for all $i$ where $ 0 \\le i \\le k$:\n",
    "\\begin{align}\n",
    "\\frac{bn-r_i}{b^2(n-r_i)} \\le 1 &\\Leftrightarrow bn-r_i \\le b^2(n-r_i)\\\\\n",
    "&\\Leftrightarrow bn-r_i \\le b^2 n - b^2 r_i \\\\\n",
    "&\\Leftrightarrow (b^2-1)r_i \\le (b^2-b)n\\\\\n",
    "&\\Leftrightarrow (b+1)(b-1)r_i \\le b(b-1)n\\\\\n",
    "&\\Leftrightarrow  \\frac{b+1}{b} r_i \\le n\\\\\n",
    "&\\Leftrightarrow  \\Bigl(1+\\frac{1}{b} \\Bigr) r_i\\le n \\tag{3.8}\\\\\n",
    "\\end{align}\n",
    "\n",
    "(3.8) is same with (3.6),which is implied by (3.4), the choose of $n_b$.\n",
    "\n",
    "Finally, we can say $p(n) = \\sum_{i=0}^{k} a_i n^{k-i}, a_i \\in \\mathbb R, a_0 >0, i,k \\in \\mathbb N$ is lisse.\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAEDCAYAAAAhsS8XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XmcjeX/x/HXZzaz2Pfd0NcukSEpkqSFIlREkixpFYWirClalFK+hLZJUmlTfWWrFNn3nSxjN5h9Pef6/THH/IbZcM6c+5wzn+fjcR7O3Ne9vM99bp+55jr3uW8xxqCUUsp3+FkdQCmllGtpYVdKKR+jhV0ppXyMFnallPIxWtiVUsrHaGFXSikfY1lhF5E5InJKRLZdxrxTRWST47FHRM67I6NSSnkjseo8dhFpA8QDnxpjGl3Bck8DTY0x/QosnFJKeTHLeuzGmD+As1mnicg1IvKriKwXkT9FpF4Oi/YE5rklpFJKeaEAqwNcYibwuDFmr4jcAHwAtLvQKCI1gJrAMovyKaWUx/OYwi4iRYFWwAIRuTC5yCWz9QC+NsbY3JlNKaW8iccUdjKGhc4bY5rkMU8P4Ek35VFKKa/kMac7GmNigX9F5H4AyXDdhXbHeHspYJVFEZVSyitYebrjPDKKdF0RiRKRx4BewGMishnYDnTOskgP4Eujl6NUSqk8WXa6o1JKqYLhMUMxSimlXMOSD0/Lli1rwsPDrdi0Ukp5rfXr158xxpTLbz5LCnt4eDjr1q2zYtNKKeW1ROTQ5cynQzFKKeVjtLArpZSP0cKulFI+xmO+eZqWlkZUVBTJyclWR/FowcHBVK1alcDAQKujKKU8lMcU9qioKIoVK0Z4eDhZrhWjsjDGEB0dTVRUFDVr1rQ6jlLKQ3nMUExycjJlypTRop4HEaFMmTL6V41SKk8eU9gBLeqXQfeRUio/HlXYlVLKVyUlwbPPwqHLOhPdOVrYC1irVq2sjqCU8gAffmCYNg0O/lvw1+fSwl7A/v77b6sjKKUsFhsLk8ancTuLueXkVwW+PS3sDmvXrqVx48YkJyeTkJBAw4YN2bZtW7b5unTpQrNmzWjYsCEzZ84E4NChQ9SuXZszZ85gt9tp3bo1ixcvBqBo0aIAHD9+nDZt2tCkSRMaNWrEn3/+6b4Xp5Sy1NtvGaJjg5hUeTrcd1+Bb89jTne81IP/zX4/jU6NK/HwjeEkpdroO3dNtvbuzapyf0Q1ziakMvjz9Re1zR90Y57ba968Offeey+jR48mKSmJ3r1706hRo2zzzZkzh9KlS5OUlETz5s3p1q0bNWrUYMSIEQwePJgWLVrQoEEDOnTocNFyX3zxBXfccQejRo3CZrORmJh4ObtBKeXlTp+Gt6ak043viZh8PwQFFfg2PbawW+GVV16hefPmBAcHM23atBznmTZtGgsXLgTgyJEj7N27lzJlytC/f38WLFjAjBkz2LRpU7blmjdvTr9+/UhLS6NLly40aZLXHQCVUr7itVdtJCb7MaH2Z9DzW7ds0yWFXURKAh8BjQAD9DPGOHULu7x62CFB/nm2lw4LyreHnpPo6Gji4+NJS0sjOTmZsLCwi9pXrFjBkiVLWLVqFaGhobRt2zbznPLExESioqIAiI+Pp1ixYhct26ZNG/744w8WLVpE3759GTp0KH369LnijEop73HkCHww3fAIn1L/rf7g7++W7bpqjP1d4FdjTD3gOmCni9brVoMGDWLChAn06tWLESNGZGuPiYmhVKlShIaGsmvXLlavXp3ZNmLECHr16sX48eMZMGBAtmUPHTpEhQoVGDBgAP3792fDhg0F+lqUUtYb93I6Jt3G2GY/QadObtuu0z12ESkBtAH6AhhjUoFUZ9frbp9++imBgYE89NBD2Gw2WrVqxbJly2jXrl3mPHfeeSczZsygfv361K1bl5YtWwLw+++/s3btWv766y/8/f355ptvmDt3Lo8++mjmsitWrOCNN94gMDCQokWL8umnn7r9NSql3Gf3bpj7qR9P8z7V3x4CbvxyodP3PBWRJsBMYAcZvfX1wLPGmIRL5hsIDASoXr16s0OXnKW/c+dO6tev71SWwkL3lVKe74Euqfz8fSoH2g2g/NJ5LlmniKw3xkTkN58rhmICgOuBD40xTYEEYOSlMxljZhpjIowxEeXK5XtnJ6WU8lqrVsGC74MYxtuUfztbOSxwrijsUUCUMeYfx89fk1HolVKq0DEGhj6ZTEWO80Lv43DddW7P4HRhN8acAI6ISF3HpNvIGJZRSqlCZ8ECWL0xmIlB4yk6+WVLMrjqPPangUgRCQIOAI/mM79SSvmclBQY+VwyjdlN3xEVoXJlS3K4pLAbYzYB+Q7oK6WUL3tvmuHfY8EsLv0a/iNmW5ZDv3mqlFIucOYMTBybxl0s4fYpt8MlX3B0J70I2GXq3r07Bw4cAP7/wl6Xa+vWrfTt27cAUimlPMX4MenEJfrzRp2PwOL/71rYL8P27dux2WzUqlXrqpa/9tpriYqK4vDhwy5OppTyBDt3woczhAHMouH7g9126YDcaGHP4uDBg9SrV49evXpRv359unfvTmJiIpGRkXTu3PmieZ977jkaNmzIbbfdxunTpwFo27YtI0aMoEWLFtSpU+eiS/Pec889fPnll259PUqpgmcMPDMomaL2WCbc+TfcfrvVkTx0jH3IEMjhColOadIE3nkn39l2797N7Nmzuemmm+jXrx8ffPABf/31Fz179sycJyEhgYiICKZOncr48eMZN24c77//PgDp6emsWbOGn3/+mXHjxrFkyRIAIiIieP311xk+fLhrX5dSylLffgtL/gzmvYCRlPtgnNVxAO2xZ1OtWjVuuukmAHr37s3KlSs5fvw4Wb8t6+fnx4MPPnjRPBd07doVgGbNmnHw4MHM6eXLl+fYsWNueAVKKXdJTMz4MtK1bOHxkaWgZk2rIwGe2mO/jJ51QZFLLtQjIoSEhGRenje/ZYoUKQKAv78/6enpmdOTk5MJCQlxcVqllJVen2Tn8Mlgfq8wkYAXP7Y6TibtsV/i8OHDrFqVcSn5L774gptvvpn69euzb9++zHnsdjtff/31RfPkZ8+ePTnekUkp5Z3274cpk+08RCRtPugBoaFWR8qkhf0SdevWZfr06dSvX59z584xePBgOnbsyIoVKzLnCQsLY82aNTRq1Ihly5bxyiuv5Lve5cuX07FjxwJMrpRyp+eeSCEgPZkprX9yy31Mr4RnDsVYKCAggM8///yiad27d+fWW29l3Lhx+Pv7Ex8fn+OyWYt/2bJlM8fYU1JSWLduHe9YOMSklHKdRYvgx8VFmOw3hiozx7j1WuuXQ3vslyEkJIRx48Zx9OjRq1r+8OHDvP766wQE6O9RpbxdfDw80S+ZBmxnyPOBUK+e1ZGy0UqTRXh4ONu2bcux7Y477rjq9dauXZvatWtf9fJKKc8xZlQ6h08F82fl8QSN/djqODnSHrtSSl2mDRvgnff8GMh/ufmTAeChZ7ppYVdKqcuQng4D+yRR3pxk8gMboH17qyPlSodilFLqMrz/np3120OYH/YkJd+fbHWcPGlhV0qpfBw+DKNftHE3v3D/tNbg4fdt1sKulFJ5MAYe75uESbEz/YbPkEfnWR0pX1rYlVIqD3PnGH5ZHsJ7gUMJj3zV485Zz4l+eOpGSUlJ3HLLLdhstlznSU1NpU2bNhddZ0YpZY3Dh+G5p9Noy3KeeLMWXHON1ZEuixZ2N5ozZw5du3bFP4+L8AcFBXHbbbcxf/58NyZTSl3KGOjfOwlbUiqzb5iF31NPWB3psmlhv8SxY8fo1q0bTZs2pV69eqxZs+aK19GzZ08efPBBWrRoQY0aNVi0aBFAtht2dO3aldGjR9OmTRuqV6+eee32Ll26EBkZ6ZoXpJS6Kh/NMvz2ZwhvBI2m1rxXwc97yqXLxthFxB9YBxw1xnRyZl1W3WcjPT2du+66i1dffZVOnTqRmJiY57AJQGJiIiEhIRddunfz5s107tyZ+fPns3LlSoYOHcrtt9/OgQMHCA8Pz5xv69attGrVij/++IOFCxcSGRlJ+/btadSoEWvXrnXm5SqlnHDoEAx9Jo12/Mmgt+t6zHXWL5crfwU9C+x04frc7rvvvqN+/fp06pTxeyk0NJRixYrRv3//XJepVasWhw4dyvw5OTmZ06dPM2bMGAAaNGjAuXPnOHPmDCVLlsycLzExkZiYGJ577jkA0tLSMtv9/f0JCgoiLi7O5a9RKZU3ux369UyClBRmt5qD3+BBVke6Yi7psYtIVaAj8Cow1Nn1WXURxE2bNtGyZcuLpiUlJbFz507Gjh3Lrl27mDdv3kW9840bN1K+fPnMn7dt20bt2rUJDg4GYMOGDVx33XXZbtaxY8cOmjVrljnevmXLlouu156SkpK5DqWU+7w1xcayVSHMCnma8C8medUQzAWuSvwOMBywu2h9lqhYsSLbt2/P/Pn06dNs3LiR+++/n7Fjx1KiRAliYmIuWqZSpUoXfRi6efNmDh8+THJyMgkJCYwZM4bnnnuOUqVKYbPZMov71q1badKkSeZyW7ZsoXHjxgBER0dTtmxZAgMDC/LlKqUusWEDjBpluI9veWzOzVCjhtWRrorThV1EOgGnjDHr85lvoIisE5F1p0+fdnazBaJv376cPHmShg0b0qRJE1atWsWaNWsyC25iYuJFwyk52bx5M127duWGG26gefPmDB48OPMeqh06dMi8P+qlhX3btm2ZPXa9KYdS7peQAD27JFLefoJZDy5FejxodaSrZ4xx6gG8BkQBB4ETQCLweV7LNGvWzFxqx44d2aZ5gv79+5sRI0aYQYMGmeXLl+c7f5s2bcyuXbtybFu/fr3p3bt3vuu47777zO7du3Nt99R9pZQ3G/BIshFsZmmlXsbExlodJ0fAOnMZddnpMXZjzIvAiwAi0hZ43hjT29n1eopZs2Zd0fz79+/P9drr119/Pbfeeis2my3Xc9lTU1Pp0qULderUueKsSqmrs/Bbw6xPijBc3qDdwqehWDGrIzlFLyngYlFRUXm29+vXL8/2oKAg+vTp48pISqk8HD4M/fuk0IxtTHglDW64wepITnNpYTfGrABWuHKdSilVUFJT4YFOCaQnpDPvxvcIenmO1ZFcQnvsSqlC64VnU/hnaxjflHyM2gunQB6X+/AmHnWCZsZnAyovuo+Uco0FXxmmzSjCEHmXrj/0hQoVrI7kMh5T2IODg4mOjtbClQdjDNHR0frFJaWctGcPPNYnjZasYvKr6dC6tdWRXMpjhmKqVq1KVFQUnnqOu6cIDg6matWqVsdQymslJMD9HRMISkniq9s/ImjkR1ZHcjmPKeyBgYHU9LIL7SilvIsx8GiPRLbuC+GXSk9Rbf7bXnHjjCvlMYVdKaUK2qRxaSz4KZQpQaO547fnoVQpqyMVCI8ZY1dKqYL0w/eG0eMC6cXnPD+/OTRsaHWkAqOFXSnl87Zvh14PptGMdcx6JQrp0jn/hbyYDsUopXxadDR0vj2BsJQ4vrt7FiFjZ1gdqcBpYVdK+azkZOjcPp6o4wEsqz2SqvPf98kPSy+lhV0p5ZPsdujTPYG/NhVlfpknaLViEhQtanUst9AxdqWUTxo5JJkFi8KYUuRlHljxBFSubHUkt9HCrpTyOR9MS+eN94J5Qj7k+Z/aQpbbThYGWtiVUj7lu2/tPD3Ej3v4gXdnF0Xa32Z1JLfTwq6U8hlLfjM8eL+NFuYf5o3bS8CjD1sdyRJa2JVSPmHVKujSMZW69p38/Oxiwl4ZZnUky+hZMUopr7dlC9zdLplKaUdY/PDnlJo62epIltLCrpTyanv2QIfWiRRNjmbJve9Rce7UQnGuel60sCulvNauXdCuZQL22AR+azuJGl9P85m7IDlDC7tSyivt3HmhqMezvO0E6v36DgQGWh3LI2hhV0p5nR07Moo6cXEsv3UiDX59G4KCrI7lMfSsGKWUV9m6FdrekIhfXAwr2r+qRT0HThd2EakmIstFZIeIbBeRZ10RTCmlLvXXSkObFkkExp9jxR2vU+9nLeo5cUWPPR0YZoxpALQEnhSRBi5Yr1JKZVr0g43b26ZRLvkIf/V4nzqLpuqYei6cLuzGmOPGmA2O53HATqCKs+tVSqkLPp+bRucuUN+2lZXPfk34F5P07Jc8uHSMXUTCgabAPzm0DRSRdSKy7vTp067crFLKRxkDb45P5OF+gdxiVrD8tX8o/85Lhf489fy4rLCLSFHgG2CIMSb20nZjzExjTIQxJqJcuXKu2qxSykelpcGgnjG8MCaU++VrFs0+SfGRT1gdyyu45HRHEQkko6hHGmO+dcU6lVKF17lz0L39OZZtKMVLIW8z4Zfm+N3S2upYXsPpwi4iAswGdhpj3nY+klKqMNu3Dzq1juHAiTA+qTiCPn8OgP/8x+pYXsUVQzE3AQ8D7URkk+NxtwvWq5QqZH5amEbzRomcOZHG0uuH02fHSC3qV8HpHrsxZiWgn2Qopa6azQZjh8Uy8d3iNGUr3zz2CzU/fENPZ7xKekkBpZSlzpyBXnedZfG60vQL+JT3Pw4jpNcoq2N5NS3sSinLrFhq4+Gu8ZyODWVWxZfpv+whqF/f6lheT68Vo5Ryu9RUePHxc7RrL4TEnuSvTq/Rf89wLeouoj12pZRb7dlt6HVXNOv+LUv/wE94Z1YYYY+MszqWT9Eeu1LKLWw2eHd8DE0bpnDgX+GbBqOZte9Wwh7pbnU0n6M9dqVUgdu+zfBY59P8c6A8Hf1+5r+jDlFl3Di93ksB0R67UqrApKbC+CFnado4nX0H/IisN4Efd9WhysTBWtQLkPbYlVIF4udvkxkyIJ69Z8vSM2AB776WSLmho8BP+5MFTQu7Usql9u01DHnwGIs2VqEOh/il3Vzu/KwXVK5sdbRCQ391KqVcIjoaXnjoKA3rpvHHxmK8UXkqW5dHc+fSF7Sou5n22JVSTomLg6kjTvDmrOIkpFekT8gCJo1Lo9LQZ3Qc3SJa2JVSVyUxEWZOOMmkqcGcTqnIfYE/MnHICRpMfAjCwqyOV6hpYVdKXZFz52D6i1G8O7cYZ1IrcJvfMib12UmLdx6CUqWsjqfQwq6UukxHDtl5d+gh/vt9BeJtVekY8D9GPnKEm9/sAmXbWR1PZaGFXSmVK7sdln4Xx/RXTvLj9poI1egR/D3Dn4mj8bhuUKyY1RFVDrSwK6WyOXnCEDnxX2Z8Fsre2IqUI4kRVb9g0AvFqfH4PRAUZHVElQct7EopIOPD0O9mnOCzD+L4bX9NbNSild8qxty6iO6Tm1Ok+cNWR1SXSQu7UoVYfDz8OvsoC+ee54et4cTbK1KNVIaHL+DhQaHUf+o2KHqj1THVFdLCrlQhE/VvGv+beZDvvk7nt/21SDFVKEMRHii7lIe7JdJmVGv8qvW0OqZyghZ2pXxczHnDis+PsOSrcyzZWJpd8dWA2tTgIIOr/USX+4SbnmtBQPi9VkdVLqKFXSkfYgzs3RjPqvmHWb0iidW7SrIlNhw71QmlDLeErmXAjf/QvntJru3bDCndzerIqgBoYVfKSyUmGLYvPcHWpafYui6FrftD2HimGmdtJYEGFCeGG0K3MbrJNtrdHsCN/RsSVKet1bGVG7iksIvIncC7gD/wkTHmdVesV6nCzBiIPZ3CofVn2L/2LPu3JrJ/v+HAsWD2nSvLv6mVMVQCKhFKAg2D9tK1yj+0vC6ZGzuWpl73RviVucnql6Es4HRhFxF/YDpwOxAFrBWRH4wxO5xdt1K+wtgNyeeTiT2ZxPmjCZyLSuD88STOn0rh3Kl0zp21c/K0P8fPBHIsJpTjCSU4nlaGJEKBKo4HlOIs1xQ5SkTp/fSptplrmwZw7a1lqdXhP/iXbmLpa1SewxU99hbAPmPMAQAR+RLoDBRIYZ/w0w5OxCRfNK1+pWI81a42AKMWbuV8YtpF7U2rl6R/61oAPL9gM0mptovaW15Thodb1gDg6XkbsdvNRe231C3HAxHVSE2389z8TdkydWhYgc5NqhCXnMbIb7Zma7+3SWXuaFiR03EpjP1he7b2+yOq0rZueY6cTeT1X3Zla3/4xhq0rFWGfafimfrbnmztA9rUokm1kmw/FsMHy/dna3+q3X+oX6k46w+dY87Kf7O1D+tQh1rlivL3vjNE/nM4W/uojvWpXDKE5btO8fX6qGztE7o0onRYEL9uO86Pm49na5/SvTFhRQL4buNRfttxMlv7uz2aEODvx/y1h/ljzxkAbOmQGi8ExqQxuGk14k4lsXzdMQ4djsOWYLAlgi1V8LPDNaWLk5ZqOHImmfgkG/Z0P2w2wWb3R8SPMmGBGCOcT0wlzWbgwttrwN9PKBYcCAZik9NJtxmMo90YQcSP0KAA7EaIT7Fjs2dMNwjGgIgfgf4BGCAhFVLsQaTag0i2B5FqipBsgkmmCMmEQOajdLZ9AFCcGMr7naJs0DnqFD1JRLFEqlYWWjQOpca1YXwde57kaqUxfv5AMU5RDP+GFah94diL3JBtnXrsXfmxd0GAv/Buj6YAfPL3Qdb8e/ai9rAi/kzpfh0A//19P1uiYi5qL1M0iPGdGwEwbeledp+I4/YGFejStEq2HK7misJeBTiS5eco4IZLZxKRgcBAgOrVq1/1xg6eSeDQ2cSLphUP+f+X8e+ZBE7FpVzUXqF4cObzfafiiU9Jv6g9vGxo5vO9J+NIv6SwN6hcHACDYffJuGyZrq+RceEjmz3n9rMJqQCk2ew5tsckZfwiSknPuT3W0Z6cZsuxPT454/UkpOTcnpia0R6XnJZje3KaPWM7ubSnpme0n0tMzbE9zZbRHp2Qc7vNUSnPxKew/VAi9lNC8NEk/I7bsEf7MfDNTZw5F0DU2QCik8pw3laSWFMic/mZmc9qZVv3BYGkEkQqgaQRQDqBkvGvnxj8BRAwdjsZ76IgGEQMQsZ/YMFkvO/GgIAfdgSDvx8USQU/DKk2Gxi7Y7mM5QP9DAF+fhnb8UujhH8Cgf7p+AekE+CfTokwIbx8EMHBws5T5/ALSsUv1A7FBHsxP65rVIZH761HyRol6PLZJtIdh14aAURTnDZNq/Dgrf8hJd3G6Gkr4fTFx74ee5d/7OXUfuF/+snY7O2B/v9/u4rjMcnZ2kuEBGY+P3Y+KVt7peT/rztR5xLZfTKOptVLZstQEMQYk/9cea1ApDtwpzGmv+Pnh4EbjDFP5bZMRESEWbdunVPbVZ4rMRH2bEtl9x8n2LUmjt077eyKKsr+uHLE2opeNK8/6VTgJOX8z1EuOJayYUmUK55K2TKGMmWgeEk/ipUKoGjpIIqVCaJo2WCKVQglrGwIISWCCAwLIiCsCBJcRK/9rXyeiKw3xkTkN58reuxHgWpZfq7qmKYKgfPnYeNfiWz8+TgbVqeyYV8xdsVWxhAEVEewU4ND1A05QqvKW6lROY1q4f5UrxdK9etKUbFpJQKqVoSAgv/zVKnCwhWFfS1QW0RqklHQewAPuWC9ygMdPgx/fhfNn99H8+eGouw4XxkIBa6hKke4PngHD9RdScOGULd5cWq3rUJI49oQWtPq6EoVGk4XdmNMuog8BfyPjNMd5xhjsn9Ko7xSTAws+S6eXz45yW9rSnA4oSxQhuIEcFPAGnrV/Y2IFv40vasi5dpdCxU6WB1ZqULPJeexG2N+Bn52xbqU9fbsNnw74xS/fJ/K3wcrkW6KUoJ0bgv8k2GNT9KmQwjX9miIf5N2Oq6tlAfSb54qAPbuhQUfnOareTY2n6wIVKAJG3mh/GLuusNOywHXEtjqbi3kSnkBLeyFWHQ0fDEjlrkfJLHxWAWgHK34i6nXfE23R4tT7ZF2UPUxq2Mqpa6QFvZCxm6HJf+zMef1kyxcWY5Ue3GuZy9Ta8yjW99iVBt4F1TWr6Er5c20sBcScXEw9/0Epr2Zyv6zpShNER4PmUu/++O57qWOUHeI1RGVUi6ihd3H/fsvvDfhPLMjixCbGkYrNjGx4XLue6k+Rbr31XtXKuWDtLD7qD17YNLzZ/n8pxKICeMB+ZpnO+6lxWv3wbWjrY6nlCpAWth9zM6d8Orz55j3c3GKEMyzQR8ydFACVV7sA5X0dmdKFQZa2H3EkSMw+ukYPvu+GCEEMSzofYY9nUqF0QOgpHsuPKSU8gxa2L1cTAy8/koi70wPwNiKMCzwPYY/nUS50YOgVCmr4ymlLKCF3UvZbDDzgzReeTGNMwmh9JbPmdh7FzXeegbKl7c6nlLKQlrYvdDatTC4dyzr9xSnLSt566aFXD/zcWjQ2+poSikP4Jf/LMpTnDsHTzyayA0t7Bzdk8C8CkNY9ksq16+cBg0aWB1PKeUhtMfuJb5baBj0SDJn4orwjN/7jBsWR4nxr0NwcP4LK6UKFS3sHu7sWXimfyKRC0Npwi5+vX46TT8fBvXrWx1NKeWhtLB7sJ9+NAzok8yZ84GMDZjIS2+VIfCpmeCnI2hKqdxpYfdAyckw9MlkPpwTzLXs5efGb9P061FQu7bV0ZRSXkALu4fZtQsevCeRLftCGeb3NpPGpRP04my9DrpS6rJpYfcgn3xseGJQOqGpCSwq/wR3//gEtGhhdSyllJfRwu4BUlLgyQEpzP6sCG1ZyecdPqPKl1P1m6NKqauihd1ix45Bt7uTWL05hFEyiXFvhuH/3GwQsTqaUspLaWG30OrV0LVjMrFnbXxdvB/dFvWDm2+2OpZSysvpeXMWmTvHcMvN6YScPcrqun3ptnWsFnWllEs4VdhF5A0R2SUiW0RkoYjo9WHzYQy8MspGv8eENrblrO08kUbrP4Hq1a2OppTyEc722H8DGhljGgN7gBedj+S7UlPhkYfSmDDJn37M5ueXV1N64RwIC7M6mlLKhzhV2I0xi40x6Y4fVwNVnY/km2Ji4O72KXz2ZSDjZQwfzfYjcPzL+iGpUsrlXPnhaT9gfm6NIjIQGAhQvZANO5w8CR1uSWbHbn8+DhrII9/dB3fdZXUspZSPyrewi8gSoGIOTaOMMd875hkFpAORua3HGDMTmAkQERFhriqtFzp8GNq3TuHoYRuLSvShw5LhEBE1ewsBAAANUUlEQVRhdSyllA/Lt7AbY9rn1S4ifYFOwG3GmEJTsC/Hvn1wW+sUzp9IYXH5vty0crJe70UpVeCcGooRkTuB4cAtxphE10TyDdu2we23pJJ+Lo7lVfpl3AwjPNzqWEqpQsDZMfb3gSLAb5LxIeBqY8zjTqfyclu2QLvWqRSJO8PvNQbQYOVMqFLF6lhKqULCqcJujPmPq4L4ih07oP0tqQTHnub3OgO45o+5UKGC1bGUUoWIXlLAhXbvzuipB8REs6z2IK7561MoW9bqWEqpQkYLu4vs25dR1M258yyt3o86f36sRV0pZQkt7C5w5EhGUU89E8vyyn2ov/IjHX5RSllGC7uToqPhjltTiDmZwu/letFo5X+hqn4BVyllHS3sTkhIgE53pHLgACwu3psmf76npzQqpSynhf0qpaXB/fels2a9P98EPUSbxaOhTh2rYymllBb2q2G3w2OP2vjltwBmyiC6fNdX702qlPIYeqONqzB2jOGzSH/G8zID5tyoF/RSSnkULexXKDISJkwU+jGb0RNDoG9fqyMppdRFdCjmCvz1F/Tra6Mtf/Bhn9XISzOtjqSUUtloYb9MBw5Al05p1LAd5JuWbxI081u9SYZSyiNpYb8MMTHQ6c40bDHxLKoyiNI/zIciRayOpZRSOdLCng+7HXr3TGfvXuG3kF7U/vU9KFfO6lhKKZUrLez5mDjB8NMvAUznSdoueBIaNrQ6klJK5UnPisnDokUwdhz04RMGT6wCHTtaHUkppfKlPfZc7NsHvXukc53Zxoy7f0Re/MrqSEopdVm0sOcgIQG63puGX0I831YfQkjkd+Cnf9wopbyDFvZLGAOPD7Szbac/vwb1oeaP06BkSatjKaXUZdPCfomPP4bPv/BjPC/T4aMHoHFjqyMppdQV0fGFLHbuhKcGp9OOpbw04Aw8/LDVkZRS6oppj90hKQke7JZGWGoMn9WZiP+7P1sdSSmlropLeuwiMkxEjIh47U0+hw01bN0ZyKcB/aj8zXsQEmJ1JKWUuipOF3YRqQZ0AA47H8ca33wDH84QXmAKd067Gxo1sjqSUkpdNVf02KcCwwHjgnW5XVQU9H80nRayhomd18GgQVZHUkoppzg1xi4inYGjxpjN4oVXOrTb4dE+NtLiU/iiwlCC5vygV2xUSnm9fAu7iCwBKubQNAp4iYxhmHyJyEBgIED16tWvIGLBmT4dliz3578M5ZovX4XSpa2OpJRSThNjrm4ERUSuBZYCiY5JVYFjQAtjzIm8lo2IiDDr1q27qu26yq5d0PQ6G+1Sf+WnIUuRqW9bmkcppfIjIuuNMRH5zXfVQzHGmK1A+SwbPAhEGGPOXO063SUtDfr0SicsPZaP/jMZmfQ/qyMppZTLFMrz2CdNgrUbAljg9ziVIt/UUxuVUj7FZYXdGBPuqnUVpA0bYMJ4O72JpPtLdaFFC6sjKaWUSxWqHntaGjz2SDrlOcO0RrPg5SVWR1JKKZcrVIX9zTdh07YAFvo9SanI9yEoyOpISinlcoWmsO/eDePG2OjOt3QZ1VCv2qiU8lmForDb7dD/URuhtjje+880GKVDMEop31UoCvuMGbBylT8f8ywV574GRYpYHUkppQqMzxf2I0dgxAs2OrCUPoNC4eabrY6klFIFyucL+9NP2rEnpfLf8i8jkxdbHUcppQqcTxf2H3+E73/0YzJjCJ/5EpQoYXUkpZQqcD57a7zERHjmyXQayA6G3HMAOne2OpJSSrmFz/bYJ02Cg0cCWBE0hKBpM62Oo5RSbuOThX33bpgy2c7DfM4tr9wC4eFWR1JKKbfxucJuDDz1hJ1QezxvhH8Az/9udSSllHIrnyvsX30FS5b5MZ2RVPhwrJ6zrpQqdHyqsCckwLAh6VwvWxnU5TTceafVkZRSyu18qrBPmQJHTwQwP2gY/u98bHUcpZSyhM8U9sOHYcrrNnrwFTeNvhU85L6qSinlbj5T2EeOMJCWxuSK78Cw5VbHUUopy/jEF5T+/hvmfSm8YKZQ/c1nIDTU6khKKWUZry/sdjsMecZGZb/jDG+2DHr2tDqSUkpZyuuHYiIjYe16fz5lOEWnTQI/r/9dpZRSTvHqwp6QACNfSKeFbKTX/enQqpXVkZRSynJeXdinToVjJwNYEPgCflM+sTqOUkp5BKfHLUTkaRHZJSLbRWSKK0JdjtOnM05vvI9vafV8K6hRw12bVkopj+ZUj11EbgU6A9cZY1JEpLxrYuXv1VczhmImlXwDRv7PXZtVSimP52yPfTDwujEmBcAYc8r5SPn791/4YLqdx5hNvTEPQvHi7tisUkp5BWcLex2gtYj8IyK/i0jz3GYUkYEisk5E1p0+fdqpjb78siHAlsqYyh/B4487tS6llPI1+Q7FiMgSoGIOTaMcy5cGWgLNga9EpJYxxlw6szFmJjATICIiIlv75dq4ESIjhRd5myqTnoTg4KtdlVJK+aR8C7sxpn1ubSIyGPjWUcjXiIgdKAs41yXPw4sj7ZTyi2V4nR+h98qC2oxSSnktZ4divgNuBRCROkAQcMbZULlZtgz+t9iPUfYJlJz8Ivj7F9SmlFLKazlb2OcAtURkG/Al8EhOwzCuMu+zdKr5H+XJlhvgnnsKajNKKeXVnDrd0RiTCvR2UZZ8zaz7Fkds0wmeEgki7tqsUkp5Fa+6sIpUqkj1frdD69ZWR1FKKY/lXZcUeOSRjIdSSqlceVWPXSmlVP60sCullI/Rwq6UUj5GC7tSSvkYLexKKeVjtLArpZSP0cKulFI+Rgu7Ukr5GCnAS7vkvlGR08Chq1y8LAV4oTEnaK4ro7mujKfmAs/N5ou5ahhjyuU3kyWF3Rkiss4YE2F1jktpriujua6Mp+YCz81WmHPpUIxSSvkYLexKKeVjvLGwz7Q6QC4015XRXFfGU3OB52YrtLm8boxdKaVU3ryxx66UUioPWtiVUsrHeHRhF5H7RWS7iNhFJOKSthdFZJ+I7BaRO7JMv9MxbZ+IjHRDxvkissnxOCgimxzTw0UkKUvbjILOckmusSJyNMv2787SluO+c1OuN0Rkl4hsEZGFIlLSMd3S/eXI4NZjJ48c1URkuYjscBz/zzqm5/qeujHbQRHZ6tj+Ose00iLym4jsdfxbys2Z6mbZJ5tEJFZEhlixv0RkjoicctwH+sK0HPePZJjmON62iMj1LgtijPHYB1AfqAusACKyTG8AbAaKADWB/YC/47EfqAUEOeZp4Ma8bwGvOJ6HA9ss3HdjgedzmJ7jvnNjrg5AgOP5ZGCyh+wvS4+dS7JUAq53PC8G7HG8bzm+p27OdhAoe8m0KcBIx/ORF95TC9/HE0ANK/YX0Aa4PuuxnNv+Ae4GfgEEaAn846ocHt1jN8bsNMbszqGpM/ClMSbFGPMvsA9o4XjsM8YcMBk32v7SMW+BExEBHgDmuWN7Tsht37mFMWaxMSbd8eNqoKq7tp0Py46dSxljjhtjNjiexwE7gSpWZLlMnYFPHM8/AbpYmOU2YL8x5mq/2e4UY8wfwNlLJue2fzoDn5oMq4GSIlLJFTk8urDnoQpwJMvPUY5puU13h9bASWPM3izTaorIRhH5XUSsuAP3U44/8eZk+fPYyn10qX5k9FgusHJ/edJ+ySQi4UBT4B/HpJzeU3cywGIRWS8iAx3TKhhjjjuenwAqWJDrgh5c3Lmyen9B7vunwI45ywu7iCwRkW05PCzpLeXkMjP25OID6jhQ3RjTFBgKfCEixd2Y60PgGqCJI8tbrty2E7kuzDMKSAciHZMKfH95GxEpCnwDDDHGxGLhe5rFzcaY64G7gCdFpE3WRpMxxmDJOdQiEgTcCyxwTPKE/XURd+2fgILeQH6MMe2vYrGjQLUsP1d1TCOP6Vctv4wiEgB0BZplWSYFSHE8Xy8i+4E6wDpn81xuriz5ZgE/OX7Ma9+5JZeI9AU6Abc5DnS37K98FPh+uRIiEkhGUY80xnwLYIw5maU963vqNsaYo45/T4nIQjKGsE6KSCVjzHHHUMIpd+dyuAvYcGE/ecL+csht/xTYMWd5j/0q/QD0EJEiIlITqA2sAdYCtUWkpuO3dw/HvAWtPbDLGBN1YYKIlBMRf8fzWo6MB9yQ5cL2s47V3Qdc+JQ+t33nrlx3AsOBe40xiVmmW7q/sO7Yycbxec1sYKcx5u0s03N7T92VK0xEil14TsYH4dvI2E+POGZ7BPjenbmyuOivZqv3Vxa57Z8fgD6Os2NaAjFZhmyc485PjK/iE+b7yBh3SgFOAv/L0jaKjLMYdgN3ZZl+NxlnEewHRrkp58fA45dM6wZsBzYBG4B73LzvPgO2AlscB1Cl/Padm3LtI2NccZPjMcMT9pdVx04uOW4m48/1LVn20915vaduylWLjLOFNjveq1GO6WWApcBeYAlQ2oJ9FgZEAyWyTHP7/iLjF8txIM1Rux7Lbf+QcTbMdMfxtpUsZ/45+9BLCiillI/x1qEYpZRSudDCrpRSPkYLu1JK+Rgt7Eop5WO0sCullI/Rwq6UUj5GC7tSSvmY/wNOPtUDa35DKgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 True\n"
     ]
    }
   ],
   "source": [
    "# tiny demostration of question2 or question3\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def p_n(n, roots, const): # for question3\n",
    "    k = len(roots)    \n",
    "    #roots = np.random.randint(-root_limit, root_limit, k)\n",
    "    result = np.ones_like(n)\n",
    "    for i in range(k):\n",
    "        result *= (n-roots[i])\n",
    "    return result + const\n",
    "\n",
    "def n_plus_n_sin(n): # for question2\n",
    "    return 2*n + n * np.sin(n)\n",
    "\n",
    "def g_n(n): # for question2\n",
    "    return n\n",
    "\n",
    "C, b, k = 10, 4, 3\n",
    "c_b = pow(b, k) # c_b should be no less than pow(b, k) to satisfy p(bn) <= c_b p(n)\n",
    "\n",
    "roots = np.random.randint(-10, 10, k)\n",
    "n = np.arange(-100, 100, 0.1)\n",
    "p_bn = p_n(b*n, roots = roots, const = C)\n",
    "cb_pn = c_b * p_n(n, roots = roots, const = C)\n",
    "\n",
    "f_n = n_plus_n_sin(n)\n",
    "z = n*0\n",
    "\n",
    "# plot of second parth of question 3\n",
    "plt.plot(n, z, '--', label = \"x axis\")\n",
    "plt.plot(n, p_bn, 'r', label = 'p(bn)')\n",
    "plt.plot(n, cb_pn, 'b', label = \"$c_b \\cdot p(n)$\")\n",
    "plt.legend()\n",
    "\n",
    "# plot of question2\n",
    "#plt.plot(n, f_n)\n",
    "#plt.plot(n, 1*g_n(n))\n",
    "#plt.plot(n, 3*g_n(n))\n",
    "plt.show()\n",
    "\n",
    "b = 3\n",
    "n_b = int(np.ceil(np.max(np.concatenate((roots, (1+1/b)*roots)))))\n",
    "print(n_b, p_n(n_b, roots, const = C) <= c_b*p_n(n_b, roots, const = C))"
   ]
  }
 ],
 "metadata": {
  "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}