{ "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", "- M\u00e9lodie Lapointe\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 `]`) such\n", "as:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "l = [1, \"two\", -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[4] # 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": [ "### 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": [ "[x for x in range(1,11) for i in range(x)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A for loop is a control flow that will allow to repeat some instructions\n", "for all elements of an *iterable* such as list.:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "l = [1, \"hello\", 3]\n", "for x in l:\n", " print(x)" ] }, { "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", " for y in l2:\n", " print(x, y, 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": [ "for i in srange(1,101):\n", " show(i.factor())" ] }, { "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": [ "from sage.symbolic.integration.integral import indefinite_integral\n", "x = var('x')\n", "for i in [sin(x),cos(x),tan(x),log(x),exp(x),sinh(x),cosh(x)]:\n", " show(indefinite_integral(i,x))" ] }, { "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": [ "for i in range(1,21):\n", " show(indefinite_integral(x^i,x))" ] }, { "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": [ "l = []\n", "for i in range(1,11):\n", " for j in range(i):\n", " l.append(i)\n", "l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Repeat it with 100 instead of 10" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "l = []\n", "for i in range(1,11):\n", " for j in range(i):\n", " l.append(i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.5\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": [ { "data": { "text/plain": [ "*\n", "**\n", "***\n", "****\n", "*****\n", "******" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i in range(1,7):\n", " print('*'*i)" ] }, { "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": [ { "data": { "text/plain": [ "*\n", "**\n", "***\n", "****\n", "*****\n", "******\n", "*****\n", "****\n", "***\n", "**\n", "*" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i in range(1,12):\n", " print('*'*min(i,12-i))" ] }, { "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": [ { "data": { "text/plain": [ " *\n", " ***\n", " *****\n", " *****\n", " ***\n", " *" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i in range(1,12,2):\n", " m = min(i,12-i)\n", " print (' '*(4-int((m+1)/2)) + ('*'*m))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.6\n", "\n", "What is the value of\n", "\n", "$$\\sum_{k = 1}^{20} k^k$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "106876212200059554303215024L" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum([x^x for x in range(1,21)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Solve $Euler problem 48 $.\n", "\n", "> sage: str(sum(\\[x^x for x in range(1,100)\\]))\\[-10:\\] '9027641920'\n", "\n", "Note that Python `tuple` (constructed with parenthesis) and Python\n", "`string` (constructed with quotes `'` or `\"`) behave the same with\n", "respect to many operations:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1 = (0, \"hello\", -2/3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1[0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1[-1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1 * 3" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 = \"I am in\"\n", "s2 = \"Saint-Flour\"\n", "s1 + \" \" + s2" ] }, { "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": [ { "data": { "text/plain": [ "696" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L_int = [ZZ(x[:-1]) for x in L]\n", "total_size = sum(L_int)\n", "print(total_size)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "87/8" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "average = total_size/len(L)\n", "print(average)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "median = sorted(L_int)[ZZ(len(L)/2)]\n", "print(median)" ] }, { "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": [ { "data": { "text/plain": [ "{'8K': 32, '28K': 9, '16K': 8, '32K': 1, '12K': 6, '40K': 1, '24K': 3, '4K': 0, '20K': 3}" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "size = {}\n", "compteur = 0\n", "valeur = L_int[0]\n", "for i in sorted(L_int):\n", " if i == valeur:\n", " compteur += 1\n", " else:\n", " size[str(i)+'K'] = compteur\n", " compteur = 1\n", " valeur = i\n", "print(size)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "('8K', 6)\n", "('28K', 1)\n", "('16K', 3)\n", "('32K', 1)\n", "('12K', 8)\n", "('40K', 1)\n", "('24K', 9)\n", "('4K', 32)\n", "('20K', 3)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i in set(L):\n", " print(i,L.count(i))" ] }, { "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": [ { "data": { "text/plain": [ "12K 12K 12K 12K 12K 12K 12K 12K 16K 16K 16K 20K 20K 20K 24K 24K 24K 24K 24K 24K 24K 24K 24K 28K 32K 40K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 8K 8K 8K 8K 8K 8K" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = ''\n", "for i in L:\n", " s+= i + ' '\n", "print(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Can you construct the same string by increasing size?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 8K 8K 8K 8K 8K 8K 12K 12K 12K 12K 12K 12K 12K 12K 16K 16K 16K 20K 20K 20K 24K 24K 24K 24K 24K 24K 24K 24K 24K 28K 32K 40K " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = ''\n", "for i in sorted(L,key=lambda y: ZZ(y[:-1])):\n", " s += i+ ' '\n", "print s" ] }, { "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": [ { "data": { "text/plain": [ "40K 32K 28K 24K 24K 24K 24K 24K 24K 24K 24K 24K 20K 20K 20K 16K 16K 16K 12K 12K 12K 12K 12K 12K 12K 12K 8K 8K 8K 8K 8K 8K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K 4K " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = ''\n", "for i in sorted(L,key=lambda y: ZZ(y[:-1]),reverse=True):\n", " s += i + ' '\n", "print s" ] }, { "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", "### 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": [ "points = [(0,0),(1,0),(1,1),(0,1),(0,0)]\n", "p = line2d(points)\n", "for i in range(1,11):\n", " new_points = []\n", " for j in range(4):\n", " new_points.append(((points[j][0]+points[j+1][0])/2,(points[j][1]+points[j+1][1])/2))\n", " new_points.append(new_points[0])\n", " p += line2d(new_points)\n", " points = new_points\n", "plot(p)" ] }, { "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": [ "points = [(0,0),(2,0),(3,2),(0,1),(0,0)]\n", "p = line2d(points)\n", "for i in range(1,11):\n", " new_points = []\n", " for j in range(4):\n", " new_points.append(((points[j][0]+points[j+1][0])/2,(points[j][1]+points[j+1][1])/2))\n", " new_points.append(new_points[0])\n", " p += line2d(new_points)\n", " points = new_points\n", "plot(p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Do the same starting from a pentagon (five vertices)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "points = [(0,0),(1,0),(2,0.5),(1,1),(0,1),(0,0)]\n", "p = line2d(points)\n", "for i in range(1,11):\n", " new_points = []\n", " for j in range(5):\n", " new_points.append(((points[j][0]+points[j+1][0])/2,(points[j][1]+points[j+1][1])/2))\n", " new_points.append(new_points[0])\n", " p += line2d(new_points)\n", " points = new_points\n", "plot(p)" ] }, { "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": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'5537376230'" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "str(sum(L))[:10]" ] }, { "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": [ { "data": { "text/plain": [ "[462, 442, 1068, 667, 1654, 314, 598, 351, 514, 688, 1322, 123, 1134, 247, 302, 222, 1210, 307]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i in range(0,len(l),2):\n", " l[i] = l[i]*2\n", "print l" ] }, { "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": [ { "data": { "text/plain": [ "['January', 31, 'February', 28, 'March', 31, 'April', 30, 'May', 31, 'June', 30, 'July', 31, 'August', 31, 'September', 30, 'October', 31, 'November', 30, 'December', 31]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t3 = []\n", "for i in range(len(t1)):\n", " t3.append(t2[i])\n", " t3.append(t1[i])\n", "print t3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.14\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": [ { "data": { "text/plain": [ "[1, 20, 190, 1140, 4845, 15504, 38760, 77520, 125970, 167960, 184756, 167960, 125970, 77520, 38760, 15504, 4845, 1140, 190, 20, 1]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "binomial = [1]\n", "for i in range(20):\n", " binomial.append(1)\n", " for j in range(i,0,-1):\n", " binomial[j] = binomial[j-1] + binomial[j]\n", "print binomial" ] }, { "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": [ { "data": { "text/plain": [ "[1, 1048575, 1742343625, 181509070050, 3791262568401, 26585679462804, 82310957214948, 132511015347084, 123272476465204, 71187132291275, 26826851689001, 6833042030178, 1204909218331, 149304004500, 13087462580, 809944464, 34952799, 1023435, 19285, 210, 1]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "stirling = [1]\n", "for i in range(20):\n", " stirling.append(1)\n", " for j in range(i,0,-1):\n", " stirling[j] = stirling[j-1] + (j+1)*stirling[j]\n", "print stirling" ] }, { "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": [ "l = [n^2 for n in srange(1, 11)]\n", "print(l)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.15\n", "\n", "Construct the same list of squares using a $for$ loop and the method\n", "$.append()$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "l = []\n", "for i in srange(1,11):\n", " l.append(i^2)\n", "print l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.16\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": [ "[5^n for n in srange(1,20)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 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": [ { "data": { "text/plain": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fib = [0,1]\n", "for i in range(50):\n", " fib.append(fib[-1] + fib[-2])\n", "print fib" ] }, { "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": [ "for i in range(1,49):\n", " print fib[i]*fib[i] - fib[i-1]*fib[i+1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Using a for loop, print the values of $F_{2n} - F_{n}^2 - F_{n-1}^2$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for i in range(1,25):\n", " print fib[2*i] - fib[i]*fib[i] - fib[i-1]*fib[i-1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What do you remark? Could you prove it?\n", "\n", "### Exercise 2.18\n", "\n", "What happens when you try to modify a string or a tuple?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s = 'ssss'\n", "s[1] = 'j'\n", "t = (1,2,3,4)\n", "t[1] = 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.19\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": [ { "data": { "text/plain": [ "1074" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L = [[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,16,70,92],[41,41,26,56,83,40,80,70,33],[41,48,72,33,47,32,37,16,94,29],[53,71,44,65,25,43,91,52,97,51,14],[70,11,33,28,77,73,17,78,39,68,17,57],[91,71,52,38,17,14,91,43,58,50,27,29,48],[63,66,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]\n", "t = [0]\n", "for ligne in L:\n", " for i in range(len(ligne),0,-1):\n", " if i == 1:\n", " t[i-1] = t[i-1] + ligne[i-1]\n", " elif i == len(ligne):\n", " t.append(t[i-2] + ligne[i-1])\n", " else:\n", " t[i-1] = ligne[i-1]+max(t[i-1],t[i-2])\n", "print max(t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2.20 (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": [ { "data": { "text/plain": [ "[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 0, 2, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 2, 0, 3, 1, 3, 2, 3, 3, 3, 4, 3, 5, 3, 6, 3, 7, 3, 8, 3, 9, 3, 0, 4, 1, 4, 2, 4, 3, 4, 4, 4, 5, 4, 6, 4, 7, 4, 8, 4, 9, 4, 0, 5, 1, 5, 2, 5, 3, 5, 4, 5, 5, 5, 6, 5, 7, 5, 8, 5, 9, 5, 0, 6, 1, 6, 2, 6, 3, 6, 4, 6, 5, 6, 6, 6, 7, 6, 8, 6, 9, 6, 0, 7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7, 6, 7, 7, 7, 8, 7, 9, 7, 0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 5, 8, 6, 8, 7, 8, 8, 8, 9, 8, 0, 9, 1, 9, 2, 9, 3, 9, 4, 9, 5, 9, 6, 9, 7, 9, 8, 9, 9, 9, 0, 0, 1]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "C = []\n", "for i in srange(1,101):\n", " l = i.digits()\n", " l.reverse()\n", " C.extend(l)\n", "print C" ] }, { "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 48](https://projecteuler.net/problem=40)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "210" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "C = []\n", "for i in srange(1,1000001):\n", " l = i.digits()\n", " l.reverse()\n", " C.extend(l)\n", "solution = 1\n", "for i in [10^i for i in srange(7)]:\n", " solution = solution*C[i-1]\n", "print solution" ] }, { "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", "## 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 }