{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "16c84c83",
   "metadata": {},
   "source": [
    "[Home](Home.ipynb)\n",
    "\n",
    "# Example Study Sheet:  Sigma Notation\n",
    "\n",
    "This student is grappling with Sigma notation i.e. notation that might be understood in terms of a computer language, with a looping construct.  Most languages have that, including Python.\n",
    "\n",
    "A first place where \"summing terms\" comes up is in deconstructing ordinary integers into expressions using a \"base\" to some power, the power coming from the \"place value\" of a digit.\n",
    "\n",
    "For example, the number $12345$ represents:\n",
    "\n",
    "$$\n",
    "1(10^{4}) + 2(10^{3}) + 3(10^{2}) + 4(10^{1}) + 5(10^{0})\n",
    "$$\n",
    "\n",
    "The same number in base 3 is $121221020$ because:\n",
    "\n",
    "$$\n",
    "1(3^{8}) + 2(3^{7}) + 1(3^{6}) + 2(3^{5}) + 2(3^{4}) + 1(3^{3}) + 2(3^{1})\n",
    "$$\n",
    "\n",
    "is the number in question."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eb3ee6e0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12345"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('121221020', 3)  # convert to base 10 int from any base"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ae4ab1c",
   "metadata": {},
   "source": [
    "Lets take those terms in the form of a list of tuples, and add them up.  Each term $(c, d)$ is evaluated with respect to a given base b as: $c(b^{d})$.  For example $(2, 7)$ gives $2(3^{7})$ and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6ed4dd72",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12345"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terms = [(1, 8), (2, 7), (1, 6), (2, 5), (2, 4), (1, 3), (2, 1)]\n",
    "total = 0\n",
    "base  = 3\n",
    "for t in terms:\n",
    "    coeff, degree = t  # unpacking assignment\n",
    "    total += coeff * base ** degree  # running total\n",
    "total"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40fa4fce",
   "metadata": {},
   "source": [
    "In Jupyter Markdown, we can represent Sigma using $\\LaTeX$:\n",
    "\n",
    "$$\n",
    "\\sum\\limits_{i=1}^n i^2 = \\frac{n(n+1)(2n+1)}{6}\n",
    "$$\n",
    "\n",
    "The ```Sigma``` function below is meant to be very generic, meaning as long as the single variable, the index, is sufficient to drive the output of successive terms, we're free to provide the corresponding [callable object](Internals.ipynb).\n",
    "\n",
    "For example, the expression ```lambda x: 1/x**2``` is callable and may be passed directly as the last argument to ```Sigma```.\n",
    "\n",
    "Or maybe we just use the index to lookup a term in a sequence, where the values were computed earlier and simply stored in order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "951c405a",
   "metadata": {},
   "outputs": [],
   "source": [
    "base = 3\n",
    "def get_term(i):\n",
    "    c, d = terms[i]  # terms already specified above\n",
    "    return c * base**d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f6a3d1bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6561"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_term(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d3f0dc6f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4374"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_term(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18e6e41d",
   "metadata": {},
   "source": [
    "Capitalizing the name of a Python function is a slight break with style conventions (see PEP 8).  However, the allusion here is to the ```\\Sigma``` in $\\LaTeX$. \n",
    "\n",
    "To get the uppercase Greek sigma in $\\LaTeX$, we spell it with a capital S.  Otherwise we get $\\sigma$ i.e. the lowercase Greek sigma."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5eaf33a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Sigma(start, stop, any_callable):\n",
    "    total = 0\n",
    "    for i in range(start, stop+1):\n",
    "        total += any_callable(i) # running total\n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18b963c4",
   "metadata": {},
   "source": [
    "The key to this function is ```any_callable``` meaning some object that \"eats\" the index and comes back with each successive term to be summed.\n",
    "\n",
    "A \"lambda expression\" defines a callable object as a one liner, without the need for a specific name (other than lambda)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3ddc3376",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6349839001848923"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sigma(1, 100, lambda x: 1/x**2) # sum 1/1 + 1/4 + 1/9 + 1/16... 1/100**2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "400ed9bd",
   "metadata": {},
   "source": [
    "Lets sum these earlier terms, given our original list, and using term (above) for any_callable:\n",
    "\n",
    "$$\n",
    "1(3^{8}) + 2(3^{7}) + 1(3^{6}) + 2(3^{5}) + 2(3^{4}) + 1(3^{3}) + 2(3^{1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "25b5352b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 8), (2, 7), (1, 6), (2, 5), (2, 4), (1, 3), (2, 1)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "cced797b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12345"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sigma(0, len(terms)-1, get_term) # start indexing from 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8ae9080",
   "metadata": {},
   "source": [
    "Another function we commonly see with ```lambda```, is ```map```. The map function applies a callable (first argument) to an iterable (second argument).\n",
    "\n",
    "In the example below, ```map``` gets used to derive some reciprocals in floating point form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "79295a8d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0, 0.5, 0.3333333333333333, 0.25, 0.2]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results = map(lambda x: 1/x, [1,2,3,4,5])\n",
    "list(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e366c2dc",
   "metadata": {},
   "source": [
    "#### Number Types\n",
    "\n",
    "We've looked and integers, and floating point numbers.\n",
    "\n",
    "Python lets us fuel the very same expressions with entirely different number types. \n",
    "\n",
    "For example, consider the Fraction type, here renamed Q, a letter commonly reserved for \"rational numbers\" i.e. \"ratios\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f4ba0e3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from fractions import Fraction as Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "17e6ff36",
   "metadata": {},
   "outputs": [],
   "source": [
    "the_sum = Sigma(1, 100, lambda x: Q(1, x**2)) # 1/x**2 as p/q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "57a7d353",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(1589508694133037873112297928517553859702383498543709859889432834803818131090369901, 972186144434381030589657976672623144161975583995746241782720354705517986165248000)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "the_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e99b1ef",
   "metadata": {},
   "source": [
    "We can always ask for the type of a number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f99d42d5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fractions.Fraction"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(the_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "2b4a0df2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.634983900184893"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "the_sum.numerator / the_sum.denominator  # same floating point answer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e420e1c",
   "metadata": {},
   "source": [
    "Note again how Python, and many computer languages, keep us thinking about types.  What type of number is involved in this computation?  \n",
    "\n",
    "The types used in conventional mathematics, such as Complex $\\mathbb{C}$, Real $\\mathbb{R}$, Rational $\\mathbb{Q}$, Integer $\\mathbb{Z}$, are similar but not identical to types implemented on computers.\n",
    "\n",
    "At the core of high school math is this notion of number types or sets, one within the other, with the progression through history being one of zooming back to see more encompassing sets.\n",
    "\n",
    "$$\n",
    "\\mathbb{Z} \\subset \\mathbb{Q} \\subset \\mathbb{R} \\subset \\mathbb{C}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "63506cc5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "float"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(1.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7891846c",
   "metadata": {},
   "source": [
    "The next number type we might test (after floats and Fractions), is the Decimal, which will allow us many more digits of precision.  We get to control with how much precision.  Default is 28 decimal digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "17f1cc03",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('1.64493396684823143647224849997935852288561656787346272344984394368905508945081916387691894393511335065864850694102516943852898129313846975027616798370227948688271259286100885516014659310032065086035182526395505636922550739754025892072461567010678770311619139305575053916476189039505623978859292825156')"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from decimal import Decimal, localcontext\n",
    "with localcontext() as ctx:\n",
    "    ctx.prec = 300\n",
    "    the_sum = Sigma(1, 10000000, lambda x: 1/Decimal(x)**2)\n",
    "the_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7953b8f2",
   "metadata": {},
   "source": [
    "We don't have to use lambda expressions.  What's done to x, to compute the term, may be more than we can comfortably fit in a one-liner.\n",
    "\n",
    "Now our student does more background research on this specific sequence.  Does it converge and, if yes, to what?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "4e1deded",
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "40798de7",
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'YouTubeVideo' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/wx/nkbzr8d11f9ds5v7xb9bnbgc0000gn/T/ipykernel_15906/2064056416.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mYouTubeVideo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"9euTxoCC8Hk\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'YouTubeVideo' is not defined"
     ]
    }
   ],
   "source": [
    "YouTubeVideo(\"9euTxoCC8Hk\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e8ac7b77",
   "metadata": {},
   "outputs": [],
   "source": [
    "YouTubeVideo(\"yPl64xi_ZZA\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "189edeeb",
   "metadata": {},
   "source": [
    "So, we have learned that:\n",
    "\n",
    "$$\n",
    "\\sum\\limits_{i=1}^\\infty 1/i^2 = \\pi^{2}/6\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "409d10ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('1.644934066848226436472415167')"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi = Decimal('3.1415926535897932384626433832795028841971693993751')\n",
    "pi**2/6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "531ab604",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('1.64493396684823143647224849997935852288561656787346272344984394368905508945081916387691894393511335065864850694102516943852898129313846975027616798370227948688271259286100885516014659310032065086035182526395505636922550739754025892072461567010678770311619139305575053916476189039505623978859292825156')"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "the_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b75e1942",
   "metadata": {},
   "source": [
    "Lets verify the identity we showcased up top:\n",
    "\n",
    "$$\n",
    "\\sum\\limits_{i=1}^n i^2 = \\frac{n(n+1)(2n+1)}{6}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "c60d2160",
   "metadata": {},
   "outputs": [],
   "source": [
    "def right_side(n):\n",
    "    return n*(n+1)*(2*n + 1)//6\n",
    "\n",
    "def left_side(n):\n",
    "    return Sigma(1, n, lambda x: x**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "4b885bb3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "right_side(100) == left_side(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "0c1c1e7c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "right_side(1) == left_side(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "84e56e62",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "right_side(12345) == left_side(12345)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edef0106",
   "metadata": {},
   "source": [
    "This identity may be associated with a spatial ball packing pattern:  1 at the apex, 4 underpinning, 9 under that, and so on; a growing half-octahedron of balls.  What is the cumulative number of balls in a 10 layer arrangement?\n",
    "\n",
    "Lets look at the sequence of successively larger half-octahedra packings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "9f580ac3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 14, 30, 55, 91, 140, 204, 285, 385]\n"
     ]
    }
   ],
   "source": [
    "print([Sigma(1, n, lambda x: x**2) for n in range(1, 11)])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cbd1dfa",
   "metadata": {},
   "source": [
    "Lets compare those numbers with what ```right_side``` would give us for the same n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "bd3ca197",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5, 14, 30, 55, 91, 140, 204, 285, 385]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(right_side, range(1, 11)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ac907c2",
   "metadata": {},
   "source": [
    "What's that sequence in OEIS?  The square-pyramidal numbers, [A000330](https://oeis.org/A000330)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efcdf17d",
   "metadata": {},
   "source": [
    "$\\Sigma$ is used for adding all the terms.  Suppose we want to multiply them all together instead, is there a Greek letter for that too?  You betcha.\n",
    "\n",
    "$$\n",
    "\\prod\\limits_{i=1}^n x = x!\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f966690",
   "metadata": {},
   "source": [
    "Since Σ is a codepoint in Unicode, might we use Σ for our Python function name?  Lets try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "590c8986",
   "metadata": {},
   "outputs": [],
   "source": [
    "Σ = Sigma  # make a synonym"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "90fb020b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Σ(1, 10, lambda x: x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b45bc9ec",
   "metadata": {},
   "source": [
    "Wow, we can!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a48d940",
   "metadata": {},
   "source": [
    "Sigma Notation is often used to express infinite sums, meaning there's no defined end to the number of terms, and \"at the limit\" i.e. as we approach infinity, we may converge to a very specific number.\n",
    "\n",
    "A lot of mathematics, including high school mathematics, if focused on these finite and infinite sums.  Sigma Notation comes in handy.  However you may also wish to write some analogous Python."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}