{ "cells": [ { "cell_type": "markdown", "id": "f5ee91d5-c2e4-4fdd-8041-3352a2d91151", "metadata": { "tags": [] }, "source": [ "##### Algorithms and Data Structures (Winter - Spring 2022)\n", "\n", "* [Table of Contents](ADS_TOC.ipynb)\n", "* \"Open\n", "* [![nbviewer](https://raw.githubusercontent.com/jupyter/design/master/logos/Badges/nbviewer_badge.svg)](https://nbviewer.org/github/4dsolutions/elite_school/blob/master/ADS_intro_2.ipynb)\n", "\n", "# Choosing Algorithms\n", "\n", "You know from your own experience that some ways of accomplishing a task may take a lot longer than others. Going more slowly may have its advantages, as in real life we're accomplishing multiple tasks and have to weigh trade-offs.\n", "\n", "For example, you could wolf your dinner in a hurry, and if the only objective were to eat and run, this could be appropriate. However dinner may be an important social occasion and eating quickly and leaving the table only deprives one of catching up on important developments.\n", "\n", "A first question, when faced with a computing challenge, is whether there's a solution at all. The second question is whether this solution is at all practical in terms of time and resources. A third question is how much original work will be required on your part, and how long might that take.\n", "\n", "The first question involves research and not reinventing the wheel. If people stopped to reinvent every algorithm from scratch, we would move forward much too slowly. Everyone would need the same insights and genius as everyone else we we know the world is not like that. \n", "\n", "Competitive Programming and Coding Interviews are not usually asking for acts of genius, as these do not come on demand, regardless of practice.\n", "\n", "On the other hand, simply grabbing a published algorithm from a book without having much insight into how the algorithm actually works, or why, may lead to its own host of troubles down the road. \n", "\n", "Not really understanding how an algorithm works should not prevent you from using it though. In computing, we learn to treat some elements of our system as \"black boxes\" meaning we have no insight into the internals, but may use them anyway. If this seems like a dark ages approach, with its reliance on \"magic spells\" so be it. The wizards and witches of the UNIX era earned that reputation for a reason. Not everyone could read a regex.\n", "\n", "The second question (how long?) involves understanding what's called \"Big O notation\" which looks something like $O(n^{2})$ or $O(n\\ log(n))$. Big O notation is about roughly how long an algorithm will likely take to find a solution, and is pegged to some input \"n\" of growing dimension. \n", "\n", "\"usaco_guide\"\n", "\n", "From: *Competitive Programmer’s Handbook, Antti Laaksonen, Draft, August 19, 2019* ([link to PDF](https://usaco.guide/CPH.pdf))\n", "\n", "For example, n might be the number of digits in a number, and you want to know if the number is prime, or its prime factors. Many off-the-self algorithms address these very questions." ] }, { "cell_type": "code", "execution_count": 2, "id": "36e82d9d-308d-4438-a144-ad92ec79fbc4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from primes import isprime, factors, all_factors\n", "\n", "isprime(23321)" ] }, { "cell_type": "code", "execution_count": 2, "id": "0c78ce41-db44-4760-8601-9b0761235898", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_factors(2)" ] }, { "cell_type": "code", "execution_count": 3, "id": "27a6573b-945c-4bfa-9de7-da46cebab157", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 2, 11, 11, 19997)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factors(4839274) # this version includes 1 as a factor..." ] }, { "cell_type": "markdown", "id": "8aa4f64b-795f-4886-81be-2fabbc3a3a20", "metadata": {}, "source": [ "The cell below typifies what you will need if hacking on a module in the background and then testing it here in Jupyter Notebook. If you're not changing the underlying code, you need not force recompilation." ] }, { "cell_type": "code", "execution_count": 4, "id": "f8db8bd0-7212-47bb-af95-a74fdf807bc0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from imp import reload\n", "import primes.primesplay\n", "reload(primes.primesplay)" ] }, { "cell_type": "code", "execution_count": 5, "id": "07ead4fe-9dcd-42f5-8836-4cb821da9616", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 2, 2, 3)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factors(12) # but not the number itself" ] }, { "cell_type": "code", "execution_count": 6, "id": "2ab3c77a-d304-4acf-8bed-0ad8c36e757c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 7, 11, 11, 13, 13)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factors(11 * 11 * 13 * 13 * 7)" ] }, { "cell_type": "code", "execution_count": 7, "id": "5f9c173b-7329-49db-85d2-d42f4f51457c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "360" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# what factors() returns should multiply together giving\n", "# the original number\n", "from functools import reduce\n", "from operator import mul\n", "\n", "f = factors(360) # list of factors\n", "reduce(mul, f) # multiply all fs together" ] }, { "cell_type": "code", "execution_count": 8, "id": "79fc335a-32b8-4742-b2a8-f1a4aa9764b4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 6, 12]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_factors(12)" ] }, { "cell_type": "code", "execution_count": 9, "id": "d26a4958-0d33-40bb-b292-de06d7866587", "metadata": {}, "outputs": [], "source": [ "def proper_divisors(n):\n", " return [f for f in all_factors(n)][:-1]" ] }, { "cell_type": "code", "execution_count": 10, "id": "b5c43a04-0bb7-4e7a-8413-12e1d1afabd7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 4, 7, 14]\n" ] } ], "source": [ "print(proper_divisors(28))" ] }, { "cell_type": "code", "execution_count": 11, "id": "e2a554a3-a560-4e06-97ac-76e92ec48ea5", "metadata": {}, "outputs": [], "source": [ "def aliquot_sum(n):\n", " return sum(proper_divisors(n))" ] }, { "cell_type": "code", "execution_count": 12, "id": "58e2095a-245b-4f58-af10-e22ed15070a8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1]\n" ] } ], "source": [ "print([aliquot_sum(x) for x in range(1, 30)])" ] }, { "cell_type": "code", "execution_count": 13, "id": "0ac00356-4206-43bb-be90-9251dc5e9c39", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "28" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "aliquot_sum(28) # perfect number" ] }, { "cell_type": "markdown", "id": "a8769999-31da-4000-9d9b-9876164030bf", "metadata": {}, "source": [ "Or n is the number of points floating in XYZ space and you wish to generate the biggest convex polyhedron that could contain all of them, either as corners, or internally. An open source program named Qhull will do this for you.\n", "\n", "If a measure of the algorithm's efficiency is something like $O(n!)$, that means the time needed grows very quickly as n gets bigger. Often times we say an algorithm takes \"polynomial time\" and usually that means the algorithm is impractical for large values of n. But how large is too large?\n", "\n", "If the efficency is more like $O(n)$, we say the time increases \"linearly with n\" which is about as good as it gets, although $O(log(n))$ is even better. Actually $O(1)$ is maximal and might be said to mean \"instantaneous, regardless of size\". \"Just giving it a name\" (e.g. bigdata = BigPile) is perhaps such an operation, but may not get us very far.\n", "\n", "For example the amount of time it takes to scan a list for a specific value tends to increase linearly with the length of the list. A list 10 times longer, takes an average of 10 times longer to search. Looking up a value by key in a dict, however, takes about the same amount of time no matter what.\n", "\n", "

Remember #Python sets and dicts use a hash table internally which makes them very fast - algorithmic complexity of O(1) - for lookups (e.g. using the "in" operator).

— Bob Belderbos (@bbelderbos) February 15, 2022
\n", "\n", "# Inventing Algorithms\n", "\n", "Sometimes you might find exactly the algorithm you need, including in the computer language of your choice. You may need to customize it a little, to fit into your larger project, but that's a minor detail.\n", "\n", "Other times, you may need to invent your own algorithms. You might want to do this anyway, because you see a clear way to accomplish a task and feel relying on others might take more time. You might elect to devise your own solution for many reasons, including because you're in school learning how to write algorithms.\n", "\n", "One technique involved in writing your own solution is [writing tests](ADS_sandbox_8.ipynb) for that solution. \n", "\n", "How will you know your solution is correct? This often requires having an independent and trusted source of \"right answers\" such as the digits of pi (if you're trying to generate them) or a list of consecutive prime numbers (if you're trying to generate primes).\n", "\n", "On the other hand, perhaps you algorithm is mathematically provable (many of them are, see below), meaning you're able to offer it with great confidance in its correctness, irrespective of implementation details.\n", "\n", "Speaking of generating prime numbers, the Sieve of Eratosthenes is a great example of an ancient algorithm, passed down through the ages. See Notes." ] }, { "cell_type": "code", "execution_count": 14, "id": "86aeb2b0-5705-41a1-a4f5-92057b16b7f7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n" ] } ], "source": [ "from primes import eratosthenes\n", "print(eratosthenes(100)) # all primes <= 100" ] }, { "cell_type": "markdown", "id": "9ecba7af-336d-4909-afc4-ab1bd5ef3b4d", "metadata": {}, "source": [ "For example, in the case of [our Wordle-like project](ADS_project_1.ipynb), evaluating a guess versus a right answer, coming up with the correct feedback, is something one can do manually, without a computer, once the rules of the game are understood. If your algorithm matches all the results you know are correct, having derived them yourself, then that's evidence you're making progress." ] }, { "cell_type": "markdown", "id": "c4c25729-adc5-49c7-8cc4-e640d896e026", "metadata": {}, "source": [ "# Proving Algorithms\n", "\n", "More valuable than tests, or at least complementary to tests, would be some kind of mathematical proof that the algorithm is in fact correct. \n", "\n", "Some algorithms may produce \"false positives\" or \"false negatives\". For example, the Fermat Primality test may falsely flag a composite as prime, but it will never falsely flag a prime as composite.\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "f9b3f5e2-b7b9-45fb-b8ae-0e78876ebd9f", "metadata": {}, "outputs": [], "source": [ "from math import gcd\n", "\n", "def fermat_test(n, base=2):\n", " if gcd(n, base) > 1: # n is composite\n", " return False\n", " if pow(base, n-1, n) == 1:\n", " return True # pass\n", " else:\n", " return False # no pass\n", " \n", "def fermat(n):\n", " bases = [2, 3, 5, 7, 11]\n", " if 5 == sum([fermat_test(n, b) for b in bases]):\n", " return True\n", " return False" ] }, { "cell_type": "markdown", "id": "e19bfddb-ebec-48d9-b15c-5806d8b8eb12", "metadata": {}, "source": [ "Although [Li Shanlan](https://en.wikipedia.org/wiki/Li_Shanlan) (1811–1882), a Qing dynasty mathematician, later realized his error in claiming any odd n prime if and only if $2^{n-1} \\equiv 1 \\pmod n$, it was too late: [the so-called \"Chinese Hypothesis\"](https://en.wikipedia.org/wiki/Chinese_hypothesis) had made it into the literature.\n", "\n", "We can see why this conjecture was tempting:" ] }, { "cell_type": "code", "execution_count": 16, "id": "6e4a414f-fd85-42f6-bf1e-47cde33a1ba6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]\n" ] } ], "source": [ "shanlan = [n for n in range(1, 300) if fermat_test(n) ]\n", "print(shanlan)" ] }, { "cell_type": "code", "execution_count": 17, "id": "72350d8b-6816-42d2-85cf-c466fbf4a26b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sifted = eratosthenes(300)\n", "sifted[1:] == shanlan # but for 2 itself" ] }, { "cell_type": "code", "execution_count": 18, "id": "c061a8eb-ccd3-4f54-abfc-9b07eb26b008", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]\n" ] } ], "source": [ "shanlan = [ n for n in range(3, 301, 2) if fermat_test(n)]\n", "print(shanlan)" ] }, { "cell_type": "code", "execution_count": 19, "id": "b74926bd-3bb0-486c-b12b-8af84074d443", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fermat_test(341) # however..." ] }, { "cell_type": "markdown", "id": "3ff5d334-ddde-4908-8ff6-fde9bc89f7f8", "metadata": {}, "source": [ "[Dr. Sarrus](https://en.wikipedia.org/wiki/Pierre_Fr%C3%A9d%C3%A9ric_Sarrus) (1798 - 1861) discovered 341 was the first (lowest) exception to this rule, and [Sarrus pseudoprimes](https://oeis.org/A001567) are Fermat pseudoprimes that pass with base 2. \n", "\n", "[A Fermat pseudoprime](https://en.wikipedia.org/wiki/Fermat_pseudoprime) passes the Fermat test for some relatively prime base, and yet is not prime. Mathematicians know such Fermat pseudoprimes exist for any base and have recipes for creating them. \n", "\n", "The [Carmichael Numbers](https://oeis.org/A002997) pass the Fermat Test for all bases to which they are relatively prime." ] }, { "cell_type": "code", "execution_count": 21, "id": "b79ee3f4-f644-414f-a267-447495e605fc", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 11, 31)" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factors(341)" ] }, { "cell_type": "markdown", "id": "23426af4-d2a5-4624-a124-7e63f583c3b2", "metadata": {}, "source": [ "One way to strengthen the Fermat Test is to apply several bases. The mere fact of checking for relative primality weeds out a lot of false positives." ] }, { "cell_type": "code", "execution_count": 23, "id": "de639b65-8fa7-4669-a0fe-6e5b701622f8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fermat(1729)" ] }, { "cell_type": "markdown", "id": "a0f86300-388c-43e1-a5d2-955c93780a5c", "metadata": {}, "source": [ "The algorithms below are too slow for use with big numbers, but have the advantage of being conceptually clear, and so good for nailing down concepts ahead of time." ] }, { "cell_type": "code", "execution_count": 25, "id": "c624b328-2965-4f05-9965-7757c8feca0f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 7, 13, 19)" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factors(1729)" ] }, { "cell_type": "code", "execution_count": 26, "id": "df3ee9e9-20f9-45a5-a9de-99e5663e88a2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fermat(561) # Carmichael Number, not really prime" ] }, { "cell_type": "markdown", "id": "5a6cb18a-23b3-4460-85d7-a90ad4ea864e", "metadata": {}, "source": [ "Along with proving and testing comes assessing the algorithm's efficiency (see above). As the inventor of the algorithm, it's up to you to get a sense of what its Big-O signature might be. \n", "\n", "If you plan to publish your algorithm as a useful invention available to a wider public, such an analysis may be expected of you.\n", "\n", "A lot of deep computer science has gone into figuring out how to prove whether a program is correct. In practice, one often can provide a proof, to everyone's satisfaction. However in theory, there's no guaranteed strategy for proving a program is bullet proof. \n", "\n", "At this general a level we're talking about the fabric of logic itself, and logicians had already come to similar conclusions, about the generic incompleteness of proof-based systems, even before computer scientists raised the issue of provability." ] }, { "cell_type": "code", "execution_count": 28, "id": "2791983e-0628-4de7-bd0a-48f941a6084a", "metadata": {}, "outputs": [], "source": [ "from math import gcd\n", "\n", "def isprime(n): # slow, inefficient, but clear\n", " return (True \n", " if sum([gcd(n,i) for i in range(1, n)])==(n-1) \n", " else False)" ] }, { "cell_type": "code", "execution_count": 29, "id": "90cbb468-2bc2-47ac-9be4-135cbbe71dc4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isprime(13)" ] }, { "cell_type": "code", "execution_count": 30, "id": "04c7bc40-6cac-44b2-9a5a-0f605ae71b70", "metadata": {}, "outputs": [], "source": [ "def primes(n):\n", " output = []\n", " for i in range(2, n):\n", " if isprime(i):\n", " output.append(i)\n", " return output" ] }, { "cell_type": "markdown", "id": "90a992f1-a5b1-4e92-9998-12e6cfd6bbb2", "metadata": {}, "source": [ "# One of the Oldest Algorithms\n", "\n", "One of the oldest algorithms that's been passed down through the ages is known as Euclid's Algorithm. Whether Euclid invented it is not the key question. The method was included among Euclid's published techniques.\n", "\n", "The purpose of Euclid's Algorithm (EA) is to find the biggest number that will divide two other numbers. We're talking about positive integers and a unit, such that if EA(a, b) is 1, then a/b is already a fraction in lowest terms.\n", "\n", "For example, EA(24, 16) is 8, because 8 is the largest integer, the greatest common divisor, of both 24 and 16. 2 is also a divisor, but isn't the greatest. If you came across the fraction 16/24, you would know you might reduce it to 2/3, and at that point, there's no further reduction possible. gcd(2, 3) = 1. When the numerator and denominator are relatively prime (e.g. 14/23), have no factors in common, then we say it's in \"lowest terms\".\n", "\n", "When computing the gcd of a pair of numbers, sometimes one of the numbers is already a divisor of the other, in which case that's the answer. The gcd of 10 and 5 is simply 5.\n", "\n", "The implementation of a \"greatest common divisor\" solution below is *not* Euclid's Method, but a relatively inefficent method that is nevertheless not hard to understand.\n", "\n", "Get all the divisors of input numbers j and k, then get the greatest divisor they both have in common." ] }, { "cell_type": "code", "execution_count": 32, "id": "1d4e03a5-d14e-4e58-859e-cec4d69f908a", "metadata": {}, "outputs": [], "source": [ "def divisors(n : int):\n", " divs = list()\n", " for d in range(1, n + 1):\n", " if n % d == 0:\n", " divs.append(d)\n", " return divs " ] }, { "cell_type": "code", "execution_count": 33, "id": "9bbea0b0-2227-4c25-9249-9f1d439c41cd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 6, 12]" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_factors(12)" ] }, { "cell_type": "code", "execution_count": 34, "id": "07a4d495-b277-4725-b134-ea46b2704644", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 6, 9, 12, 18, 36]" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_factors(36)" ] }, { "cell_type": "code", "execution_count": 35, "id": "a73a650a-2521-4a2c-954f-7f6be101c5c9", "metadata": {}, "outputs": [], "source": [ "def gcd(a, b):\n", " return max(set(all_factors(a)).intersection(set(all_factors(b))))" ] }, { "cell_type": "code", "execution_count": 37, "id": "8725357f-7bc6-43d0-ba6a-e92648d2e462", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gcd(24, 10)" ] }, { "cell_type": "code", "execution_count": 38, "id": "09be6409-8c1c-4ae3-aa36-c3191d30c6dd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gcd(19, 21)" ] }, { "cell_type": "code", "execution_count": 39, "id": "490a0f4d-764d-4f0d-ba57-8997e143c53e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "35" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gcd(10045, 4095)" ] }, { "cell_type": "markdown", "id": "7c9edbca-5f0d-4012-a2a5-06e897644627", "metadata": {}, "source": [ "This works!\n", "\n", "However, Euclid's Method (another name for Euclid's Algorithm) is much cleverer. \n", "\n", "Consider our two inputs to be m and n. If the smaller m divides the larger n with no remainder, we're done: m is the greatest divisor. \n", "\n", "It could be that m is down to 1 at this point (see below), in which case the original n and m were \"strangers\" to one another, meaning their only factor in common was the number 1. We could also say they were \"relatively prime\"." ] }, { "cell_type": "code", "execution_count": 40, "id": "b98ee8aa-5517-42d2-a2eb-8fe647723286", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from math import gcd\n", "\n", "gcd(19, 101) # both prime" ] }, { "cell_type": "code", "execution_count": 41, "id": "dcfd3f43-4057-43e9-afcf-eb158d15bc7b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gcd(18, 13) # relatively prime (strangers)" ] }, { "cell_type": "markdown", "id": "79f6afdf-aa89-42ed-849d-28247d25daf1", "metadata": {}, "source": [ "Otherwise, if m is not 1, and there's some remainder r after dividing n by m, then the next step is to find the greatest divisor of m and r. Whatever divides both will also divide n, the longer starting length. \n", "\n", "And so on, we keep going. The n, m pair keeps getting smaller as we keep taking the remainder from the previous pair. Down to m = 1 at the limit, but we don't necessarily get to that. Whenever m divides n, we're done.\n", "\n", "Here's a first attempt at implementing the above:" ] }, { "cell_type": "code", "execution_count": 42, "id": "2922e07e-02db-4eac-9194-906e248c5fe3", "metadata": {}, "outputs": [], "source": [ "def EA(m, n):\n", " if m > n:\n", " m, n = n, m # make m the smaller\n", " while True:\n", " q = n // m # get quotient\n", " if q * m == n: # if no remainder, done\n", " return m\n", " n, m = m, n - q*m # m, r -- the new terms" ] }, { "cell_type": "code", "execution_count": 43, "id": "abf540ed-8fb3-4e00-b250-10b57075f1f4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EA(12, 100)" ] }, { "cell_type": "code", "execution_count": 44, "id": "4293e75b-53e7-4778-bebd-c9ec9c8337b0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "35" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EA(10045, 4095)" ] }, { "cell_type": "code", "execution_count": 45, "id": "c505053e-de02-44a8-8c6f-2dabf9465586", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "761 ns ± 304 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n" ] } ], "source": [ "%timeit gcd(4839274, 639232)" ] }, { "cell_type": "code", "execution_count": 46, "id": "4afadd53-99c4-4f7f-aba4-515f1f56e63c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5.1 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit EA(4839274, 639232)" ] }, { "cell_type": "markdown", "id": "b36441bc-3990-48df-909d-ff999cfe2eec", "metadata": {}, "source": [ "EA is hugely more efficient compared to the all-divisors based algorithm, taking only micro-seconds versus milliseconds. \n", "\n", "EA does not require finding all the divisors of any number. EA eventually comes to an end, with an answer if 1, so there's no danger the ```while True``` loop will be infinite.\n", "\n", "Speaking of loops, here's another implementation of EA employing recursion:" ] }, { "cell_type": "code", "execution_count": 47, "id": "ac8cdf2c-97e7-454d-a2d4-16019da1e675", "metadata": {}, "outputs": [], "source": [ "def EA(m, n):\n", " if m > n:\n", " m, n = n, m # make m the smaller\n", " r = n % m # remainder\n", " if r == 0: # if no remainder, done\n", " return m\n", " return EA(m, r)" ] }, { "cell_type": "code", "execution_count": 48, "id": "1c49e2b7-2baa-4246-bd4f-b829c84d5497", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5.55 µs ± 823 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit EA(4839274, 639232)" ] }, { "cell_type": "markdown", "id": "0f8265cb-9d9b-4cc9-aa12-6db51f0c51e3", "metadata": {}, "source": [ "The pithiest (most Pythonic) implementation of EA is attributed to Guido van Rossum, Python's inventor. \n", "\n", "Here it is:" ] }, { "cell_type": "code", "execution_count": 49, "id": "0b493429-80cc-47f4-9ba3-96ed9e798865", "metadata": {}, "outputs": [], "source": [ "def EA(m, n):\n", " while m:\n", " n, m = m, n % m\n", " return n" ] }, { "cell_type": "code", "execution_count": 50, "id": "2e52dcdc-cd9d-4ebe-a2d7-6f85cef71b3e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EA(12, 100)" ] }, { "cell_type": "code", "execution_count": 51, "id": "dc97e5f9-1518-40b2-8273-b8114b2f269d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1.74 µs ± 306 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit EA(4839274, 639232)" ] }, { "cell_type": "markdown", "id": "d1c1fd12-e0bf-40e7-adfc-c1e9c159f64b", "metadata": {}, "source": [ "### Lowest Common Multiple\n", "\n", "One way to get the Lowest Common Multiple of two numbers, m and n is to get their product, but then to divide by the GCD." ] }, { "cell_type": "code", "execution_count": 52, "id": "d9231598-e758-476b-ac7d-9057e0681da7", "metadata": {}, "outputs": [], "source": [ "def lcm(a, b):\n", " return (a * b) // gcd(a, b)" ] }, { "cell_type": "code", "execution_count": 53, "id": "ce71d2e5-2b0d-40e4-85d1-041cd29b7deb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "216" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lcm(27, 72)" ] }, { "cell_type": "markdown", "id": "980b11ee-0c08-45ba-94a4-9bfaea6799a3", "metadata": {}, "source": [ "### The Extended Euclidean Algorithm\n", "\n", "Once we have the GCD of two numbers, m, n, we should be able to stack these two lengths side-by-side such that the two stacks differ only by the GCD itself. How many bricks of each length will we need? That's what the Extended Euclidean Algorithm (EEA) will tell us.\n", "\n", "This puzzle piece proves useful when we introduce RSA, the public key cryptography algorithm. Follow the 2nd link below for more information. " ] }, { "cell_type": "code", "execution_count": 54, "id": "bb52f983-7e08-477a-9eac-4e91dcdbe971", "metadata": {}, "outputs": [], "source": [ "from primes.euler_test import xgcd" ] }, { "cell_type": "code", "execution_count": 55, "id": "cb5f559d-6b4d-4ed9-87f6-85058968077d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9 -3 5\n" ] } ], "source": [ "m, n = 117, 72\n", "g, a, b = xgcd(m, n)\n", "print(g, a, b)" ] }, { "cell_type": "code", "execution_count": 56, "id": "e246a511-a075-4709-a1c5-fedbc0f93c0b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * m + b * n" ] }, { "cell_type": "markdown", "id": "133053f3-d819-47cc-b9bf-84e9559c84ff", "metadata": {}, "source": [ "#### Links:\n", "\n", "\n", "[Link to source code](./primes.primesplay.py) for the Seive of Eratosthenes, factors, isprime and so on.\n", "\n", "[Extended Euclidean Algorithm](EEA.ipynb)" ] }, { "cell_type": "markdown", "id": "4f47cbcf-9896-4cd7-bcba-669ac40cf0c7", "metadata": {}, "source": [ "# Cumulative Sequences\n", "\n", "Suppose you have a sequence such as the Fibonacci numbers, and for some reason want a cumulative total of all the numbers in a sequence up to a specific term. In fact, you would like a cumulative total to go with every term in the original sequence.\n", "\n", "Like this:" ] }, { "cell_type": "code", "execution_count": 57, "id": "90c3c230-cc6f-4f49-9bc1-ca74639a055d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]\n" ] } ], "source": [ "# Fibonacci Numbers\n", "# https://oeis.org/A000045\n", "\n", "def fibo(a=0, b=1):\n", " while True:\n", " yield a\n", " b, a = a + b, b\n", " \n", "gen = fibo()\n", "fibs = [next(gen) for _ in range(10)]\n", "print(fibs)" ] }, { "cell_type": "code", "execution_count": 58, "id": "625261ab-0ba1-4a6b-89aa-85c2b5b90f0a", "metadata": {}, "outputs": [], "source": [ "def accumulate(seq):\n", " totals = []\n", " term = 0\n", " for i in seq:\n", " term += i\n", " totals.append(term)\n", " return totals" ] }, { "cell_type": "code", "execution_count": 59, "id": "34eef489-126c-48d8-acb2-2e743e761f57", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 4, 7, 12, 20, 33, 54, 88]" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "accumulate(fibs)" ] }, { "cell_type": "markdown", "id": "1e2d27ff-8ff6-40c7-b821-b8c55e8d28eb", "metadata": {}, "source": [ "Interestingly, the [running total of Fibonacci numbers](https://oeis.org/A000071) matches itself, minus one from each term, starting a couple terms further forward. \n", "\n", "Imagine subtracting 1 from each of these terms:" ] }, { "cell_type": "code", "execution_count": 60, "id": "3f43ec8f-a3f1-4b41-9d27-8c47623a4f5c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 5, 8, 13, 21, 34]" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fibs[2:]" ] }, { "cell_type": "markdown", "id": "3749e1e0-555e-4855-8754-46d09feb13fe", "metadata": {}, "source": [ "Now let's do it:" ] }, { "cell_type": "code", "execution_count": 61, "id": "50af803e-8b50-47c9-aa20-eb4ad49eedf2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 4, 7, 12, 20, 33]" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[fib-1 for fib in fibs[2:]]" ] }, { "cell_type": "markdown", "id": "3b1e2a2e-fa55-4ac9-9c55-0a120ccadcfc", "metadata": {}, "source": [ "Here's another sequence and its correlated cumulative sequence: the cuboctahedral numbers.\n", "\n", "![Image of Cubocta](http://www.4dsolutions.net/ocn/graphics/cubanim.gif)\n", "\n", "A way to pack (equi-sized) balls together very efficiently is in what's called the CCP arrangement, or Cubic Close Packing. The growing shape depicted above is a 14-faced (8 triangle, 6 square) \"cuboctahedron\" and it is growing outward in layers. The first layer around the nuclear ball has 12 balls. The next layer has 42. The sequence is known in the OEIS as [A005901](https://oeis.org/A005901).\n", "\n", "Lets generate it, and accumulate." ] }, { "cell_type": "code", "execution_count": 62, "id": "ae3027a0-3f58-4d0f-bf48-a4139e5e572c", "metadata": {}, "outputs": [], "source": [ "def cubocta(n : int):\n", " \"\"\"\n", " n is number of layers (0 for nuclear ball)\n", " \"\"\"\n", " if n==0: return 1\n", " return 10 * n * n + 2" ] }, { "cell_type": "code", "execution_count": 63, "id": "30ca19f7-c179-44be-a1e9-701251f7f254", "metadata": {}, "outputs": [], "source": [ "a005901 = [cubocta(i) for i in range(15)] # first 20 cuboctahedral numbers" ] }, { "cell_type": "code", "execution_count": 64, "id": "2a3cfcb7-eded-4a58-9c77-93cac5e0837d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 12, 42, 92, 162, 252, 362, 492, 642, 812, 1002, 1212, 1442, 1692, 1962]\n" ] } ], "source": [ "print(a005901)" ] }, { "cell_type": "code", "execution_count": 65, "id": "cca45d9e-82b7-40f4-8e7a-4cdc0b1f5c76", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 13, 55, 147, 309, 561, 923, 1415, 2057, 2869, 3871, 5083, 6525, 8217, 10179]\n" ] } ], "source": [ "a005902 = accumulate(a005901)\n", "print(a005902)" ] }, { "cell_type": "markdown", "id": "ce4684b0-abff-4218-8ce6-8bdcd42dcdfc", "metadata": {}, "source": [ "Now that we have done the work to implement `accumulate` lets take a look at the tool already provided in the standard library. It's in `itertools`, a goldmine of generic Python generator type objects." ] }, { "cell_type": "code", "execution_count": 66, "id": "ef7e0ec1-3dbb-4e92-83d9-393f6f06087a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 13, 55, 147, 309, 561, 923, 1415, 2057, 2869, 3871, 5083, 6525, 8217, 10179]\n" ] } ], "source": [ "from itertools import accumulate\n", "result = accumulate(a005901)\n", "print(list(result))" ] }, { "cell_type": "markdown", "id": "db8fb42a-921e-40a0-8580-b6d18d4b37c0", "metadata": {}, "source": [ "Remember `itertools` when your topic is permutations and/or combinations." ] }, { "cell_type": "markdown", "id": "ab33b292-5cb2-4e4f-93d0-4f5966c9fe47", "metadata": {}, "source": [ "## Exercise: Sequence Differences\n", "\n", "Write a function that takes a sequence and returns a sequence, of differences between successive terms.\n", "\n", "For example, ```[0, 1, 2, 4, 7, 12, 20, 33]``` would output ```[1, 1, 2, 3, 5, 8, 13]```. The resulting sequence will have one less term than the input sequence." ] }, { "cell_type": "code", "execution_count": 67, "id": "2e063345-c02d-4b53-bfd1-48e515e374cf", "metadata": {}, "outputs": [], "source": [ "from ads_solutions import diffs # secret stash of solutions? what's your solution?" ] }, { "cell_type": "code", "execution_count": 68, "id": "f5b6a662-fffa-4a18-8f2f-453494b70c0e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, 2, 3, 5, 8, 13]" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "diffs([0, 1, 2, 4, 7, 12, 20, 33])" ] }, { "cell_type": "code", "execution_count": 69, "id": "3300492b-e57c-406e-bca5-c51366c4b83b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fibs" ] }, { "cell_type": "code", "execution_count": 70, "id": "de8d9610-b588-4a6c-bdcb-8ecfbfaad8c3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 0, 1, 1, 2, 3, 5, 8, 13]\n" ] } ], "source": [ "print(diffs(fibs))" ] }, { "cell_type": "code", "execution_count": 71, "id": "8e3c75bf-1cee-4a7d-8a0f-5fb469c42078", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[12, 42, 92, 162, 252, 362, 492, 642, 812, 1002, 1212, 1442, 1692, 1962]\n" ] } ], "source": [ "print(diffs(a005902))" ] }, { "cell_type": "code", "execution_count": 72, "id": "b251b15f-8b6f-4b04-81de-4837aef14e92", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(zip([1, 2, 3, 4, 5], [2, 3, 4, 5, 6]))" ] }, { "cell_type": "code", "execution_count": 73, "id": "cf93e409-4bf2-42b4-9def-39fa0848c348", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-10, 15, -6, -1, 102]" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "diffs([0, -10, 5, -1, -2, 100])" ] }, { "cell_type": "markdown", "id": "f5e55278-43d5-49df-91af-1352a81ed312", "metadata": {}, "source": [ "# Resources\n", "\n", "* [List Comprehension Syntax](List_Comprehensions.ipynb) and related concepts\n", "\n", "* [Learning Math with Python](https://doingmathwithpython.github.io/pycon-us-2016/#/3) (slide show on Github) by the author of a book by that title, Amit Saha.\n", "\n", "* [Math Adventures with Python](https://www.amazon.com/Math-Adventures-Python-Illustrated-Exploring-ebook/dp/B074653Z4D/ref=sr_1_3?crid=1IT4OKGBJVTOZ&keywords=math+adventures+with+python&qid=1643748496&s=books&sprefix=math+adventures+with+python%2Cstripbooks%2C307&sr=1-3) by Peter Farrell, depicted below (on the left):\n", "\n", "\"Peter\n", "\n", "Lots of Python in this MIT course:" ] }, { "cell_type": "code", "execution_count": 74, "id": "159f5a92-df3c-41aa-a7cb-8eb69c0c31b2", "metadata": {}, "outputs": [ { "data": { "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkzODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQEDEQH/xAAbAAABBQEBAAAAAAAAAAAAAAAAAQIDBAUGB//EAEIQAAEDAgMEBgcGBQMFAQEAAAEAAgMEEQUSIQYxQVETFCIyYXEzcoGRobHBIzRCUmKCFTVDc9EHJGMlRJLh8fAW/8QAGAEBAQEBAQAAAAAAAAAAAAAAAAECAwT/xAAgEQEBAQACAgIDAQAAAAAAAAAAARECIRIxE0EDUWEi/9oADAMBAAIRAxEAPwDh6TvO8lZKrUned5Kwd6rNS01PJVVMcEIzSSOsAtefEIcIvR4cyOaVuks8guC7iGhUsLlNOyuqWaSQ0xyHkXENv8Ss8CwHNGXQ1NS7FKORsmS7KETOc3TK5ptb2qv0Ms+zkVPLLGwlzp4mvcBdgFjZZ9OJZYKmJjiGCIyPA3kA6rQ2gip8mGvp5C6M0TQy4tezjf4pVkRR4u5lbPVNi7T6bq8etsnZAup8Sq4qvZ1sgeOnlrGukZxBEdifLRZ9DR9Z6V739HDC3PI+24KeP+HxStzB08c7exwcx17doJbEQ1lRHPLREXyxU0cL/ME3WtXVlO/AKwUjWhkEkWQEdqxJuT7gsjEIoYcTqIKVzpIo3ZWuI1Ku09KYsJxJ03Zz04GR2+4cC0j4oNGuwKN/8PyyBtRVyhsvJl2ByiMOCzYiylYZi2GNwe9huHvvpqsZ9fVSAF0zi4PbIHcQQ3L8lHTzyU0wmhfkkvvCpY0psIp6alfLNWgvDe7FGXC/IngsqNjpHtY0Xc42A5lXKbE6pspYZWNinlvLdgsbnUqKGVtJijZWEOZDPdp5gHQoTWscFpKKFj699Q7MbEwMzBp8+Nli1LY4qmWOJxexrrNeRa452W7SQYvQwV0sjyylbG+ZkjxdrnXFrX53WPU4nPWsHTiMm29rA35LMMxUQhCoRCEIEKanFNKKFaw372PVKqq1hv3seqUHTYaf9mPWKsEqrhx/2Y9YqwSq5lO5Kmk6JwOiiFCvYcbSPHNpVC6uYd6R/qlBlgA4gwneHqLFv5NXf3Pqnt/mcf8AcTMW/k9f6/1UI5IlCCkR1KEqRLdUKlCai6B6VMulugcjeLJt0oKDW6M4nh8PR61VJH0bmcXx7wRzsmtlfRbPgQyFk9XVXNjYtYwW+Z+CZh9HUOAq+k6tEw26dxsPJW6quwmaSLpY5ZXi4kla3KHexXGfSGlNRiNDXQukL5M8UgzH8IuD8wm0FdT0tVh05ZnMTHCUHdmJNj48Fo08WGPJ6HobOFrNnIdbyT3bP0czfsTURO4XYC333Wcqap1UsVXg9YRUvqJoJ2SgluWzDoVbgdDHQYNgsoA64HTSP4szkhlvcFNBsvVUrK1/SxPikpHx3zW7Rtb4hI7D6SEQVuJzurJmRNjZT0vDLuuUXYxsKwmatlfmIip4XETSu3NsdfarOM1MdThML6VloBWOiiHHK1otfxNyU3FauvxAiIUxpqW9xDHuPiTxKTDpTSM6KtppJKQSCUBo1DxuVslNT1GDU9NNK+SozsjcAYo+046AkHksWplE1VLIxmRjnXawm9gp4KpnW6ipqg8ukcZMjDYOJO4lMqnRzRioBaySSRwMI/CNLIK5NgTyC08YjMAwqhaLmGkDyP1vJcfostwu23PRb9aGS7U4lI8FzKSG7WjiWtDQPeisE6IW4/DJKupwqlexsNU6IuqBxawHRxHOyjxbD4qbC2zxse6aSd93DdGwbgfFbvGyatY6Lq3idOyn6k6MENqKVsxvzJIPyVNYAoKnutUyhqdzUWFo+8/yVg71Xo97/JWShVqhGalxKPi6mzD9rgVUV3CC0YnCyTSOa8Lj4OFv8KCmo5H1nVHXD2uLXDlbejJkEkkTz0RsZGmM+IO8J80730tNSvAtSl4aeNib2WlR08NRPRzxwlkJrGQtJN843n5LPjo56hlRUhhELHOLnnQDXddBPh89P1Oto6mQxNqMjmSW0Bab2Pmq9e6mdUjqgPRhgB5F3GykosPNVE6V8giZfK0kXzOteypjW3irou4X0/WJOr5WuMZDpHfgbxKdiMDoKOhje/pCHSWcNz2kgj6pgwuv6LpOqzCNw35TqExlXagfRvjDmh2aMnfGePsWb5fRq7heHQVdG+pmkMcVNLaod+gi4t430WSDe5tYE6A8lpUVe6npJsPmblp6iN2Y21Lt7T7wqLIr0b5ybFj2st5g/wCFrpDA0uNmgnyCsUVI6pkc2xsI3vJtoMrbqxhBxCGQuoacSOmBjGZma/OysQ1hwfGquBpa6Eh0b2nUFxbb5lSb9DJ6xM6BsZkd0eW2W+lio10FVhpfCYXNjbUNmiYxzOyH5hqAOIHNUsTpKahqqZ8TnzUszC4XGV2hsVV3WaB8ELcgweUEVdIYqikeNW5wCByPJUq6mphRitopHdEJOjfG7Usda+/juRNUEi6CipnwYdE+koo6yrljEr87c4YwkgWb7N6wZ2vZK4SMyOvq21rKaumFNSoVUitYd96HqlVlYw/70PVKDo8O+6n1irBKrYf90/eVOSjmXMlBTEt0D7q5hh/3DhwLCqIKuYb96I/QVEZl/wDqcX9xJi38or/WPzCL/wDUo/XRi38nrvW+oUI5LghBSI6hKkShUKhCVAiEqLIJaenlqXFkLC9wGaw32VzDqaKMz1VfE/oKYAllrZ3E2DVSgmlp5mzQSOjkbuc02IV99XUVeD1nTTySOFRE52Y30s4fNUDeuY9WHO9sccbbngyFg/8A3mmznCmUczIHTyVDSBG82DXczbkn0rJpMAr2UzSXdMx0zW7zHY/C6MKFNUtOH1ENnyOL2Tt3ts0mx5jRTcRmWv5p7ZZGODmSOaQbgglX6PDY67pXU8sj2QsL3kRm4HlxT5MIuWmCZoAjzyCU5DH2rAG/NX3NNivVYpV1dKKaR4bDmzOawWzO5lVGEx9xzm+RsrJw+oFU6nyXezvHgBzvySuw6cSwxtyvMwJYWuuDbemU6QGeXd0jreafBUVEcgMMj855G6r3V/CLtqKiZuj4KWSRp8d31QTsqRitqWoaxlSTaOa1sx5FZkjHRSvjkaWvYbOB4FWccjFNjFZHHoGEEeByg/NXMdgkqMTpXsbeWqo45ngcXZdT8FDGSHWII3g3CV8skkz5nvJkkOZzuZUY13aoVVK2aVsvSiRwkOhdfVSQVtRTCQRSENl77TqHKvv04oTTFisrJq2SN8xH2UYiY1osGtHBQXSIUCqGp7rVLdQ1G5qEPod7/JWbKvQ/1PIK1ZFpuoII0I1B8V0lO+CbEIsTdlZHWQyQzEmwZNltryuudsrmG1jKV8kNQzpKScZZWcRycPEJfTK7W1EsFTRyOY2CCjcDDTtO/mfG/NU8Lq+jn6tPIOpzPJkY7dqd/gUyvojSTjt9JC/tRS8HN/yrHUqaop4pacyRmZzmsD9Q4jhp5pxPSaadn8Dlgox0joKmRgdx6M2s74WVHBDCzGKU1GXos1ru3A20v4XsoI2StkcGNeHM7wA1HmoyS43JvxuqjonYTiE9KamorpI6kPcS0vIYWjUFvgn4DBROhb2I5Jnsmd0zjdoc0XA92q55lTOyMxslcGOFiLqbDK2SgqY3McejBu5g3OFrEfFFWJ8IxOpAqGsFU0i+eHVqpta8M6g+MsfJOwlx3jha3tUMbpIQWskc0btHFDXlkzJd7muDteNiojeqI2tnp445JWFxcyljiOXsgkFxPMkFZNXhtXTSOM1PIzW5L9616p1BW07GzF8TAXOp5wNGhxuWO8iTuWTikrZa9zoZumaGNaXi/aIFiVeKzBh0r4sQpaqVznRU0zHPJN8rb2TXwGSnq5mvdI2mnETBe/ZcTa3uV2KShmwmqMzerzODIQW6h1jmzEc9FNh1XTYRRyXeJZKzS7d0Ybud53UvU01RloJqeIRsfI2TozLOwGwY3hfzSxSTYq0URLWMjY6SJjGgZiBx5m11oGjmkw6DDoPtK2sIqKuU/gj/AAgn4qHDqWCm2gw5kFSJ5usgOyggBvHers3YIKDGGQUbDaUVMMToYywkBzTe2byuVk3c7tPcXOO8k6lSTNYKiYR9wSuDfK5sm2QNSJSkRQp6D72PIqDgrFB97b5FB0WH/dP3lTFQ4f8AdD65UxRgiEIRChXsM+9fscqAV7DT/uP2lBln+ZR/3E7Ff5TiHn9Qmv0xKL+4nYmL4ViPt+YUI5HgkS8EijoEoSJQqFSpAlCqlSJUIgCt0E8cUskc4JgnZkktw5H2FVoo3yvyRjM7kr2HYa+rrehmvDGxpfK5wtlaN6FJG2sw2ra6leS46Ne0Xa8eS1j/ABueN5ioGRvkaWuexgBsfkqYxrI+Onw+1JRh3fcMznDmf/Su4hWYdC9jZYnVMr42yZ7uA1F+ajKHDsJxagke40EzopYzG9rTa4PG4TZMPqIIaxjaere+ojEf2rf1A3vfwVT+JRAktomgcPtnFSvxN8DYz1KMZ25m5nO3c960na/hb5GPp2TM+2kppad4dxtqy/xCq4TJPLjVCx0PRRxNlYxgGjbsddMbtDUs7lNTtPtQ/aXEni14W+Ueqm1e1nB2UUMNG9sUT2CMyVU7zct39kDmo8HpoIa/rDp2PpZWua9huH5DwtzUNJjjqfR1NGRzaLFaEeJR4gLNqZInX7mgP+FOys8YVWYviNRVTs6vBLKXvlk0a1t/8LYdLDUbWYVU0fbpHUrogSLaNDgVj1VFNUyPjhrutlhs6MvsfdxWcZKmkzQhz4jYgtOm/ei6u4c+hqqHqTKfoqxwOWcuuDbw4LJViCpkp4iyOzQTckb7clC85pHG1gTcDkg0cEioJ61kVdK+MmRmQtbcHXcVHiUcLq6qfDJcmVxyWtl1OipNu1wc02c03B5KejqjSTyS9EyV0jHNs/hfj5q4oqKKamfllFj0Ql0/KdyaKSo6u6cxOETRcvtorgxV0mHVcFUDJK+ERRP4tGYG3lorVJXT1uFYvDM4Eila8Hj2XtUxNUZsMfHBAXSNEszmtycWh24lJtJQS0mIzgxlsETmxMPA6b/gVp1eLUFWKWd0cjJGOjdMxoFnFoABvyss3GKiGRtaI5zKJKwSMvfukO/zZFntQoN0nkFaUuz+FTYjHUugfE0xZbh7st733K9JgOJMBPVi9vNhBCQ5MxFlZloaqEfaU8rPNhUJYRvBCrKSKrljh6DR8N75HagHmOS0aXEoKeihDYxmZNIQCLlhLRZ3vCybIsg18MqujpKyrLs0/TXk5yNIP1UAwtjcOo3ds1FTG+RuUXAANrLPFxuJHkrtXV9JRYWyJ7myU0ckb8ptvdcJbb9i27CY/wCGUbIQZKqscHNeTZrW2JI+CShw1tJjVFT1zQ9lQ8ZHMdxB+SyhLKGtaJZLM7ozHRWIK18ctC993Gkn6VridbXuR8FMRWqXiasqJG910ryNLaXKjspJLGWRzRZrnuLRyBN02yrSzT4jU08YjBY+MbmSNzAKycUppLdYw2J3MxHIs2yLIjboRgdY5w6jPGWi+tQNfLRNmOz0bjG6krGPG9rnG4+CoYcymdU2qn5G2JaSbAngCeCXFBJLVuqXzRS9JYXiNwLC1kiNGPE8NjgniikrInTPjcZGm7rN4fFRsxGnp3T17ZWy1DWOZTgMyuzO0zHyCxbIsio2MysDeSCE8hIimEJqkKaQgaVNQ/e2e1Qqeh++M9qK6Gg+7O9dTlQYf93f6ymOguUYBQkTgxxGgKBFcwz73+0/JVujdyKtYZ98Hqn5IYzX/wAzj/uJ+I/yvEfIpsv8yj9dSYl/LMQ8QSojjeASJfwjySI6FShIlCASpEqBUiEKqc1xa4OaSHDUEcFqU1RU1OHYk3pHvl6NhGuuXN2vospS01RLSzNmhdle32g+BHFEprYJZo3GJjnAbyBuvzVvFtcUlY3VsLGRAjk1oCt0mJtZOZoH9TqHNs45Q6N+vEHcm4jNik7XOlMUrHC2eCNouPMBKmiWiigwESvaeuECc2OgiLsvvup8Vo4p3YcKOYEdSYAx3e3uKzJa2eUSB7r54G0+vBotb5KWmxOopqumqI2szU8IhAcLgjX/ACpgYKF4lyukYGdGZOkBuMu75qJ9PI2ATtBdCTlEgGl1clxJkgrWmPKKinETGtGkZDg7Tw0Kv01XHT7O0HTWdTyCdkkQ3ucCCCFS/wAY/UanooZBE5zZwSzKL3tvU1LQvdS1s8sbmthp+kY4i1zmA/ytTDqqCmoBEJ45Q0hzY3vLSG31sRuPgm4fiBmbidO57GxSFhjaTdrRnuQD7UkTe2BlkjLXODmE6g7vatqnmjqcN6TFrvhEwgbOO+w2vqeIRUNxHF2RsqmRQiAEgkBvZ9ididPT02Ay0kEjpJYZmVMuYWsD2bfJasw99VlYjQyUFSYZCHAjNG8bnt5hV2xveHFjS7KMxsNw5rXpc1VgWWW1qSrjbE935X6Fvs3p1DSCggxKSsf0bSHUcf6nX1Plp8Vif1WKEi0qyOnbRRmkZGWk2c5riSDbcs06Gx3qqFq0pihwiorMwDnRvpXs4kmxB+CzmROdFJLazGWufNOZTyPp5JQOxGRf2mwREA3KKq3NWhLh9VFLJG+B4fGMzxbuhZ9V+FS1Z7dRsG1kkVex5ylxjANuNytOfF6CmqpIHPfdhtnDDY+1Y+xVLWVcNeyilDHDoyQeOpXSNpcYg7LoYpB5AonJDHi9FJqyvbfk5xHzVkTRzC4fBLfmGuUUkQc3/d4TG7n9mqj6HB3m7qCSE843kIwuuoqSQfaUFOfFoyn4KvJguHPP3aSP1JP8qAYdRA/YYhWQHlmuFKKKrFurY2w+ErEETtm6Etu2pnjPiwFRP2WY70OJQk/8jHNV0Q46w9l1DUDwdlKV1Ri0QvNgrnjiYpAUO2Q/ZbEBfonU8w/RKPqq0uA4tD36CYj9IzfJbpxeJhAnoaqE8bsT48dw0Hs1boXfqu1Da5KWGaE5ZYZGHk5pCjXfR4lDKOxXxvB4FwN/elkigntnpqWUf2xr7QquuAQu3kwjDXm76Brf7bi3/KrP2ew14Nusxu4ZXAj4hDXJWS5RyXSv2XprfZYhI0/8kOnwKgdsrUHWKupHD9Ti36KrsYBCaQtqTZfFW3LYWSgcY5Gn/wBqpLg+JQi8lDO0eoVBQITbKZ8b2aPY5p5OFk2wQREJhCmITCCio7Kaj+9x+ajspqEXrohzJQb2H/d3+slmmazs7ym0bslPK48HKoQ982a3eKLJtdBh0UZsZW5itdkTXi4Y2y52KoMQHgrMOKPzZS7RZ16uPGRNURiOTpLaDeE2Isp5hM3VtiD4FMqa1r7kb1SkqAKVzObrqSn5OPH6RvObEIj/AMgUuJD/AKZWjmx3yVOKQOqYuYeFoYiL4bWeo75LTyWOIHdCEDujyQihKEJQgRKhKFVIlS2S2RDUJ1kWRCBPjkkheHRPcx3Npsm2S2QXBiLni1TTwzjmW5Xe8J4dhco1ZUUzvC0g+ioIQaAw6GXWnr4Hjk/sH4qd+G4jLR09LHTB7IHvkDozckutf5LHsnNc5mrHvafBxCC+MBxQ/wDZTe5O/gGJ/ipiwfqcB9VS6zU2t1ma39wpjnvf33ud5uJRGjDhk9K8vNZDTkjKT0l9OSVn8Oo45xJVTVT5m5XNibYHW+pPksqwRogt1uIS1UUdOyNsFNGczYmHS/M+KgfNJOWdM9zw3cOSjQir1RPSR4WaeldI6WSYPcXCwaMpB+apzvEk7ntFmncE1IitCaspn0FLAyB4dECX3PZe4neVfw6eilZSUz5Ax0rWwystoCJM2YlYCEHUUGKHEcfpqXL3quUvf+Zmth7AsXHp4qkSvaWlzKlzGOAsXM8fcm4ZXHDqzrLW5niN7W+BItdZcwsxgWc+ye3Yf6dSywtxF8IBdaPf5ldoMQnt26cHycuQ/wBMGh8mItcLjKz5ld/1ePkpbfo5cbVIYhH+OF7fZdO6zRPHasPWarLqVh4KJ1E08FZa53jYgNNhs34YT7lG7BKGTVrSPVcpnYcw8Aojh2XukjyKrKF2z0d/s55G/FRnBquM/ZVnvVnoKph7M0ntN04SVrPxB3m1DYpGkxaMaObJ7VA+KqsRUYbFKPGMFawralp7UTT5aJwxG3fgePIgouubmpcOf94wdrPFoLVX/hmDX7Bq6c/okXXjEKd3ezN82ozUE2/oT5gIOSbhzWj/AGuPVMfhILqVtJi7PRYpSTj9bbFdIcMw+XdEw+qVE/AaR3cMjPJyLlYI/wD6CPV1BTVA/wCKUApjsSrItKnBKlvMs7S23YA4D7OrkHmEwYXicPoqsEciSgxmY5Q5sskdRC79UZ0VqDHMPdrHiTWHxcW/NXHx4uNJIY5QPAFVJYs33vB43D+3/hDpbZiIkGWOujkB4FzXfNNfBBP6SipJPHogCfaFmPo8Gcby4a+J3Nji1RDC8K/oV1bTnwddUaEmD4Y/V2HNB/45C3/KrS7N4U8XaKuI+Dg4fFNbh9Q23VdoDblKxOy46zVlTRzjx0JUO1STZSld6LES3+5Ebe8FQjZl1HJ1rrtPIyIFxAJDjpwBWgarG4tZcJbKOcT1BPi0jo3QVGF1ELpG2uRoEqxVo8phcHbiVbMbGs3Cyzz9nAWO3mxUTqqQNy5uysvTwiaZ93GxVTpnCTVIZt+qhmlGS99UjduLgqWjvOUNRU62BWc1xI3ppeb71cYvJqYcc1XH6wW5Wj/p9b6j/ksXBaeSaV8zBdkGVz/AXW/WtvhtYeJjeR/4laceVcC3ut8kqGjsN8ktlA1KE6yUBUIAlASgJwCBtkoCdZLZENsiydlRlQNskspLJLIGWRZPsiyBtkWTrIsgbZJZPsksgbZIn2SEIGITrIsgahLZLZFNsiydZFkQxQ1O5qs2Veq3NUant02wOK02FOrX1OezwwDI2/NdzHtPhEm+rEfrtIXkFG8sLwBcFXW1Dhuc4eF1MW16/DidBUehraeQ8myAqyCCLg3HNeMipPGx8xdTx4hNHbJI5tvyvLfkieT2FJZeWw7SYjF3ayb2uzfNXottMRZbNJG+3B8X1BCGvQ8o5IyDkuLg25l/rU0D/UeWfMFX4dtaJ4HS08rCfylrvqqdOjMTTwTDTsPBZcW1WFSGxmez1mFXYsXw6YXjrYT4F4B+KJ48ae6jYeCjdh7DwVxj2vF2ODhzBunonxxluw1o3JOqSs7krx5OWqksifGzAKtg0lJ8xdL1mradWsPsK0co5JMgRPCqPXpR3oL+Tk4YhH+Jj2+y6tGJp4D3JppmHgEM5ITVUsnec0+s1MNNh82uSE+5Suo2ngojQM5BGe/uIpMDoH7oy31Sq79nYf6U0jParfUS03aSD4EhJ0NS3uyv9puqb/Ge7BKuL0NYfaqNdT4rT0zs012EgO14ErfzVbeIPmEOmmc3LLCx7eW5RZXnuKl8NSYzoRvWeZHHeV1G0OGy1BlrBH2mNu4AcAuTe8XUejhTi4qN5NkB104tuFVRtOiRrA951UgbYJkbSyTMiY6HYlkz8eyMd9iYnCVtt44fFdjXYNfDqiKI3c5jsoI4kLn/APT+nAlnq3g3d9mz6rukrOPE5qaamlME8bo5GaFrhayZkK9mqqKmrABUQsktuLheyqO2fwpxOaii137wjOPJAwp2RenS7I4RIdIXs9V5+qpzbDUT79DUSx+YDkMrz3KnALs5dg5Qfsq6N3rRkfUqrLsVibD9m6CQeDrfMKmOXshbcuzGLRd6ie7xYQ75FU5sLrIPTUkzBzcwhEUbIspXR5TYgg+KMiIjskspciaW+CCOyLKSyTKgZZFk/KlsgjskspLIsgjISWUtgkyoqOySyksksgZZACfZFkDEiksksgZZVqsaNVzKqtcLBntUWeyULC/pLcAFZMTgNyjwvdN5BXUaqplPIpLK4ggHgiKdylDirJjaeCaYmoIc5QJFKYBzTDAeCJhRM4bnH3p4qH271xyOqiMT+SaWOHBBcjrJGEFtgeY0PwV6DaCvgbZlTMByzk/NYlnBF3KDqI9sMRZb/cZvXjBV6DbioA+1jgf42LVxWZyA4odvQ4tt4XWz0v8A4Sg/AgK9FtZhsh7Yni9Zl/kSvL86USW3Eou163Hj2FybqyMeDrj5q3FWU03oqiJ5PJ4K8cbUPbueR7VIKuUfiv5qmvZkLyCHE6iH0Ukkf9uRzfkVeh2nxKL/ALqY+DnBw+IUXXqCLBefxba1zT2zG/1o7fJXIduXk/aU0R55XEfNE2OzyhGRvJc1HtrRut0lNM0c2kO+oV2DaWhrC+OlMrpAwuF4yBp4qnSbFaqODDa85R9nC4n2heTED8W5emiRk9FNCbHODnN9bFcptNhjY4RU0zDlB7fhyTFjDmhYyY9A/PFYEE70gKrRE5tFchiLzoFWoexl2XUL99hvO5WpXCKPLpdLg0PWMSjJF2sOYqlrt9m6bqdFSQC1xq423krplzlISBYK91t7sfjga93RiE5m8MyWMytVIlQsKiksxpcTZo3kpjZQ7VrwR4FTEAggi4K56swmWKpIpW3jfq1oNsvMK658uP6b2cp2fwXK5a6J+UCdpHBpJTxiFbFo6V49dqbGd5R0+cJcwXOtxmpB7Qjd7LKePGXHvU//AIuTpfKth8EMvpImP9ZoKqS4Lhk189DBryYAfgoRi0X4o5G+y6mbiNM7+pbzBCYef8U5dk8Jk7sL4/UkP1uqUuxFG70VTMzzAct9lTE4XbKw+1Sh/imL5cXHy7DS69FXMPg6Mj6lU5tjMTZ3HQSeq63zC73MUudDeLzWXZnF4zrRud6pB+qpS4bWwelpJ2eLoyvWMwRmCGT9vHiwgpMpXr8kMMwtLGx4/U0FVZcGw2Y3fQwE+DAPkmr4vKspQWlekS7KYRJugdGf0PP1VSbYmhd6KomZ61nf4V1PGuBsUll2cuwz7/ZVzT60dvqqUuxeJM7j4JPJxB+ITTK5hFlty7L4vENaMuH6XB3yKqS4TXQ+ko52/sKDPsiymdE5ps5paeRFk0sREdlTxDus8ytDIqWJNysZ5lRZ7GF7pvIK7ZVMI7s/7fqr1kjZiE+yTKiGoTsqTKUQ1CdlKSyKRInJLIEsEmVvJOSIGGNp4JphHAqVCCAw8ik6JynQiKxYRwSWPIqyhVVXVLc81YLRySGNp4IiHMUZlL0QSGLxUDA83XTbG3e/E5XH0cAaDyuuaMZC6vY2CSPCsTqCCGylrG/qsNbKq0MOcell8W2WhUOjgozFK3MZhq08lQoahlLM6Rzc92kAHde6gqJn1Epe9xLnFdJBmPwmmjkJYXZB4blVxynGHNYIXtc1wvmaugmj6CjGb0r+A4LErKN1TEY9wOt0w1gZnycyV1GzlCYos8je2fgqdNTQUn6nb7W3q9R4h1eou9uZjjqBw8knEtdJA3K9qoVLpf4pPNE4hwflBHCyv0k8U4bLE67Dz3hVKG0kj3OF80hK1YzHSUOfqUXSuzPLbklWFFA4GMC24KVcK6BZ+JROnpp6eN5ZI5meMjeCFeLgCASLngqtZmZNBK3gS0//AL2KJXIdfnbGwMqHtcW6kO1BTI8VrBrJMXniHi91lbQximx6sYNGvcJABycLqkKktGjnJjLr6XFIXygVkUbY7E3a3VaFFStrWGpphaFziGg71w1PUZpm9JI4gLuMBxPDaTC4aeWuhbILk5jl1JJ4ph1Wg3DtO0Anfw5itQ1VPP6GeKT1Hg/JTIeEZzsOZyTDh4bq0kHwK1Eius/HGZ1eoZ3Zn++6S9W3QPv5halgkyjkmp8dZvWapp1jafgl688d6B3sK0OjbyTTC08Amp8fJUFfH+Jjx7E8VsB/qAeeildSsPBMNGwjcrqePI9lRG7uyNPkU/OVTdh7DwUZoCO65w9qHlyjRzozhZvV6lvdmf7TdLmrWfiDvNqh51pZwlzBZnWqpvejY73hOFc8d6A+wp018laDmskFnta4ciLqrJhOHSjt0UB8mAfJRjEIvxNe3zCe2upz/Ut5hMX5IqS7MYRJ/wBrl9V5H1XIbdbP0mF0EE9M6S7pMpa43G5d+2ojd3ZGn2rkP9S3k4VSC/8AWPyRZylcThHdn/b9VfVHCB2J/wBv1V+xSNkQlSIBCEIBCEIhLJLJyRDCZUmVOQgYWFIWlSIQRWKCpLJLII0J+UIyhAxCdlRlQNSJ2UpMpVCHdoL+C9Eio/4bg1BRO0zAh1vzkXXKbO4LNilZFKBamilaZHX321su12lDm0Ec7B2oZWuv8Pqg56VuRxG7W6dRsEtSA7uN7R8lbqTDXNZJGcr7WeCeKqvLYYTGzvO7x8F0iEq5hNUuffTgqznAR+JTnLKqKiSOuZE8XZcO9i0zqd0YujIOSsuaCSQkyqiXDZJoJCY79Gd7eC1sIaS9reZVGhZaNXaWQ0xdIPwjTzSjo2zwxyNgzjpDwUnSB2YM1LTYrm6OR4Mk47Uruyy/PmtON3VX09Lnu++eU+K43i3Kv5AZs+8WWXitc+HFKOnHon36T3q/TztJfyvosbHoDNG2Yb43ndyKmKwP9QoRFiVFI0d6IsJ5kLk85XY7XT9d2do5j6WGcMPjoRdcj0em9RmmiQhPE7h+I+RUZYUhaeSonE+tyGk87K1Di9VB6KomZ6shCzbIQb8W1OKRnStlt+oB3zCvwbbYgz0hhkHjHb5FcjcoDiodu8i27f8A1KKJ3iyYj5hXoNtqF/paeoj8gHD4FebZyndIUNr1SParCX76gx+uwhXIcYw6f0VbAf3gLyETOG5xSid3P3hDa9oY9jxdjmuHMG6evF2VLmm4AB5tuPkr0GO10IAjrKloHDpXEe4qNa9aQvNItsMUZvqc3g6Np+iuxbcVo70dM/zDmlDXe2SZRyXIxbdMNs9CTzySj5FXYts8Nf34qmPzjBHwJROq6AxtPBNMDTwWfFtHhMtrVrAeTgW/NW48QopfR1cDvKQFE8eNONKw8Ao3ULDwVoEOFwQR4JyqfHxZzsOYeC47/UOk6vQUhG4yn5L0JcZ/qa2+C055TfQqE4Zdcbs+wOgq78Mn1Wl0TVnbO+gq/wBn1Wqq3URhCYYFYQUZ1V6EpDEVbRZBSMbgkynkrxaDwSZAgo2KarxiCaYQi6ppVYMCaYUECFKYnJpjIQ0xInFpSWKBEiVCBEJUiBU1OSKjtdn5mU+zlKYJPtC5znsvv1/+LZfUQ4rhs0TCBIWG7TwKwNncO61gLKiJ2STpHC5HAFJUyfw+YGOYOl4kJgpMJaWnjxT3u1UBnjO92t9yt0MXXJOia4X4eK6xmobk6c1LUUzMwkyjOGZb24K2/DZYZAHDiAp6+mMUZeztN3EqxGO1lhbkjIp2C5VhtN0mgIB5laQtCw9FuSydkPYdL6qakkbTHJKNx3qriczRUse3uvNkEmGVPQBz7XIOnmnxzvNSZXuu471UpB9k/wAHKUDVTFaMU7r6HersBbL9m8Zg/QgrHiktJ4BaWF5pJi8nsM1JWeUajl9oGmHB6iBxvkqWAey65pdFtSxwpopJCA6rnc8N45RuK58hclNSJUiBLBIWjknJEDSwJOjT0II+jSZDyUqFEQ5TySWU6LIIEmqnICTKEEPa5pQ4jfqpCxNyKgz+CUSEbiQkLEmVDEgneNA4pwncOI9yhseSTVQXoq+eM9iSRvqvI+RV2HaHEou5XVI8C/MPiCsTVLcoOqg2zxOMjPLFL68YHyss7anaSfF6GGnljiaGvzXZfl4rGzFQVRu1qEaezvoKv9nzK1Fl7O+gq/2fMrURaEIQjJboSIQOQhCBEIQgEIQgLJC1OQUEZjCaYQVKhBAYRZMMCspEVVMJTTEQriLXQUch5JMpV7KEhjFkHTbIxitwCWlJcwxVDrkcb6/VXajZ9trsLbcXHgo9m4nt2eh6oWiZsrjL+o3Onusr9Y2oqI7NcWni0qxXE4jHDDMRESfFVKeslpauOVl/szcDyXRVkTIH5Jo2Bx3gLJq6VovLE0jyFlsdhPWRVMAlidfMAQqVRK7qhYBfMVn4dLliYHHsZb/FXhKyR7WtXSMVRjbZ6stfYpssRZLYDRNOhstIsFwcLOF/NUcRjvTFzd7DcBT3TZTeMg7lUEItTMI/GLpx0CIhaNnICyeGmQgNBJ8FmqaxjnWDRcrTrZOo4a2ljNp5tDbeAd5UlPAygh6ecfafhZ4rPDJauodUTHQal3AeC53tqIscZDNTtpSy5LAWO4s0XFEAjcu0rpY3wTTuPZiYbeOi4tvcB5rFU0tTS1SIUVFZFlJZFkEVighS2SEBBHZCksElgoI0J+VGVEMQnZUlkDUWS2QqoQhCiEIRYJSkQJlCMgTkiBmRV6xtg1W1VrtzUqxo7O+gq/2fMrUWXs76Cr/Z8ytRChCEIyEIQgW6EiEAlSIQLdIlSIBCEIBCEIBIhCoEIQgEqRKg6DZeodSsqXmNz2SSNBI4WC6eWSOSMF2jHDR/AFYexsoNJVxOHdlB18R/6W42nyOkGjopDcsPAqNxnSYVE4GommBaBe/h5rmMRr4p5DT0/cabk24LW2gY+lzQslcIZBcC+48ly8MZivl47ytcUrUoSDT5L3LNPJSBzmPuCq+FdoVHNrgPgrEjtdV1lZX6epZLGWTGz+BVeQlj+1qOaq6nUJvTvAtwWmVsSDmo5ZAGHW6rGQngmucSmmLeHYjHHJklZfkSttmIwxAPigHmuTdY+BWlSAimzSk5BuA4qXtW9UVMdQWuO4jcoa+U9WENNGQCO0QFkOrngjJD2RwJV3DscbEcj2BoO8OKxYsU8RgdJg9TEzvPiIAXH0z+kp2niBYr1GKlpKp7XRO7I1dGvM5KXqeO1tFfsse4DTeL6LFaNSKwYU0wlQQoUhjITSwoGoS2KSygRInWSFUCRKkUAhCEBZFkqEDbJMqchUNypC1PQgZYosU9KoIrFVK7c1X7KniI7LPMpT7XtnvQVf7PmVprM2e9BV/s+ZWmhSoSJUQIQhECEIQCEIQCEJECoSIQKkQhAIQhAIQhUCEIQdLscAZK2NwuHBjvmurXGbIm2MOF+9AfgQu0WW453a5t6RjhvXJbmkrttphfDSuJbqLLUSloKh0DC9o0eTceN1p1A1WG30XRne15Ps3haOFT9ewuGRzx0urXC/JXRI12qce0bpr2FjiChpWtMODEhYlzJpdyV0wwxXK06WgfU0T5S8sbGoqCifUve+RrhHGLm+i3YpIKVjWwgsIbYxu3PCdoqDBpGQtc277i4AUTcElmfZ0eXxK1QetxXppDFMz8F9AqT8Rr6aTo52kC9s9gQs7Rbp8JFK1r+suZkC4LGZWT7Yzvjbla9l/gunqqmaV5L5nOB9gXJVOu08nhF9FFTWS2SoUZNygpCwck9CghMQSGEKZIioDCE3oVZsiyIqGEppiKu2CMoRdUMh5JMpV4sCToxyQ1RSK8YWphg1QVEKyYE0wFBAhSmIpvRlVTEJ2UosUCKniPdZ5lXFTxHuM8yoRd2e9BV/s+ZWmqGzURkp6wgtFizebc1q9Vm/Jm9U3QqFKnGN43scPYmG43ohUJEIhUJEIFSIQgEIQihCEIgQhCAQhIgEIQgEoSIRVzDayWgqxUQMzvyloadxuuhjdiUoD6mqLL/hZosLC4g6QSubcNK3XzDJJrbo9/gs16fxcNYeLvr6eXMypc+MusWON1RG5SGvkqaiaMXI115JkMcj2AhpVifk4fpVkdkqHnh0ZPtC52J74yHRvc0jkV0ldSTvpZckZL3EWssk4NWMAvESCrrnONPpccqoWZH2laeDir0ePRPDc0Lmk77blTo8Gq56yKNsLu04Aka2BO9epYfs/huHhvQUzM4/EdSVdTMcbh7MQxHKaeglyne9/ZC7KhwyCipwJg1z3nVx11WoqZmbURTQm3SC4tzTUPdHDFCWGwa7eVjVk0c0TGb3R6A81L190TTFKzpGDQgqBzaCXVsj4jxa7X3LpJjFqtTzSQuvfUG4dxU1VVyzDtm4TJqSB1zDUEu5LKrsXpaCMxyzh8o/AwXKUS1tTFSQGaUgAbgeK5jC5nVFZV1Lxq5oFuVys+vxCevmzzO0HdaNwV/BBamnPNwCxWmiEJEKMlQkuluoEQhCAQhCAQhCBEIQgVCRCBUIQgSw5IyjklQgaY2ngmmEKRKggNOCs3GI+jjj8ytlZWO+ii9YosO2flMcVUBxLN/tWsKk8QFiYIbR1H7fqtG6jPL20G1tt+YeRT+vg3ufe0FZt0XRnWl0sDhrFCfK7Sm5ad2uVzfVddUMyMyaavmCI92Rw9ZqTqu/LNGfbYqo2V43OITxUyfmumrqwaKo4Rl3qm6idFI3vMcPYhlVlPdHs0Ura5wFg54HLMqaroVsVubvZHW/O0FHSwuGsMRPMEgouqiFcyUzyT0crRb8Dw5NNPCe7M5p/Ww/NDVVCtdTLr5JonW5utf3ppoaoW+xLr7suvyRVdCc6N7DZzHDzCagRCEIBCEIrWwyeCGkkMh7WcJ/XQamqbe5dqPcsGaTo26i43qSWqHSsqG7pBldbgj08OWRYw7oqSCYu+0kndob7ldhcGttYC3BZlK4dxjc0mt78ApnSdG+75LuUbllX31bG6E2VeWrY5pAdr5Kq6UO4XUTrHwTC8o6TZzHKGmw+RtU8RzRuJJI1cF0NPicNTSx1MJvG+9ivJqyspi1zAM55q7gO07sNp+qzML4M2Zlt7VuSfbzcnpZxDk1ZFVI81ZeCWuJuCFx9ZtjVSH/bxiMeO9VDtTiJN3ZCfJb/zGMrt3Z37wSeagnlp6VmepkbG3xK407T4mWFvStbcWuAsuoqZ6l2aeZ8h/UU8jG/iu03SB0OHtMbdxk4lc25xe4uc4ucd5KRCxasgC3sHbbDifzSH5LCAXQ4c3LhkH6szvioqwhCEYCEIUAgoQUAhCEAhCEAkSoQCEIQCEiLqhUIQoBLdIhAqy8d9FF6xWosvHfRResUWe0eCC7Kj9v1WjZZ+B+jqf2/VaKicvYtZCELLICEJFYmBCEq14rhEt0iFPE8TgUXTUKYeJ4dY6aKQSuH4ioEajimJiwJnX1sfMJ7agtOgsfDRVLlOvohlX218zRYSyW5E3CXrxebyRxPPiwfRZ+YpQ9U7aTX0z2jPTAcy1xCMlE4m3TM5DvLPD0okI4qabV7qcDrZKxt+T2Ftk3+Hym+R0TwOTxqqomcEol8FdXySS0UwFnwv18FXFOGCxaR4EK02qLNz3t8iQp24jIW5emuBwe0EfFNWc2ZI1zRni0cBwTIhnYC4HNxutgVTTfpIad9+IblI9yZekMZvTOzcxKq3PyMKurTSPbG1oJIvcrMmrJpu8825BamOxxihppWEgvkd2DvaOGqwUa8rQUIQiHIQhUCRKkKAQhCBQuko25aCmH/Hf4rmwL6c9F1WUMjjZ+VoCJTUqRKjIQhCAQlQoEQlskQIhCEAhCEAhCEAhIlQCVIhAqEiVALLx30UXrFaiy8d9FF6xRZ7NwP0VT+36rSss7AvRVP7fqtElZTl7LomoukVkTAUISrUUiEIVUgcM5ZxAuU5RxW6aZ536NUiBEJpkAlbGQbuBI9itQUVTUNvFA9w5gaIYroTnsdG8se0tcN4IsU1DAhCEQIQrNHQVVdIGU0LnnieA8yoYrXQCuir9mosPwmWpqKwCdrbhtuyTy5lc23tNBU9l4pMyLpoSpjPiW6W6alTDDrpeFrmyQMNkuQpiYz8aJNNDfg5Yp3rbxYXpQOIcsUgqOvH0RCEKqUJU1KgVCEioEIQoJaZuapibzeF079XnzWFgtxi1M8EDK7N7l1ZrBISZYIX33nLY/BVms+yLK/0lC49qncz1Hn6ppipHjsSvb5tBUZ1SQrfUmHuVMZ8DcFJ1Ce/ZaH+oboaqoUj4JWauieB4hMsihIhCBEJUIEQlQgRCEIBCEIBCEIBKkSoBZeO+ii9YrUWXjvoovWKLPZuBuyxVPPs/VXy4k6rNwb0dR+36rRuFYthbpU26FWTroumoQKlSIQDhYFw324KnBiLX9mVuUq5eyzK8Qk5m9l3zUab+E08NbUsmJD2QSAPZfUh2l/Jd0yjjgfGJjmdIcoHBul9PcvGYqiaEkxSOYSLHKbXC28N2sxCifB0rzUxQuzBjzqTYjf7VLtblx3WN4THJZ8jXPA3SN0cPM8ViuwE6ZZXtzaNDo9CfNbOBY9Ry4TFbO/K0umN8xjO83TMR2iZhWz1Me/W1Ef2UZ3i/E+AUla2fbkDdsj2OFnMcWuHiEijiGVnadmeSXOdzJ1KkutOVB3LqKja6hwyi6PD4A/K0ZRuu7jcLk5rkBrdC42uiKSCMBklDFIQdX3IJSwhlVXVmMVQqMQqBYd2MHQKcOZ+Ye9O6xh733dRSRNA3MeD80hGFStPSSSRng0xX+IKSYUCx3JQozQ0gDTTYnDmJ7jszfiRZXGUjzZokgkcfySgqorgJQNVZ6lUG+WFzrb8ovZMMMjd7HDzCIVqlihfPII4mlz3GwAG9SYfh1VXTdHCzdvcdAAu1wvCocOiGUZ5j3pDv9nIKbhIwhsZ01OOnq3RyneGtuAs2s/0/qrl1NWRP8HtLf8AK79JdRvqPLajYTGWatjhl9R/+VmVGzmLUt+lw+cAcWi4+C9lJsmdMy9r6odPDJYJIyQ+N7SN+YWUS92JiqG2cwPH6m3WRjlNgFFSOqMQpKcN4dgXceQVHkGqNVerZIKmrfLT0wp4SeywG6gyoIEq1IaWOkY2qqwHEi8cPF3InwVaUvnkMkli88QLJmibBWnrjnflaVs5isej6SKQ9GC4v0sN66D+D4v0Ykfh8tjysT7t6jFlV8x5pLg7wESxTwG09PNEf1sIUQlYdzlMYyphbm4e1KCRukt5hMGoSIna0yrqWEZZt27tFSHEJj6WNr78S0Eqklugt9apnO+0pWD1btTstDJxkj9ocqfSO5pC4He1p9iaurZpoHAmOpA8HNISGhltdjo3jwcqoDOALfJyMrvwTEesLpq6nfSzsF3wvA52UJFjYi3mlZPVRnsPHmHEKcYhWNFpIy9vkHppqsUKx16BxPS07G/sLU4SYfId0jfVeD81dXVVCutpKeUfZ1Jb4PZ9Qh2GSamOWGTydb5oapIU7qKpbe8LvZqoSx7e80jzCKRIiyVALLx30UXrFaiy8d9FF6xRZ7RYP3J/2/VX1Qwf0dR+36q+rFoQhCqDVF0IQLdF0iECk6KjURiQm4VxMcwFFZclMfwqAscDuK13RppjUVToJKunnz0sjonkWJHJWhFI+Yy1EjpHnTM43VxlFPHC2odC4Qk2D7aEpSAkgRoDRYJ4UZkY3e4Jpc+TRoyt5lVkk5u4Zd7d5CWRtgHc96bK9sLMo1e7QBTObdgaeSKquTCU925QudqooJ1ScU0lPha6aZkTNXyODWjmSqHNlkaLNkkaOTXEKw3Eq1jQ1tTJlHAm4V6v2WxKgoW1Usd9TnY03LBzKxcyJrZpdp8YpLiGoiynUtdENVpQ7dYmzSWnpZPIFv1XKZkocor1LZzaBmORygw9BPCRmZmzAg8QVtryvZfERh+OwSPdlhlBjk8juPvsvS2V9G82bVQk8s4usqsIsEAg7jdYW0e01NgzOhZaascOzEDu8TyQWscxukwWl6Wd15Hejib3nleWYpX1uL1bqmseST3WDusHIKSrqaivqnVVZIZJne5o5AIpKWatqBDC27jqTwaOJJ4BVFOOnllkbHGwve7QALQkgiwk5XFk9ZbdvbEfqfgrE1ZDQskp8NuXnsvqjvdzy8gs0MC10dVHJI+aQvkcXPdvJVnDMNqcSqBBSxlzjvPBo5la+A7NVWJvEjm9FTX1kcN/q816Fh2HU2G04hpYw1vE8XeZ4qbgobP7PwYLT8Jal3flt8B4LaQhZUhAIsRcKrNhlDOby0cDzzMYuraEGLNsvhUvdgdF6jyFSl2MpzfoayZnLMA7/C6dCDip9j61noKiGUfqu0/VY1fQVeGStZVR5cwuCDcH2rtsY2iosKGRzumqDuiYdb+J4e1c5UQ47tJE2q6NraVxvHCCBa3HXejNkYXSJQ8cVdfgWJsNjRSn1Rf5Ks+gq2Os6lnBG/7Mq4z4mZm80oPionxvYbPY5vmLJu5PFnwThOzWCr3dzS9I4Jh4rHSu5prmxvPajaTzsoek5hL0oUxMqQRRgjKHNt+VxUgzju1Mnk8AhQteOadm8UMqVklSzuPjN+RLVZir6xje3E548LOHxVG6XOeami4cQgzWnpWAH8zC0+8I6XD5DoxzR+l9/mq3TP5lNLwT2mNPsTTVwwUjz2J3N9Zqxto6YQwQOE8Ut3HRh1GnFXfs73ykeRWXjnoou049o71da43tDg/cqP2/VaAWfg/cqP2/VXwtR0pboSIVZLdF0iECoSI0A1NggVIozUxA2zXPIapvTPd3IXebtEEySyj+3PGNvxR0Tz3pnewAIqWdrZWBj3uLQb2zaKIimjbq4X5FyXq0R7+Z3mU9scbO6xo9iCITNGkMTnHwFk60795EY8NSpbougZHAyM37zvzHUqW6RIURXqBl15qi+RX6l0fRkP8AZZZD3XceSiw8yIErmkOY4hzSCCOBUN0IrtIP9QKjqgp66hjqAWlr3B+XMPKy5QTDWzbC5sBwCrIugtdIEudVbpQ5Bdiks4G67+gD8Xw6Kp6MSutkdprcLzdryr9JJVyMbDSSzB5d3Y3EXQx3pp3sJuJGO8CQqU2G0b3ukmjJcd73ONz7VJRvrcJpemxDE5XvLbCEkEf/AFY9ZXioJdVG8I1bStNy4/rPLy1QRS0lJVymSlPQ0kJtLO46E/lbzKgq8SvGaWhb0FKNP1yeJP0UFVVTVRYHlrY4xZkbBZrR4KuqhN3ku02a2Va+JtXibLhwDo4r/E/4XGWU9PWVdL91rKiC+/JIbH2KLHr7WtY0NaA1o3AaAJy8zj2txxjQ3rMT7cXxAn4KzBtti0Z+3ippm+DSw/MqYa9DQuPp9vID95w+oZ4xOa8fGy0qfbDBptHVD4TyljLfjuUVvIVOnxSgqiBT1tPKTuDZAT7lM6qgawyOniDBoXF4t70Ey5vazHf4fB1Old/u5hvH9NvNWsW2io6HD3TwTxVEjuzGxjg67vGy4KGOaurAZJA+pqH9p7jYf/FZEtxdwDCH4nXFpLjG3tTSnUnwv4r0eKNkMbY42hrGiwA4BVcKw+HDKJkEOvFzuLjzV1LdUIQhQIQDvAKrPw+ikN30kDjzMYKtIQZrsBwpxuaKL2XCrybLYS836BzfVeVtIQc4/Y3DnHsyVDRyDgfos7aHC8JwXCnEMfJVS9iHM/W/P2LsZHtjY573BrWi5J4LzLGcT/i+KSVQ9C3sQg/l5+1XtMUbWQlKRVkoLuZTJJxELvPsUc9Q2Ac3cAqccUtbJc6DnyUTGvTPM1OyU2Ga5sjP2zobcykjYI4WxtOjQl3rNYpbrOxk/ZR+sVo6LNxn0UfrFIvH2ZhHcqP2/VXwqGEdyf8Ab9VfW460iVImP7TsvAb1WSmVt7NBcfAJpleP6ZHmUvgNB4JWs4lRUd6iTu5WDmlFO06yvdIfE6KZCqGtY1vdaB5BOSIQCEIQCEqEAhCEAUxztE46pHNFkVQqjmVRzVekiBOhURgPNQVCwpuUq2YXJvRO5IqtYoVgtI4JpamCBKpciOjQRAq1QVstFVxTw9+NwcPNMbFcqxFDYjwQXaqsq8Sk6ase297hrNAorWFgE5FlQ1In2SWQCRLZCIAlSBOCACcEgCcAgMjD3mNPmECGIbo2+5OslCBA1o3AD2J1gRZwuOSRKiLTcSxCMARV9TGGiwAk0HsU0eO4zG7M3EpT4Pa1w+Sz0Jg3ItrcYjHadTTevER8iFZZtvXN9Jh8D/Fspb9CuaQphtdezbmP+phsw9WRp/wpm7cYee/S1jf2A/VcUhMXa71m2WDuPbkmj9aF30BViPajBZRpiETfXBZ8wF50hMNrp9r8fgq6ZmHYfO2USm8z2G4DeV/FcwBuAGialBtqpibpxVSqqxH2Wau+Siqqy92Rm5O8p1HQF1pZt35TxS0MpqOSpd0j9GHieK1WNEbAxo0CNb6aDkEKazoQkRdZZFlnYz6KP1itFZ2M+ij9YqxePtmRyPjPYcW35KdtZO38d/NIhV1qzT18j5mMc0WJsmtrwCczDqTqEIVE7a+D9Q9ilbVQO3SBCE0qQPadxBSoQrGQhCFQIQhAJUiEUqEIRCJr9yEIqud6QoQoESjUoQqqQR6XIUZa2/dCRCtQ0xs5JOiahCilEYCmjbYoQoJLISIWgtkIQoJWupzA4PjeJLdlzToT4qEpEIhQnNBJAAJJ0AHFCEV3mz2zUNNSdJiEDJZ5NcrxfIOS0X7OYRISTRNB8HOHyKELGqqv2QwtxuBM3yeqsmxVMfR1crfNoKVCuirJsTKPRVrHeswj6lVpNjsRa27JIH+AcR8whCbRVl2ZxWLfTZvVcCsuaJ8EropWlsjDZzTvBSIVlSmIQhVkJChCBEIQgRzg0EuOgVCoqXzHJFfKdPNIhSi3SUAis+UAu4DkrlyhCzWaOCLoQog3oQhRAs7GfRR+sUIVi8fb/9k=\n", "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.display import YouTubeVideo\n", "YouTubeVideo(\"k6U-i4gXkLM\")" ] } ], "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.9.12" } }, "nbformat": 4, "nbformat_minor": 5 }