Introductory SageMath Course – Lecture 2
We start with a recap of last time and a few exercises. After that we learn how to write simple conditional expressions, loops, functions and some advanced list handling. The worksheet end with exercises.
Recap of list creation.
Here are some examples and exercises to practice list creation learnt in the first lecture.
︡01ec6d67-296d-4761-84b2-dcf33459257a︡{"html": "Introductory SageMath Course – Lecture 2
\r\nWe start with a recap of last time and a few exercises. After that we learn how to write simple conditional expressions, loops, functions and some advanced list handling. The worksheet end with exercises.
\r\n\r\nRecap of list creation.
\r\nHere are some examples and exercises to practice list creation learnt in the first lecture.
"}︡ ︠1d6014b7-2a11-40db-be10-54afa6d4cff0︠ c # The first ten squares L = [i^2 for i in range(0, 10)] L ︡d73d0ada-a70b-488b-9872-9dadbec7750f︡{"html":"Exercises.
L1. Create a list of length 20 whose kth element is $1+2+\cdots+ k$.
L2. Create a list of length 10 whose kth element is $\int_0^1 x^k dx$.
L3. Create a list of length 50 whose kth element is the numerical value of $\frac{\sqrt{k}\binom{2k}{k}}{2^{2k}}$.
Programming constructs
Loops
We can use two kinds of loops: 'for' and 'while'. The general advice is that for loops are used for repeating the same action for elements of an interval, list, set etc. In contrast, while loops should be chosen when we are repeating an action until a condition finally fails (or succeeds). We illustrate both kinds of loops with examples.
Sage (and python) uses indentation (starting lines with empty spaces, tabs) to denote where a loop ends. Note the difference between the following two examples. Also note the colon at the end of the first line.
︡5a16a7e6-81ec-4160-8810-b7f885f2fa45︡{"html": "Exercises.
\r\nL1. Create a list of length 20 whose kth element is $1+2+\\cdots+ k$.
\r\nL2. Create a list of length 10 whose kth element is $\\int_0^1 x^k dx$.
\r\nL3. Create a list of length 50 whose kth element is the numerical value of $\\frac{\\sqrt{k}\\binom{2k}{k}}{2^{2k}}$.
\r\n\r\nProgramming constructs
\r\nLoops
\r\nWe can use two kinds of loops: 'for' and 'while'. The general advice is that for loops are used for repeating the same action for elements of an interval, list, set etc. In contrast, while loops should be chosen when we are repeating an action until a condition finally fails (or succeeds). We illustrate both kinds of loops with examples.
\r\nSage (and python) uses indentation (starting lines with empty spaces, tabs) to denote where a loop ends. Note the difference between the following two examples. Also note the colon at the end of the first line.
"}︡ ︠841b101b-3236-4201-8fa4-7d573dfbaa7cs︠ for i in [1..6]: gkjk jfjj hfjhj jfjf ︡f3b36528-3d18-4f31-9e42-e4cf5d15d73d︡{"stderr":"Error in lines 1-5\nTraceback (most recent call last):\n File \"/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py\", line 1013, in execute\n exec compile(block+'\\n', '', 'single') in namespace, locals\n File \"\", line 2, inConditionals.
Checking whether a condition holds can be done by using 'if'. The indented part following 'if' is only executed when the condition holds (indentation rules are similar to loops). Optionally, we can specify what should happen when the condition fails, using the keyword 'else'. There is also an 'elif' keyword, see the examples.
︡9be72f07-f6a3-4599-8572-2c6a41a28064︡{"html": "Conditionals.
\r\nChecking whether a condition holds can be done by using 'if'. The indented part following 'if' is only executed when the condition holds (indentation rules are similar to loops). Optionally, we can specify what should happen when the condition fails, using the keyword 'else'. There is also an 'elif' keyword, see the examples.
"}︡ ︠f28121b3-f3c0-4e79-8c08-5e7d59d2f7dfs︠ # Count primes up to 1000 (remember, prime_pi does this already). cnt = 0 for i in range(1, 1001): if is_prime(i): cnt += 1 cnt ︡9c5c0dfd-4915-480a-ac84-06262d3b9480︡{"html":"Functions.
When you have to perform the same calculation for several different values (e.g. counting the primes up to n for several values of n), it is beneficial to make an abstraction, and make the calculation into a named function. This is done by the keyword 'def'. The result (the output) of a function is called the return value and is specified by the keyword 'return'. It is generally a good idea to avoid duplication of code in programs and use abstraction for repeating tasks.
︡416b0c43-9cc6-40c2-a168-1275621b7b90︡{"html": "Functions.
\nWhen you have to perform the same calculation for several different values (e.g. counting the primes up to n for several values of n), it is beneficial to make an abstraction, and make the calculation into a named function. This is done by the keyword 'def'. The result (the output) of a function is called the return value and is specified by the keyword 'return'. It is generally a good idea to avoid duplication of code in programs and use abstraction for repeating tasks.
"}︡ ︠4d15a595-1c24-4cf0-9ba0-70c7684a8bb4s︠ def my_prime_counter(n): cnt = 0 for i in range(1, n+1): if is_prime(i): cnt += 1 return cnt ︡8d9c6460-3610-4e34-a1a5-adb0f3ed4353︡{"done":true}︡ ︠b6af70d2-61fc-4894-9adc-2e59465ca818s︠ my_prime_counter(1000) ︡e735eb50-f568-462d-978f-ed590e135d87︡{"html":"Functions can also come handy when we define matrices or graphs, for example. We create a matrix whose entry in the (i, j) position is the greatest common divisor of i and j. Then we create a matrix with $M_{ij} = ij + i + j$ using a newly defined function.
︡66c23d04-06a7-417f-a6f6-e3fff7c5951b︡{"html": "Functions can also come handy when we define matrices or graphs, for example. We create a matrix whose entry in the (i, j) position is the greatest common divisor of i and j. Then we create a matrix with $M_{ij} = ij + i + j$ using a newly defined function.
"}︡ ︠f6c71aa3-5d54-4e85-9224-4ff3c0b974a5s︠ M = matrix(5, 5, gcd) M ︡c9014871-63e3-42fe-8f6d-cc213e89f522︡{"html":"We now create a graph with vertex set $\{2, 3, \ldots 9\}$. We connect two vertices if the corresponding numbers are relatively prime.
︡ef101b4e-65ea-4024-977e-fdce0285b2f7︡{"html": "We now create a graph with vertex set $\\{2, 3, \\ldots 9\\}$. We connect two vertices if the corresponding numbers are relatively prime.
"}︡ ︠aaeee61d-776f-4a55-9509-60ee7127c55cs︠ def is_rel_prime(i, j): return gcd(i, j) == 1 G = Graph([Set([2..9]), is_rel_prime]) ︡02e7785d-08ce-49cc-a356-c5e3db568047︡{"done":true}︡ ︠1ddd70f4-88e6-4f29-90d4-32a49186d3ces︠ G.show() ︡5dd6be17-4d1a-4e69-8bab-b4312c55dbff︡{"file":{"filename":"/home/user/.sage/temp/project-9e3e1eca-35f2-42f2-b2da-e4e4e739e6dd/110/tmp_d8yQrc.svg","show":true,"text":null,"uuid":"413f71d4-eee3-4461-ae73-5572e5fed010"},"once":false}︡{"done":true}︡ ︠05f2e306-3c2b-41cf-a84e-fc3368c612cbs︠ G.chromatic_number() ︡6b6bdc56-2d74-4dc6-aad3-5b6c6181c110︡{"html":"One may wonder whether it is really needed to create a function just for using it once in building a graph or matrix. The answer is no: we have the possibility to use unnamed functions called lambda expressions. See the examples below.
︡a70b98d6-9d0b-457f-9631-3abb3a1c2f19︡{"html": "One may wonder whether it is really needed to create a function just for using it once in building a graph or matrix. The answer is no: we have the possibility to use unnamed functions called lambda expressions. See the examples below.
"}︡ ︠fa97d729-70f6-44f3-83b2-0fda404dc583s︠ G = Graph([Set([1..9]), lambda i,j: (i+j)%2 == 1]) G.show() ︡6c941d18-ad2f-410b-95a0-5ad9400319af︡{"file":{"filename":"/home/user/.sage/temp/project-9e3e1eca-35f2-42f2-b2da-e4e4e739e6dd/110/tmp_bgaUGV.svg","show":true,"text":null,"uuid":"6d987293-240b-41df-b0c0-8142cc2092a7"},"once":false}︡{"done":true}︡ ︠ef824edb-e492-4b56-8b8a-c1a37fbfdd19s︠ G.is_bipartite() ︡80fa652d-d165-4f7d-8a98-7c812ba55043︡{"html":"List manipulation
There are commands that help you manipulate lists without explicitely having to use loops or fucntions. We present a few examples using map, filter, zip and reduce. Using 'map', one applies a function to all elements, 'filter' selects elements satisfying a condition. Both can be simulated by list constructions.
︡f137dadb-6ab6-4635-8c8f-31b1f383f93c︡{"html": "List manipulation
\nThere are commands that help you manipulate lists without explicitely having to use loops or fucntions. We present a few examples using map, filter, zip and reduce. Using 'map', one applies a function to all elements, 'filter' selects elements satisfying a condition. Both can be simulated by list constructions.
"}︡ ︠9c71b1d9-9074-42b4-a67f-87499c1720bes︠ L = [1..10] map(is_prime, L) ︡bbb024ec-3e15-4789-a0ad-e1c0ec6029a6︡{"html":"The function 'reduce' can accumulate a calculation through a list. Summing, multplying elements of a list is an example, but for these we already have the commands 'sum' and 'prod'. An example could be the following problem: given a list of pairs, calculate the sum of pairwise products. E.g. [[3, 4], [5, 7], [1, 18]] would give 12+35+18 = 65. We show a loop-based solution and one using 'reduce'.
︡1f5bf9a3-0229-4b18-bfa5-bad85dd62b0b︡{"html": "The function 'reduce' can accumulate a calculation through a list. Summing, multplying elements of a list is an example, but for these we already have the commands 'sum' and 'prod'. An example could be the following problem: given a list of pairs, calculate the sum of pairwise products. E.g. [[3, 4], [5, 7], [1, 18]] would give 12+35+18 = 65. We show a loop-based solution and one using 'reduce'.
"}︡ ︠50cb8a17-d84e-4720-8ffd-949101ad3363s︠ L = [[3, 4], [5, 7], [1, 18]] s = 0 for pair in L: s += prod(pair) s ︡8466e450-5499-4843-be55-1280ab477559︡{"html":"Exercises.
1. Sum up the primes up to 10000.
2. Write a function for summing up primes up to n.
3. Sum up primes of the form $17k + 1$ up to n with a function.
4. Create a function that calculates the number of positive divisors of a positive integer using its prime factorization. Look up the formula on the web. (Hint: list(factor(n)) gives the factorization in a digestible form for a computer)
5. Create a complete graph on 6 vertices.
6. Create a 4-dimensional hypercube graph.
7. Let $S = \{1, 2, 3, 4, 5\}$. Create a graph that has the two-element subsets of $S$ as vertices. Two vertices are connected if they are disjoint. Do you recognize this graph?
7. Let $p$ be the first prime after $10^{15}$ and let $a_n$ be a reursive sequence defined by $a_0 = 7$, $a_1 = 2$ and $a_n = a_{n-1} + a_{n-2}$ for $n\geq 3$. Calculate the millionth element of the sequence modulo $p$.
7*. Let $p$ be the first prime after $10^{15}$ and let $a_n$ be a reursive sequence defined by $a_0 = 7$, $a_1 = 2$ and $a_n = a_{n-1} + a_{n-2}$ for $n\geq 3$. Calculate the 4398046511175th element of the sequence modulo $p$.
︡97a0deec-beff-4966-a13e-cfbe4804b246︡{"html": "
Exercises.
\n1. Sum up the primes up to 10000.
\n2. Write a function for summing up primes up to n.
\n3. Sum up primes of the form $17k + 1$ up to n with a function.
\n4. Create a function that calculates the number of positive divisors of a positive integer using its prime factorization. Look up the formula on the web. (Hint: list(factor(n)) gives the factorization in a digestible form for a computer)
\n5. Create a complete graph on 6 vertices.
\n6. Create a 4-dimensional hypercube graph.
\n7. Let $S = \\{1, 2, 3, 4, 5\\}$. Create a graph that has the two-element subsets of $S$ as vertices. Two vertices are connected if they are disjoint. Do you recognize this graph?
\n7. Let $p$ be the first prime after $10^{15}$ and let $a_n$ be a reursive sequence defined by $a_0 = 7$, $a_1 = 2$ and $a_n = a_{n-1} + a_{n-2}$ for $n\\geq 3$. Calculate the millionth element of the sequence modulo $p$.
\n7*. Let $p$ be the first prime after $10^{15}$ and let $a_n$ be a reursive sequence defined by $a_0 = 7$, $a_1 = 2$ and $a_n = a_{n-1} + a_{n-2}$ for $n\\geq 3$. Calculate the 4398046511175th element of the sequence modulo $p$.
\n"}︡ ︠75bdb7be-7dd0-4b65-b165-6a82284d36c0s︠ memo = {} def fibo(n): if n in memo: return memo[n] elif n < 2: memo[n] = n return n else: memo[n] = fibo(n-1) + fibo(n-2) return memo[n] ︡d4e3b865-bab0-480c-882b-3ebbdf7eedef︡{"done":true}︡ ︠bf0af0c6-f6cb-46c1-ad9b-c0eb5848beacs︠ def fibvec(n): if n == 0: return [1,0] else: prev = fibvec(n-1) a = prev[0] b = prev[1] return [a+b, a] ︡ac45f4b2-706d-4e7b-9af6-35031da7c848︡{"done":true}︡ ︠5d2bf88a-0151-46a4-98f7-d389745dcddbs︠ fibvec(100) ︡e483a56f-d23c-455a-8719-8c8784cacf3c︡{"stdout":"[573147844013817084101, 354224848179261915075]\n"}︡{"done":true}︡ ︠00a222b1-cb06-4fcc-ac31-82cd02bb7b15︠