recitation2.ipynb

{
 "metadata": {
  "name": "recitation2"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# CS1001.py\n",
      "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n",
      "# Recitation 2 - 7-11.3.2013\n",
      "## Last update: 24.4.2013 - added XKCD comic"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Getting input from the user\n",
      "You can get input from the user by calling the `input` function:\n",
      "\n",
      "```\n",
      "m = int(input(\"enter a positive integer to apply Collatz algorithm: \"))\n",
      "```\n",
      "\n",
      "Note that `input` returns a *string* and therefore you are responsible to convert it to the appopriate type."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Collatz Conjecture\n",
      "\n",
      "The [Collatz Conjecture](http://en.wikipedia.org/wiki/Collatz_conjecture) (also known as the *3n+1* conjecture) is the conjecture that the following process is finite for every natural number:\n",
      "> If the number $n$ is even divide it by two ($n/2$), if it is odd multiply it by 3 and add 1 ($3n+1$). Repeat this process untill you get the number 1.\n",
      "\n",
      "### Implementation\n",
      "We start with the \"Half Or Triple Plus One\" process:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "m = 100 # integer to apply the conjecture on\n",
      "\n",
      "n = m\n",
      "while n != 1:\n",
      "    print(n, end=\", \")\n",
      "    if n % 2 == 0:\n",
      "        n = n // 2\n",
      "    else:\n",
      "        n = 3 * n + 1\n",
      "print(1) # 1 was not printed\n",
      "print(m, \"is OK\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1\n",
        "100 is OK\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next we add another loop that will run the conjecture check on a range of numbers:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "limit = 10\n",
      "m = 1\n",
      "while m <= limit:\n",
      "    n = m\n",
      "    while n != 1:\n",
      "        if n % 2 == 0:\n",
      "            n = n // 2\n",
      "        else:\n",
      "            n = 3 * n + 1\n",
      "    print(m, \"is OK\")\n",
      "    m += 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 is OK\n",
        "2 is OK\n",
        "3 is OK\n",
        "4 is OK\n",
        "5 is OK\n",
        "6 is OK\n",
        "7 is OK\n",
        "8 is OK\n",
        "9 is OK\n",
        "10 is OK\n"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "When a loop goes over a simple range it is easier to use the `range` function with a `for` loop - and more robust against bugs:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for m in range(111, 98, -2):\n",
      "    print(m, end=\" \")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "111 109 107 105 103 101 99 "
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "start, stop = 99, 110\n",
      "for m in range(start, stop + 1):\n",
      "    n = m\n",
      "    while n != 1:\n",
      "        if n % 2 == 0:\n",
      "            n = n // 2\n",
      "        else:\n",
      "            n = 3 * n + 1\n",
      "    print(m, \"is OK\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "99 is OK\n",
        "100 is OK\n",
        "101 is OK\n",
        "102 is OK\n",
        "103 is OK\n",
        "104 is OK\n",
        "105 is OK\n",
        "106 is OK\n",
        "107 is OK\n",
        "108 is OK\n",
        "109 is OK\n",
        "110 is OK\n"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[![XKCD](http://imgs.xkcd.com/comics/collatz_conjecture.png)](http://xkcd.com/710/)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Lists\n",
      "\n",
      "Lists are sequences of values. \n",
      "\n",
      "Lists can contain a mix of types:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list = [3, 5.14, \"hello\", True, [5], range]\n",
      "print(mixed_list, type(mixed_list))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[3, 5.14, 'hello', True, [5], <class 'range'>] <class 'list'>\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lists are indexable, starting at 0:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[0]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "'hello'"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Negative indices are counted from the tail:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[-1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "builtins.range"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[-2] == mixed_list[2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lists can be sliced:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[1:3]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "[5.14, 'hello']"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[:2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "[3, 5.14]"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[1:]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "[5.14, 'hello', True, [5], builtins.range]"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[:-2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "[3, 5.14, 'hello', True]"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[:1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "[3]"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[7:8]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "[]"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list[7]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "IndexError",
       "evalue": "list index out of range",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-13-d8a75e7ae27c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mmixed_list\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m7\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
        "\u001b[1;31mIndexError\u001b[0m: list index out of range"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lists can be concatenated:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list + [1, 2, 3]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "But this doesn't change the list, but creates a new list:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "[3, 5.14, 'hello', True, [5], builtins.range]"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list = mixed_list + [1, 2, 3]\n",
      "mixed_list"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Some functions can be used on lists:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numbers = [10, 3, 2, 56]\n",
      "numbers"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "[10, 3, 2, 56]"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(numbers)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "71"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(['hello','world'])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "TypeError",
       "evalue": "unsupported operand type(s) for +: 'int' and 'str'",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-19-a479ce694266>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m'hello'\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'world'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
        "\u001b[1;31mTypeError\u001b[0m: unsupported operand type(s) for +: 'int' and 'str'"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "len(numbers)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 51,
       "text": [
        "4"
       ]
      }
     ],
     "prompt_number": 51
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "len(['hi','hello'])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(sorted(numbers))\n",
      "print(numbers)\n",
      "print(numbers.sort())\n",
      "print(numbers)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[2, 3, 10, 56]\n",
        "[10, 3, 2, 56]\n",
        "None\n",
        "[2, 3, 10, 56]\n"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lists are iterable:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mixed_list"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for item in mixed_list:\n",
      "    if type(item) == str:\n",
      "        print(item)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "hello\n"
       ]
      }
     ],
     "prompt_number": 55
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(len(mixed_list)):\n",
      "    print(i)\n",
      "    if type(mixed_list[i]) == str:\n",
      "        print(mixed_list[i])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "hello\n",
        "3\n",
        "4\n",
        "5\n",
        "6\n",
        "7\n",
        "8\n"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "i = 0 # important!\n",
      "while i < len(mixed_list) and type(mixed_list[i]) != int:\n",
      "    if type(mixed_list[i]) == str:\n",
      "        print(mixed_list[i])\n",
      "    i += 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9\n"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A list of numbers can be created using *list comprehension*.\n",
      "The syntax is:\n",
      "```\n",
      "[**statement** for **variable** in **iterable** if **condition**] \n",
      "```\n",
      "The `if **condition**` part is optional, the statement and the condition can use variable.\n",
      "\n",
      "Create a list of the squares of numbers between 1 and 10:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[x ** 2 for x in range(1, 11)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 29,
       "text": [
        "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Create a list of the square roots of odd numbers between 1 and 20:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[x ** 0.5 for x in range(1, 21) if x % 2 == 1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 30,
       "text": [
        "[1.0,\n",
        " 1.7320508075688772,\n",
        " 2.23606797749979,\n",
        " 2.6457513110645907,\n",
        " 3.0,\n",
        " 3.3166247903554,\n",
        " 3.605551275463989,\n",
        " 3.872983346207417,\n",
        " 4.123105625617661,\n",
        " 4.358898943540674]"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "l = []\n",
      "l += [1]\n",
      "l"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "[1]"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Grades problem\n",
      "\n",
      "Given a list of grades, count how many are above the average."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "grades = [33, 55,45,87,88,95,34,76,87,56,45,98,87,89,45,67,45,67,76,73,33,87,12,100,77,89,92]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "avg = sum(grades)/len(grades)\n",
      "above = 0\n",
      "for gr in grades:\n",
      "    if gr > avg:\n",
      "        above += 1\n",
      "        \n",
      "print(above, \"grades are above the average\", avg)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "15 grades are above the average 68.07407407407408\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Using *list comprehension*:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "avg = sum(grades)/len(grades)\n",
      "above = len([gr for gr in grades if gr > avg])\n",
      "        \n",
      "print(above, \"grades are above the average\", avg)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "15 grades are above the average 68.07407407407408\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Functions\n",
      "\n",
      "### Maximum and minimum"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def max2(a,b):\n",
      "    if a >= b:\n",
      "        return a\n",
      "    else:\n",
      "        return b\n",
      "\n",
      "def min2(a,b):\n",
      "    if a <= b:\n",
      "        return a\n",
      "    else:\n",
      "        return b\n",
      "    \n",
      "def max3(a,b,c):\n",
      "    if a >= b and a >= c:\n",
      "        return a\n",
      "    elif b >= a and b >= c:\n",
      "        return b\n",
      "    else:\n",
      "        return c\n",
      "\n",
      "def max3v2(a,b,c):\n",
      "    max_ab = max2(a,b)\n",
      "    return max2(max_ab,c)\n",
      "\n",
      "print(max2(5,10))\n",
      "print(min2(5,10))\n",
      "print(max3(5,10,10))\n",
      "print(max3v2(5,10,10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10\n",
        "5\n",
        "10\n",
        "10\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit max3(100,45,67)\n",
      "%timeit max3(45,67,100)\n",
      "%timeit max3v2(100,45,67)\n",
      "%timeit max3v2(45,67,100)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000000 loops, best of 3: 905 ns per loop\n",
        "1000000 loops, best of 3: 893 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 1.54 us per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 1.53 us per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* Which should be faster, `max3` or `max3v2`?\n",
      "* How would you implement `max4`?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Perfect numbers\n",
      "\n",
      "A perfect number is a number that is equal to the sum of its divisors:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_perfect(n):\n",
      "    '''\n",
      "    is_perfect(integer) -> bool\n",
      "    Return True iff n equals the sum of its divisors\n",
      "    '''\n",
      "    if n == sum(divisors(n)):\n",
      "        return True\n",
      "    else:\n",
      "        return False\n",
      "\n",
      "help(is_perfect)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Help on function is_perfect in module __main__:\n",
        "\n",
        "is_perfect(n)\n",
        "    is_perfect(integer) -> bool\n",
        "    Return True iff n equals the sum of its divisors\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def divisors(n):\n",
      "    '''\n",
      "    divisors(integer) -> list of integers\n",
      "    Return the proper divisors of n (numbers less than n that divide evenly into n).\n",
      "    '''\n",
      "    return [div for div in range(1,n) if n % div == 0]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "####Notes\n",
      "\n",
      "* Functions that return a boolean are named with `is_` as a prefix.\n",
      "* Use `'''` after the function definition to create function documentation\n",
      "* in `is_perfect` we can return the condition value instead of using the `if-else` clause:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_perfect(n):\n",
      "    '''\n",
      "    is_perfect(integer) -> bool\n",
      "    Return True iff n equals the sum of its divisors\n",
      "    '''\n",
      "    return n == sum(divisors(n))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 64
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(\"perfect numbers in range(1,1000)\\n\")\n",
      "print([n for n in range(1,1001) if is_perfect(n)])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "perfect numbers in range(1,1000)\n",
        "\n",
        "[6, 28, 496]"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 67
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Complexity\n",
      "\n",
      "We can write another version of `divisors` that is more efficient by iterating only on numbers between 1 and $\\frac{n}{2}$, but this function is more complex and bugs are crawling in it:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def divisors2(n):\n",
      "    divs = []\n",
      "    for m in range(2,round(n * 0.5)):#1 and n**0.5 will be handled separately. why?\n",
      "        if n % m == 0:\n",
      "            divs += [m, n // m]\n",
      "    divs += [1] # 1 surely divides n\n",
      "    return divs"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(divisors(6))\n",
      "print(divisors2(6))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 2, 3]\n",
        "[2, 3, 1]\n"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit -n 100 divisors(10**4)\n",
      "%timeit -n 100 divisors2(10**4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100 loops, best of 3: 6.83 ms per loop\n",
        "100 loops, best of 3: 3.33 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 78
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Fin\n",
      "This notebook is part of the [Extended introduction to computer science](http://tau-cs1001-py.wikidot.com/) course at Tel-Aviv University.\n",
      "\n",
      "The notebook was written using Python 3.2 and IPython 0.13.1.\n",
      "\n",
      "The code is available at <https://raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb>.\n",
      "\n",
      "The notebook can be viewed online at <http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb>.\n",
      "\n",
      "The notebooks is also available as a PDF at <https://github.com/yoavram/CS1001.py/blob/master/recitation2.pdf?raw=true>.\n",
      "\n",
      "This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}