{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Course 2: lists, loops, conditionals\n",
"====================================\n",
"\n",
"We first review quickly some of the material we introduced in the first worksheet:\n",
" - basic Python objects: booleans (`bool`), integers (`int`), floating point (`float`) and string (`str`)\n",
" - binary operations `+`, `*`, `-`, `/`, `//`, `%` and comparisons `==`, `!=`, `<`, `<=`, `>`, `>=`\n",
" - tab-completion and documentation\n",
" - using modules"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# floating point numbers (type 'float') have limited precision\n",
"print(1e308)\n",
"print(1e309)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# as a consequence some operations involving floats overflow\n",
"print(7.13 ** 154.37)\n",
"print(421.23 ** 125.2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# as another consequence addition is not commutative\n",
"1e100 + 1 - 1e100 == 1e100 - 1e100 + 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# integer (type 'int') have unlimited precision\n",
"103 ** 2543"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# operations on them are exact\n",
"10**100 + 1 - 10**100 == 10**100 - 10**100 + 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# when you have a Python object you can:\n",
"# - use tab-completion to get its list of methods\n",
"# - execute the cell with a '?' at the end to get the help"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"s = \"I am a string\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"s. # press Tab"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"s.upper? # press Shift-Enter"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# there are many features that are inside modules\n",
"# you need to use import to be able to use them"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import math\n",
"print(math.cos(math.pi / 4))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# using arange\n",
"# the syntax is arange(start, stop, step)\n",
"from numpy import arange\n",
"arange(0, 5, 1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"arange(0, 5, 2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this second worksheet, we will learn:\n",
" - how to manipulate objects of type `list` (creation, removing/adding elements, copy)\n",
" - how to go through the element of an iterable (`for` loop)\n",
" - how to do an operation under a certain condition (`if`, `elif`, `else`)\n",
" - how to repeat an action until a certain condition is verified (`while` loop)\n",
" - the operator `or`, `and` and `not`\n",
" - the functions `all` and `any`\n",
"\n",
"Lists\n",
"------\n",
"\n",
"A list is constructed with square brackets \"`[`\" and \"`]`\". We also access its elements using these."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l = [1, 34, 18] # a list of 3 elements\n",
"print(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l[0] # access element at position 0 (= first)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l[2] # access element at position 2 (= third)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l[-1] # access element at last position"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l[5] # the element at 6-th position (?!)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"len(l) # get the length of the list"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above comands also works for strings (and other \"list like\" Python objects):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"s = \"AIMS Rwanda\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"s[0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"s[-4]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"len(s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`str` and `list` are also similar with respect to addition and multiplication:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\"Rwa\" + \"nda\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"[1, 4] + [5, -4, 1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\"abc\" * 7"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"[1, 2, 3] * 7"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can run through the elements of a list (or a string) using for loops. There are two ways of using `for` loop as shown below:\n",
"- to perform an operation on each element of the list (e.g. `print`)\n",
"- to build another list from the previous one (this is called \"list comprehension\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"l = [1, 'haha', 18.3]\n",
"s = \"AIMS\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for x in l:\n",
" print(x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for x in s:\n",
" print(x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l = [1, 2, 3]\n",
"l2 = [x**2 for x in l]\n",
"print(l2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"s = 'abc'\n",
"l3 = [c*2 for c in s]\n",
"print(l3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- Create a list with the odd numbers from 11 to 19 included\n",
"- Make a for loop in order to compute their product\n",
"- Can you modify your loop to compute at the same time their sum?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- construct a list `my_list` that contains all integers from `1` to `16` included\n",
"- build a list that contains there cubes of elements of `my_list`\n",
"- build a list that contains the square root of elements of `my_list`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"But contrarily to string lists can be modified"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l = [0,1,2]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"l[0] = 25\n",
"print(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"s = 'abc'"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"s[0] = 'd'\n",
"print(s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Lists can also be modified through methods\n",
"\n",
"- adding terms with `append`, `extend` and `insert`\n",
"- removing terms with `clear` and `pop`\n",
"\n",
"Exercise\n",
"---------\n",
"- Look at the documentation of the 5 methods of list mentioned above\n",
"- What is the value of the list `l` after the evaluation of these lines\n",
"```python\n",
"l = [0] * 3 + [1, 2] * 2\n",
"l.append(5)\n",
"l.append(2)\n",
"l.pop(2)\n",
"l.insert(0, 2)\n",
"l.insert(2, l.pop(3))\n",
"```\n",
" Check your answer by copying, pasting and executing the above code."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Construct a list which contains once the number 1, twice the number 2, 3 times the number 3, up to 10 times the number 10."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`range`\n",
"-------\n",
"If you want to iterate over integers there is a useful function called `range`. It is a function that can be called with either one, two or three arguments:\n",
"\n",
" - `range(stop)`: all integers from `0` to `stop-1` included\n",
" - `range(start, stop)`: all integers from `start` to `stop-1`\n",
" - `range(start, stop, step)`: all integers from `start` to `stop` and with a difference of `step` between each consecutive terms\n",
" \n",
"**Exercise:**\n",
"Copy/paste the codes below in 3 code cells and before executing it try to guess what will be the output\n",
"\n",
"1 -\n",
"```python\n",
"for x in range(5):\n",
" print(x)\n",
"```\n",
"\n",
"2 - \n",
"```python\n",
"for x in range(12, 20, 3):\n",
" print(x)\n",
"```\n",
"\n",
"3 - \n",
"```python\n",
"for x in range(30, -1, -10):\n",
" print(x)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** What is the value of $$\\sum_{k = 1}^{20} k^k$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Recall that the Fibonacci sequence is defined by $F_0 = F_1 = 1$ and $F_{n+1} = F_n + F_{n-1}$. What is the 100-th Fibonacci number?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Could you make a list containing the odd integers from 1 to 201 included?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- make the list of the first $30$ Fibonacci numbers $F_n$\n",
"- make the list of the quantity $F_n^2 - F_{n-1} F_{n+1}$ for $n=1,2,...,28$\n",
"- What do you see? Could you prove it?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Let $S_0$ be the standard unit square with vertices $(0,0)$, $(1,0)$, $(1,1)$ and $(0,1)$. We define the square $S_n$ obtained as joining the middle of each side of $S_{n-1}$.\n",
"- Draw on the same pictures $S_0$, $S_1$, $S_2$, ... up to $S_{10}$.\n",
"- Do the same starting from another quadrilateral which is not regular\n",
"- Do the same starting from a pentagon (five vertices)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** what does the following code?\n",
"```python\n",
"x = 1.0\n",
"for i in range(10):\n",
" x += (x + 2.0 / x) / 2.0\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the following exercise, you will need to use nested loops. That is construction of the form\n",
"```python\n",
"for x in l1:\n",
" for y in l2:\n",
" do something\n",
"```\n",
"**Exercise:**\n",
"- Using the recurrence relation satisfied by the binomial numbers $\\binom{n+1}{k+1} = \\binom{n}{k} + \\binom{n}{k+1}$ compute the list $\\binom{20}{0}, \\binom{20}{1}, \\ldots, \\binom{20}{20}$.\n",
"- What is the sum of these 21 binomial numbers?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Note:** `range` constructs an object of a strange nature (can you find its type?). Abstractly, it looks like a list: you can access elements with square brackets and compute the length\n",
"```python\n",
"r = range(0, 1523, 2)\n",
"print(r[10])\n",
"print(r[-5])\n",
"print(len(r))\n",
"```\n",
"And as we have seen you can run a for loop on it (we say that it is *iterable*). However, the `range` object is not expanded in memory! As a consequence, the list of commands below is fine (but will run forever)\n",
"```python\n",
"j = 0\n",
"for i in range(2**64):\n",
" j = j + i\n",
"```\n",
"Note however that the list of integers from $0$ to $2^{64}$ is much bigger than the RAM available in your computer. This second example will freeze your computer (eating all the memory)\n",
"```python\n",
"l = list(range(2**64))\n",
"```\n",
"Execute the first of the two above list of commands. You can check that the code continue executing (look at the star that appears in the blue box on the left). To interrupt the execution you can use the menu on the top of the page: \"Kernel -> Interrupt\". Better to not execute the second example!"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`if`/`elif`/`else`\n",
"------------------\n",
"\n",
"We have just learned loop basics. We will now see another construction which allows to perform an instruction only when a certain condition is fullfilled. These are constructed with the keywords `if`, `elif` and `else`. There are several way of using the construction\n",
"```python\n",
"if condition:\n",
" instruction # executed if condition is realized\n",
"```\n",
"or\n",
"```python\n",
"if condition:\n",
" instruction1 # executed if condition is realized\n",
"else:\n",
" instruction2 # executed if condition is not realized\n",
"```\n",
"or possibly\n",
"```python\n",
"if condition1:\n",
" instruction1 # executed if condition1 is realized\n",
"elif condition2:\n",
" instruction2 # executed if condition1 is not realized but condition2 is\n",
"elif instruction3:\n",
" instruction3 # executed if condition 1 and 2 are not realized but condition3 is\n",
"```\n",
"The possible number of intermediate `elif` is unlimited. The final `else` is optional.\n",
"\n",
"This is well illustrated if you want to compute the sign of a real number `x` (that is `-1` if `x` is negative, `0` if x is zero and `1` if x is positive)\n",
"```python\n",
"if x > 0:\n",
" s = 1\n",
"elif x == 0:\n",
" s = 0\n",
"else:\n",
" s = -1\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** we consider the following substitution on lists $1 \\mapsto 12, 2 \\mapsto 13, 3 \\mapsto 1$. Starting from $1$, applying repeatedly this substitution we obtain $12$, $1213$, $1213121$, etc. Write the first 15 iterations of this procedure. (*hint: you need to write a for loop with a if statement contained inside*)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** Starting from an integer value $x_0$ the Collatz sequence is define by $x_{n+1} = \\frac{x_n}{2}$ if $x_n$ is even and $x_{n+1} = 3 x_n + 1$ otherwise. Starting from $x_0 = 2^{10} + 1$ what are the first 20 terms of its Collatz sequence? How will it continues?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is also possible to use the `if` construction in list comprehension. For example, the following code\n",
"```python\n",
"[x for x in range(20) if x**2 < 30]\n",
"```\n",
"builds the list of integer $x$ in $\\{0, 1, \\ldots, 19\\}$ that satisfies the condition $x^2 < 30$. You can see that it is very similar to the notation from set theory $$\\{x \\in \\{0, 1, \\ldots, 19\\}: x^2 < 30\\}.$$\n",
"\n",
"**Exercise:** Build the list of Fibonacci numbers $F_n$ with $n$ less than 50 so that $F_n$ is congruent to 1 mod 7."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`while` loop\n",
"------------\n",
"\n",
"There is second way of repeating actions: while loops. A certain action is repeated while a certain condition is satisfied.\n",
"\n",
"**Exercise:** Can you guess what does the following loop do?\n",
"```python\n",
"n = 18600435\n",
"z = 0\n",
"while n % 3 == 0:\n",
" n //= 3\n",
" z += 1\n",
"```\n",
"What are the values of `n` and `z` at the end?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:**\n",
"- what is the first Fibonacci number larger than $2^{2^{2^{2^2}}}$?\n",
"- how many digits does it have?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** It is a famous conjecture that starting from any positive integer $x_0$ the associated Collatz sequence is ultimately periodic $1 \\mapsto 4 \\mapsto 2 \\mapsto 1 \\mapsto \\ldots$. Check this conjecture for the first 10000 integers."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Constructing complex conditions: `or`, `and`, `not`, `any`, `all`\n",
"-----------------------------------------------------------------\n",
"\n",
"In the `if`, `elif` or `while` constructions the condition can be any Python object. For example the following is valid Python syntax\n",
"```python\n",
"if \"I am nice\":\n",
" print(\"hello\")\n",
"```\n",
"What happens is that the Python string `\"I am nice\"` is implictely converted into a boolean (`True` or `False`). And you can obtain this boolean by executing `bool(a_python_object)`. What is it in the above example?\n",
"\n",
"**Exercise:**\n",
"- execute the following command `[bool(i) for i in range(-10, 10)]`\n",
"- what do you think about conversion of integers to booleans?\n",
"- what will be the output of the following commands\n",
"```python\n",
"i = 5\n",
"while i:\n",
" if i - 3:\n",
" print i\n",
" i = i - 1\n",
"```\n",
"check by copy, paste, execute.\n",
"- check that a Python floating point converts to `True` if and only if it is not zero\n",
"- check that a Python list (or string) converts to `True` if and only if it is not empty"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With this boolean conversions in mind, we now introduce some operations to build more complex conditions\n",
"\n",
"| command | description |\n",
"|-----------|-----------------------------------------------------------------|\n",
"| `a or b` | returns `a` if it converts to `True` otherwise returns `b` |\n",
"| `a and b` | returns `a` if it converts to `False` otherwise returns `b` |\n",
"| `not x` | returns `True` if `x` converts to `False` and `False` otherwise |\n",
"\n",
"**Exercise:**\n",
"Based on the definition above what is the result of each command below\n",
"```python\n",
"1 or 0\n",
"0 or 1\n",
"0 and 3 == 0 and 2\n",
"1 and [] == 1 and 5\n",
"not []\n",
"```\n",
"check by copy, paste, execute."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** What does the following code do?\n",
"```python\n",
"l = [1, 12, 5, 14, -6, 13, 19, -4, 10]\n",
"l2 = [x for x in l if x > 0 and not x < 10 or x == 14]\n",
"```\n",
"Check your answer by copy, paste, execute."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we see two more constructions with the functions `any` and `all`. They allow to check for a whole range of conditions. For example\n",
"```python\n",
"all(x % 3 == 1 for x in l)\n",
"```\n",
"checks that if all elements in a list `l` are congruent to 1 modulo 3. While\n",
"```python\n",
"any(x > 2 for x in l)\n",
"```\n",
"checks that if one of the element in the list `l` is larger than 2. Note that the syntax is very similar to the one used for list comprehension. Note also that these are the very same thing as the quantifier $\\forall$ (for all) and $\\exists$ (exists) in mathematics.\n",
"\n",
"**Exercise:**\n",
"For each of the command below tell what will be the output\n",
"```python\n",
"all([1, 2, 3])\n",
"all(range(-10, 10))\n",
"any(x % 5 == 0 for x in [6, 7, 8, 9])\n",
"all([])\n",
"any([])\n",
"```\n",
"Check by copy, paste, execute."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise:** What is the value of the list `l` at the end of the execution of the code below\n",
"```python\n",
"l = [0, 1]\n",
"while any(x < 4 for x in l):\n",
" l = [2*i + 1 for i in l if i % 5 != 3]\n",
" l.append(l[-2] + l[-1])\n",
"```\n",
"Check your answer by copy, paste and execute."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Extra exercises\n",
"---------------\n",
"Below are two more complicated exercises. You have learned enough Python to do them. However, do not worry if you do not succeed since it is delicate to design the algorithm."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (++):**\n",
"- Print all possible permutations of the list `[0, 1, 1, 2, 2, 2, 3, 3, 3, 3]`\n",
"- How many are they?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (++):**\n",
"A partition of a positive integer `n` is a weakly decreasing list of positive integers whose sum is `n`. For example the partitions of 4 are in reverse lexicographic order\n",
"\n",
" [4]\n",
" [3, 1]\n",
" [2, 2]\n",
" [2, 1, 1]\n",
" [1, 1, 1, 1]\n",
"\n",
"- Print all partitions of 10.\n",
"- how many are they?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Copyright (C) 2016 Vincent Delecroix <vincent.delecroix@u-bordeaux.fr>\n",
"\n",
"This work is licensed under a Creative Commons Attribution-NonCommercial 4.0\n",
"International License (CC BY-NC-SA 4.0). You can either read the\n",
"[Creative Commons Deed](https://creativecommons.org/licenses/by-nc-sa/4.0/)\n",
"(Summary) or the [Legal Code](https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode)\n",
"(Full licence)."
]
}
],
"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.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}