{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solutions and Discussion for HWA 2.3\n",
    "\n",
    "This HWA section gets its own debrief document because we needed to do other things in class. This document is a Jupyter notebook that you can either simply read and enjoy, or you can upload it to SageMath Cloud and play with it interactively. \n",
    "\n",
    "\n",
    "### Side note: The `%` operator \n",
    "\n",
    "In Python and in Sage, the `%` operator is used to return the remainder that occurs when dividing one integer by another. For example, dividing 23 by 5 leaves a remainder of 3, so `23 % 5 = 3`. \n",
    "\n",
    "The `%` (pronounced 'mod') operator is handy for testing whether one integer is divisible by another. Can you think of how? Or, can you see how in the code snippets below?\n",
    "\n",
    "### Problem 1\n",
    "\n",
    "__How many integers between 1000 and 9999 (including 1000 and 9999) are there that are divisible by 9?__\n",
    "\n",
    "First of all let's find _the smallest_ integer in this range that's divisible by 9. We can do this with the `%` operator and a little guess-and-check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1008 % 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks like it's 1008. The next one is 1017, which is 9 units away from 1008. Then the next one is 1026, another 9 units away. In fact _all_ of these divisible-by-9 numbers are 9 units apart, so all we need to do is think about __how many jumps of 9 units are there between 1000 and 9999__.\n",
    "\n",
    "This is the same question as: __If we take the numbers between 1000 and 9999 and group them into groups of 9 each, how many groups are there?__ Now it's easy: We just need to take the number of integers from 1000 and 9999, and divide that number by 9. (Analogy: There are 32 students in one of my classes. How many groups are there if I form groups of 4?) \n",
    "\n",
    "There are 9000 integers between 1000 and 9999, so the number of integers in this range divisible by 9 is $9000/9 = 1000$. \n",
    "\n",
    "The code snippet below finds them all (in the list `divisible_by_nine`) and then finds how many (`len`). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divisible_by_nine = [x for x in range(1000, 10000) if x % 9 == 0]\n",
    "len(divisible_by_nine)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2\n",
    "\n",
    "__How many even numbers are there in this range?__ \n",
    "\n",
    "This one is a lot easier because _exactly half of the integers are even_. Since our range from 1000-9999 is an even length, we just find the number of integers in this range and divide by 2. That would be $9000/2 = 4500$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 3\n",
    "\n",
    "__How many integers in this range have distinct digits?__\n",
    "\n",
    "This means, all the digits are different. We can count these using the law of products. \n",
    "\n",
    "+ There are 9 choices for the first digit ($1, 2, \\dots, 9$). \n",
    "+ Once that choice is made, there are nine choices for the second digit: (anything from $0$ to $9$ except whatever you chose for the first digit). \n",
    "+ Once _that_ choice is made, there are eight choices for the third digit. \n",
    "+ Then there are seven choices for the final digit. \n",
    "\n",
    "So, that's $9 \\times 9 \\times 8 \\times 7 = 4536$ of those. (Which, oddly enough, is one of the integers we just counted because it has distinct digits.) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 4\n",
    "\n",
    "__How many integers in this range are not divisible by 3?__\n",
    "\n",
    "Here we will employ a useful strategy for combinatorics problems which is to approach the problem from the backwards direction. Let's count the number of integers that _are_ divisible by 3; then the number of integers that _aren't_ divisible by 3 will be 9000 minus this number because there are 9000 integers in the range all totalled, and the set of integers that are divisible by 3 and the set of the ones that aren't, are disjoint. \n",
    "\n",
    "We saw how to count this kind of thing in the first problem -- just divide 9000 by (this time) 3. That gives 3000. Therefore the number of integers _not_ divisible by 3 is $9000 - 3000 = 6000$. Here's some code to check: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6000"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "not_divisible_by_three = [x for x in range(1000, 10000) if x % 3 != 0]\n",
    "len(not_divisible_by_three)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 5\n",
    "\n",
    "__How many integers in this range are divisible by either 5 or 7?__ \n",
    "\n",
    "This will be equal to the number that are divisible by 5, plus the number that are divisible by 7, _minus_ the number that are divisible by both 5 _and_ 7. That's the rule of sums. \n",
    "\n",
    "Mimicking the solution for problems 1 and 4, the number of integers in this range divisible by 5 is $9000/5 = 1800$. \n",
    "\n",
    "Finding the number divisible by 7 is trickier because 9000 is not itself divisible by 7. If we just divide we get a decimal. So, we need to round -- but which way? \n",
    "\n",
    "Let's play around with a smaller case to see what we should do. \n",
    "\n",
    "If we just looked at the integers between 1000 and 1050 (sort of a smaller version of the range we use in the main problem), we get 1001, 1008, 1015, 1022, 1029, 1036, 1043, 1050. That's 8 of those; and notice that $51/7 \\approx 7.2$. We divide into 51 because there are 51 integers from 1000 ro 1050. That makes us think we ought to round up. \n",
    "\n",
    "Let's try one more case, from 1000 to 1099: 1001, 1008, 1015, 1022, 1029, 1036, 1043, 1050, 1057, 1064, 1071, 1078, 1085, 1092, 1099. That's 15 in all. Note: $100/7 \\approx 14.29$ so we round up again. \n",
    "\n",
    "If we stop here and generalize, we should compute \n",
    "\n",
    "$$\\lceil 9000/7 \\rceil = 1286$$\n",
    "\n",
    "Let's cheat and use some code to see what that number is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1286"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "div_by_seven = [x for x in range(1000,9999) if x % 7 == 0]\n",
    "len(div_by_seven)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Boom. \n",
    "\n",
    "So there are 1800 integers in range divisible by 5 and 1286 of them divisible by 7. How many are divisible by both 5 _and_ 7? Well, if you are divisible by both 5 and 7 then you must be divisible by 35 (which is $5 \\times 7$). (Note: This is true because 5 and 7 are both prime numbers. This argument doesn't work if the two numbers share a common divisor.) \n",
    "\n",
    "That count is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "257"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "div_by_35 = [x for x in range(1000,9999) if x % 35 == 0]\n",
    "len(div_by_35)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are finally ready to answer the question. Let $A$ be the set of integers in this range that are divisible by 5. Let $B$ be the set of integers in this range that are divisible by 7. Then the number of integers in this range that are divisible by either 5 or 7 is: \n",
    "\n",
    "$$|A \\cup B| = |A| + |B| - |A \\cap B| = 1800 + 1286 - 257 = 2829$$\n",
    "\n",
    "### Problem 8\n",
    "\n",
    "__How many integers in this range are divisible by both 5 and 7?__\n",
    "\n",
    "This is out of order, but we just answered it: 257 of them. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 6\n",
    "\n",
    "__How many integers in this range are not divisible by either 5 or 7?__\n",
    "\n",
    "Well, we just counted the number of integers in the range that _are_ divisible by either 5 or 7, and that count was 2829. So the number of integers that _aren't_ would be all the others, of which there are $9000-2829 = 6171.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 7\n",
    "\n",
    "__How many integers in this range are divisible by 5 but not by 7?__ \n",
    "\n",
    "Since in order to be divisible by 5 _and_ by 7, the integer has to be divisible by 35, this question is the same thing as asking \n",
    "\n",
    "__How many integers in this range are divisible by 5 but not by 35?__ \n",
    "\n",
    "This may not seem any easier to answer, until you start listing out some multiples of 5 and see a pattern. To see this, start all the way back at 0: \n",
    "\n",
    "$$5, 10, 15, 20, 25, 30, \\mathbf{35}, 40, 45, 50, 55, 60, 65, \\mathbf{70}, 75, \\dots$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ones in bold are the ones divisible by 35 and notice they come at regular intervals: _every seventh one_. Which makes sense when you think about 35 equalling $5 \\times 7$. So if we wanted to find, say, all the integers that are divisible by 5 but not by 35 between 1 and 100, we'd need to find all the numbers divisible by 5 and _remove 1/7 of them_. In this case (from 1 to 100) that would be 20 integers in all and remove $\\lfloor 20/7 \\rfloor = 2$ of them for a total of 18, which you can check by brute force. \n",
    "\n",
    "Now just generalize this: Starting at 1000 (which is not divisible by 35) and going to 9999, we already found there were 1800 integers divisible by 5. We will remove $\\lfloor 1800/7 \\rfloor = 257$ of those, and we're left with $1800 - 257 = 1543$.\n",
    "\n",
    "Checking with code: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "five_not_seven = [x for x in range(1000,10000) if x % 5 == 0 and x % 7 != 0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1543"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(five_not_seven)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "What I hope you learn from this exercise is: \n",
    "\n",
    "+ Counting involves formulas sometimes, but far more often it involves __computational thinking__: Breaking down the problem into smaller parts, looking for patterns, making abstractions, and then devising an algorithm to solve your problem. \n",
    "+ The formulas you learn in the book are just tools. They do not give you any insight into the problem! \n",
    "+ Logic is just as important of a tool in counting problems as formulas.\n",
    "+ Mathematics is a creative endeavor and it takes trial and error, and there are lots of opportunities for productive failure. \n",
    "+ Writing code is a good way to check your work on things. "
   ]
  }
 ],
 "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.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}