{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\def\\CC{\\bf C}\n",
"\\def\\QQ{\\bf Q}\n",
"\\def\\RR{\\bf R}\n",
"\\def\\ZZ{\\bf Z}\n",
"\\def\\NN{\\bf N}\n",
"$$\n",
"# Chapter 2: Lists and for loops\n",
"\n",
"Authors \n",
"- Vincent Delecroix\n",
"\n",
"License \n",
"CC BY-SA 3.0\n",
"\n",
"In the first tutorial, you learnt how to call Sage functions and solve\n",
"basic problems. To do more advanced computations you will need to learn\n",
"a bit of programming. The aim of this tutorial is to introduce you to\n",
"some basic Python programming: `list` that is one of the builtin Python\n",
"data structures and `for` loops.\n",
"\n",
"For reference you can have a look at\n",
"[pydoc-datastructures]\n",
"and\n",
"[pydoc-controlflow].\n",
"\n",
"## Manipulating lists\n",
"\n",
"In Python, lists are constructed using square brackets (`[` and `]`)\n",
"such as:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1, Partition([3,1,1]), \"hello\", -5.7, Primes()]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As you can notice, the data contained in a list is not necessarily\n",
"homogeneous. To access elements of a list, one also uses square\n",
"brackets:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[0] # the first element"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[2] # the third elements"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[-1] # the last element"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l[17] # this is out of range"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"An important function is `len` that returns the length of the list:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"len(l) # number of elements in l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Given a list `l` and a non-negative integer `n` the operation `l * n`\n",
"duplicates `n` times the list `l` :"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l * 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Given two lists `l1` and `l2` the operation `l1 + l2` is the\n",
"concatenation of `l1` and `l2` :"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[1, 2, 3] + [4, 5, 6]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, note that lists can be nested:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"ll = [ [1, 2, [3, 4], [5, [6, 7], 8]], [[9]] ]\n",
"print(ll)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Could you guess what is the value of `ll[0][2]`?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.1\n",
"\n",
"Construct the list that contains 1 time 1, 2 times 2, 3 times 3, ..., 10\n",
"times 10 (i.e. `[1, 2, 2, 3, 3, 3, ..., 10]`)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## For loop and range\n",
"\n",
"A for loop is a control flow that will allow to repeat some instructions\n",
"for all elements of an *iterable* (such as a list):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1, Partition([3,1,1]), 3, Primes()]\n",
"for x in l:\n",
" print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Most mathematical sets are also iterable:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for p in Partitions(10):\n",
" print(p, p.conjugacy_class_size())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can have more than one instructions inside a for loop:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1, 2, 3, 4, 5]\n",
"for x in l:\n",
" y = 3 * x^ - 2\n",
" print(y)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And it is possible to nest them:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l1 = [1, 2, 3]\n",
"l2 = [4, 7, 13]\n",
"for x in l1:\n",
" x = 2 - x + 1\n",
" for y in l2 * x:\n",
" print(x, y)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Often you might want to perform a for loop for integers in a given\n",
"range. To do so there are the functions `range` (from Python) and\n",
"`srange` (from Sage).:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(10):\n",
" print(i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in srange(10):\n",
" print(i)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The difference between `range` and `srange` is that `range` produces\n",
"Python integer while `srange` produces Sage integers. You can compare:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(10):\n",
" print(i.is_prime())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in srange(10):\n",
" print(i.is_prime())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For both `range` and `srange` there are three possible syntaxes\n",
"\n",
"- `range(stop)` : integers from `0` to `stop-1` included\n",
"- `range(start, stop)` : integers from `start` to `stop-1`\n",
"- `range(start, stop, step)` : integers from `start` to `stop` and\n",
" with a difference of `step` between each consecutive terms\n",
"\n",
"### Exercise 2.2\n",
"\n",
"Write a for loop which prints the factorization for each integer from 1\n",
"to 100."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.3\n",
"\n",
"Write a for loop which prints the primitive of the functions $\\sin(x)$,\n",
"$\\cos(x)$, $\\tan(x)$, $\\log(x)$, $\\exp(x)$, $\\sinh(x)$ and $\\cosh(x)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a for loop which prints the derivates of the functions\n",
"$f_n(x) = x^n$ for all values of $n$ from $1$ to $20$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.4\n",
"\n",
"Redo exercise 2.1 using a `for` loop"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Repeat it with 100 instead of 10"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.5\n",
"\n",
"What is the value of\n",
"\n",
"$$\\sum_{k = 1}^{20} k^k$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Solve [Euler problem 48](https://projecteuler.net/problem=48)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Strings and tuples\n",
"\n",
"Strings and tuples are two other Python builtin data structures that\n",
"share a lot with lists. Here are a string and a tuple:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = \"This is a string\"\n",
"t = (1, Partition([3,1]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"They behave the same with respect to many operations:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(s[0])\n",
"print(t[0])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(s[-1])\n",
"print(t[-1])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(s * 3)\n",
"print(t * 3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s1 = \"I am in\"\n",
"s2 = \"Bonn\"\n",
"print(s1 + \" \" + s2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = (1, 2)\n",
"t2 = (3, 4, 5)\n",
"print(t1 + t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.6\n",
"\n",
"Write some code that displays the following figure using a loop"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print('*')\n",
"print('**')\n",
"print('***')\n",
"print('****')\n",
"print('*****')\n",
"print('******')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write some code that displays the following figure using a loop:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print('*')\n",
"print('**')\n",
"print('***')\n",
"print('****')\n",
"print('*****')\n",
"print('******')\n",
"print('*****')\n",
"print('****')\n",
"print('***')\n",
"print('**')\n",
"print('*')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write some code that displays the following figure using a loop:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(' *')\n",
"print(' ***')\n",
"print(' *****')\n",
"print('*******')\n",
"print(' *****')\n",
"print(' ***')\n",
"print(' *')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.7\n",
"\n",
"Here is a list describing the size of 64 files:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"L = [\"12K\", \"12K\", \"12K\", \"12K\", \"12K\", \"12K\", \"12K\", \"12K\", \"16K\",\n",
"\"16K\", \"16K\", \"20K\", \"20K\", \"20K\", \"24K\", \"24K\", \"24K\", \"24K\", \"24K\",\n",
"\"24K\", \"24K\", \"24K\", \"24K\", \"28K\", \"32K\", \"40K\", \"4K\", \"4K\", \"4K\", \"4K\",\n",
"\"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\",\n",
"\"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\", \"4K\",\n",
"\"4K\", \"4K\", \"4K\", \"4K\", \"8K\", \"8K\", \"8K\", \"8K\", \"8K\", \"8K\"] "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compute the total size of the files, their average and the median"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint*: to convert a string `s` like `\"12\"` into an integer simply do\n",
"`ZZ(s)`)\n",
"\n",
"How many files are there of each size? (you might want to look the\n",
"available method on list object)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Construct the string that is the concatenation of each file size\n",
"separated by a space"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can you construct the same string by increasing size?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint*: you might want to sort the list first... use tab-completion to\n",
"find the appropriate list method to do this)\n",
"\n",
"And by decreasing size?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint*: have a look at the documentation of the method you used for\n",
"sorting in the previous question)\n",
"\n",
"## Three more advanced exercises\n",
"\n",
"### Exercise 2.8\n",
"\n",
"Let $S_0$ be the unit square with vertices $(0,0)$, $(1,0)$, $(1,1)$ and\n",
"$(0,1)$. We define the square $S_n$ obtained by joining the middle of\n",
"each side of $S_{n-1}$.\n",
"\n",
"Draw on the same pictures $S_0$, $S_1$, $S_2$, ... up to $S_{10}$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Do the same graphics starting from another quadrilateral which is not\n",
"regular"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Do the same starting from a pentagon (five vertices)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.9\n",
"\n",
"What does the following code?:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = 1.0\n",
"for i in range(10):\n",
" x = (x + 2.0 / x) / 2.0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What is the difference with:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = 1\n",
"for i in range(10):\n",
" x = (x + 2 / x) / 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.10\n",
"\n",
"Solve [Euler problem 13](https://projecteuler.net/problem=13). To\n",
"simplify the exercise, the list of numbers has been created in the\n",
"following cell:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"L = [37107287533902102798797998220837590246510135740250,\n",
"46376937677490009712648124896970078050417018260538,\n",
"74324986199524741059474233309513058123726617309629,\n",
"91942213363574161572522430563301811072406154908250,\n",
"23067588207539346171171980310421047513778063246676,\n",
"89261670696623633820136378418383684178734361726757,\n",
"28112879812849979408065481931592621691275889832738,\n",
"44274228917432520321923589422876796487670272189318,\n",
"47451445736001306439091167216856844588711603153276,\n",
"70386486105843025439939619828917593665686757934951,\n",
"62176457141856560629502157223196586755079324193331,\n",
"64906352462741904929101432445813822663347944758178,\n",
"92575867718337217661963751590579239728245598838407,\n",
"58203565325359399008402633568948830189458628227828,\n",
"80181199384826282014278194139940567587151170094390,\n",
"35398664372827112653829987240784473053190104293586,\n",
"86515506006295864861532075273371959191420517255829,\n",
"71693888707715466499115593487603532921714970056938,\n",
"54370070576826684624621495650076471787294438377604,\n",
"53282654108756828443191190634694037855217779295145,\n",
"36123272525000296071075082563815656710885258350721,\n",
"45876576172410976447339110607218265236877223636045,\n",
"17423706905851860660448207621209813287860733969412,\n",
"81142660418086830619328460811191061556940512689692,\n",
"51934325451728388641918047049293215058642563049483,\n",
"62467221648435076201727918039944693004732956340691,\n",
"15732444386908125794514089057706229429197107928209,\n",
"55037687525678773091862540744969844508330393682126,\n",
"18336384825330154686196124348767681297534375946515,\n",
"80386287592878490201521685554828717201219257766954,\n",
"78182833757993103614740356856449095527097864797581,\n",
"16726320100436897842553539920931837441497806860984,\n",
"48403098129077791799088218795327364475675590848030,\n",
"87086987551392711854517078544161852424320693150332,\n",
"59959406895756536782107074926966537676326235447210,\n",
"69793950679652694742597709739166693763042633987085,\n",
"41052684708299085211399427365734116182760315001271,\n",
"65378607361501080857009149939512557028198746004375,\n",
"35829035317434717326932123578154982629742552737307,\n",
"94953759765105305946966067683156574377167401875275,\n",
"88902802571733229619176668713819931811048770190271,\n",
"25267680276078003013678680992525463401061632866526,\n",
"36270218540497705585629946580636237993140746255962,\n",
"24074486908231174977792365466257246923322810917141,\n",
"91430288197103288597806669760892938638285025333403,\n",
"34413065578016127815921815005561868836468420090470,\n",
"23053081172816430487623791969842487255036638784583,\n",
"11487696932154902810424020138335124462181441773470,\n",
"63783299490636259666498587618221225225512486764533,\n",
"67720186971698544312419572409913959008952310058822,\n",
"95548255300263520781532296796249481641953868218774,\n",
"76085327132285723110424803456124867697064507995236,\n",
"37774242535411291684276865538926205024910326572967,\n",
"23701913275725675285653248258265463092207058596522,\n",
"29798860272258331913126375147341994889534765745501,\n",
"18495701454879288984856827726077713721403798879715,\n",
"38298203783031473527721580348144513491373226651381,\n",
"34829543829199918180278916522431027392251122869539,\n",
"40957953066405232632538044100059654939159879593635,\n",
"29746152185502371307642255121183693803580388584903,\n",
"41698116222072977186158236678424689157993532961922,\n",
"62467957194401269043877107275048102390895523597457,\n",
"23189706772547915061505504953922979530901129967519,\n",
"86188088225875314529584099251203829009407770775672,\n",
"11306739708304724483816533873502340845647058077308,\n",
"82959174767140363198008187129011875491310547126581,\n",
"97623331044818386269515456334926366572897563400500,\n",
"42846280183517070527831839425882145521227251250327,\n",
"55121603546981200581762165212827652751691296897789,\n",
"32238195734329339946437501907836945765883352399886,\n",
"75506164965184775180738168837861091527357929701337,\n",
"62177842752192623401942399639168044983993173312731,\n",
"32924185707147349566916674687634660915035914677504,\n",
"99518671430235219628894890102423325116913619626622,\n",
"73267460800591547471830798392868535206946944540724,\n",
"76841822524674417161514036427982273348055556214818,\n",
"97142617910342598647204516893989422179826088076852,\n",
"87783646182799346313767754307809363333018982642090,\n",
"10848802521674670883215120185883543223812876952786,\n",
"71329612474782464538636993009049310363619763878039,\n",
"62184073572399794223406235393808339651327408011116,\n",
"66627891981488087797941876876144230030984490851411,\n",
"60661826293682836764744779239180335110989069790714,\n",
"85786944089552990653640447425576083659976645795096,\n",
"66024396409905389607120198219976047599490197230297,\n",
"64913982680032973156037120041377903785566085089252,\n",
"16730939319872750275468906903707539413042652315011,\n",
"94809377245048795150954100921645863754710598436791,\n",
"78639167021187492431995700641917969777599028300699,\n",
"15368713711936614952811305876380278410754449733078,\n",
"40789923115535562561142322423255033685442488917353,\n",
"44889911501440648020369068063960672322193204149535,\n",
"41503128880339536053299340368006977710650566631954,\n",
"81234880673210146739058568557934581403627822703280,\n",
"82616570773948327592232845941706525094512325230608,\n",
"22918802058777319719839450180888072429661980811197,\n",
"77158542502016545090413245809786882778948721859617,\n",
"72107838435069186155435662884062257473692284509516,\n",
"20849603980134001723930671666823555245252804609722,\n",
"53503534226472524250874054075591789781264330331690]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Modifying lists\n",
"\n",
"Here are three ways to modify an already existing list `l` :\n",
"\n",
"- `l[i] = j` : modify the element at position `i` to become `j`\n",
"- `l.append(j)` : append the element `j` at the end of `l`\n",
"- `l.pop()` : remove the last element of the list `l` and return it\n",
"- `l.extend(ll)` : add to `l` the content of the iterable `ll`\n",
"\n",
"(there is also `l.insert(i, j)` that we will not use)\n",
"\n",
"### Exercise 2.11\n",
"\n",
"What is the value of the list `l` at the end of the execution:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1, 2, 3]\n",
"l.append(-1)\n",
"l[1] = 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(think about it before executing the lines)\n",
"\n",
"What is the value of the list `l` at the end of the execution:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1]\n",
"l.extend(l)\n",
"l.extend(l)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(think about it before executing the lines)\n",
"\n",
"### Exercise 2.12\n",
"\n",
"Given the following list of integers:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [231, 442, 534, 667, 827, 314, 299, 351, 257, 688, 661, 123,\n",
"567, 247, 151, 222, 605, 307]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Modify it so that each number at an even position is replaced by its\n",
"double"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.13\n",
"\n",
"Let the following lists:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
"t2 = ['January', 'February', 'March', 'April', 'May', 'June',\n",
"'July', 'August', 'September', 'October', 'November', 'December']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using `t1` and `t2` create a new list `t3` containing all elements of\n",
"the two lists alternating them in such a way that each Month is followed\n",
"by the corresponding number of days, that is,\n",
"`['Janvier',31,'F\u00e9vrier',28,'Mars',31, etc...]`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.14\n",
"\n",
"What happens when you try to modify a string or a tuple?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.15\n",
"\n",
"Using the recurrence relation satisfied by the binomial numbers\n",
"\n",
"$$\\binom{n+1}{k} = \\binom{n}{k} + \\binom{n}{k-1}$$\n",
"\n",
"compute the list $\\binom{20}{0}, \\binom{20}{1}, \\ldots, \\binom{20}{20}$.\n",
"In order to do that you need to start from the list $[1]$ and design a\n",
"loop that constructs successively $[1, 1]$, then $[1, 2, 1]$, then\n",
"$[1, 3, 3, 1]$, etc. (It can be done using only one list.)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Modify your loop to compute the Stirling numbers of the second kind that\n",
"satisfies\n",
"\n",
"$$S(n+1, k) = k S(n, k) + S(n, k-1)$$\n",
"\n",
"with initial conditions $S(0, 0) = 1$ and $S(n, 0) = S(0, n) = 1$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## List comprehension\n",
"\n",
"List comprehension is a flexible way to build list. To build the list of\n",
"squares $n^2$ from $n=1$ to $n=10$ one can do:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"squares = [n^2 for n in srange(1, 11)]\n",
"print(squares)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.16\n",
"\n",
"Construct the same list `squares` using a $for$ loop and the method\n",
"$.append()$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.17\n",
"\n",
"Construct the list of powers of 5 for all values of exponents in the\n",
"interval $[1,20]$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## More exercises\n",
"\n",
"### Exercise 2.17\n",
"\n",
"The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$ and for all\n",
"$n \\geq 2$, $F_n = F_{n-1} + F_{n-2}$.\n",
"\n",
"Make the list of the first $50$ Fibonacci numbers $F_n$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using a for loop, print the values of $F_n^2 - F_{n-1} F_{n+1}$ for $n$\n",
"between $1$ and $48$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using a for loop, print the values of $F_{2n-1} - F_{n}^2 - F_{n-1}^2$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What do you remark? Could you prove it?\n",
"\n",
"### Exercise 2.19\n",
"\n",
"Solve [Euler problem 5](https://projecteuler.net/problem=5): what is the\n",
"smallest positive number that is divisible by all of the numbers from 1\n",
"to 20?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.20\n",
"\n",
"Solve the Euler problem [18](https://projecteuler.net/problem=18) and\n",
"[67](https://projecteuler.net/problem=67) about \"maximum sum paths\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.21 (Champernowne constant)\n",
"\n",
"The [Champernowne\n",
"constant](https://en.wikipedia.org/wiki/Champernowne_constant) is the\n",
"real number obtained by concatenating all natural numbers in base 10\n",
"\n",
"$$C = 0.1234567891011121314151617181920212223\\ldots$$\n",
"\n",
"The *Champernowne word* is the sequence of digits. Using a for loop,\n",
"construct the begining of the Champernowne word obtained by\n",
"concatenating the integers from $1$ to $100$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*hint*: use the method `n.digits()` of Sage integers together with the\n",
"method `l.extend(ll)` on lists)\n",
"\n",
"Then solve [Euler problem 40](https://projecteuler.net/problem=40)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# edit here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Further comments\n",
"\n",
"To learn more about iterators (that can be thought as \"lazy lists\") and\n",
"in particular how to construct them, you can have a look at the Sage\n",
"thematic tutorial on Comprehensions\n",
"[sagett-comprehensions].\n",
"\n",
"There is a difference between Python 2 and Python 3 concerning the\n",
"`range` function. In Python 2, `range` produces a list of integers while\n",
"in Python 3 it produces an iterable (but the list is not created). For\n",
"example the following would not work in Python 3:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = range(10)\n",
"l[0] = 3 # broken in Python 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The simple work around is to use `list(range(10))` when you actually\n",
"want the list of integers.\n",
"\n",
"## References\n",
"\n",
"pydoc-controlflow \n",
"\n",
"\n",
"pydoc-datastructures \n",
"\n",
"\n",
"sagett-comprehensions \n",
""
]
}
],
"metadata": {
"kernelspec": {
"display_name": "sagemath",
"name": "sagemath"
}
},
"nbformat": 4,
"nbformat_minor": 2
}