\n", "In todays lecture, we'll start with a reminder of **conditional execution** (``if``) and **loop** (``for``) in Python, and the datatype of **dictionaries**. Then we discuss various types of numbers in SageMath, such as **integers**, **rationals**, **algebraic numbers** and more. In the last part, we discuss **symbolic expressions** and how to use them to solve equations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Python warmup : conditional execution (if/else)\n", "Sometimes we want to perform some operations in our code (like computing the inverse of a matrix $A$) only if certain conditions are satisfied (the matrix $A$ is invertible), and maybe do something else otherwise (print a warning). This can be done in Python using the if/else construction:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A = matrix([[1,2],[3,5]]); A" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "if A.is_invertible():\n", " print('The inverse of A is:')\n", " print(A.inverse())\n", "else:\n", " print('A is not invertible!')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here the general pattern is:\n", "```\n", "if CONDITION:\n", " do_something()\n", " do_more_of_something()\n", "else:\n", " do_something_else()\n", " maybe_more_of_something_else()\n", "```\n", "Note that the indentation (using a ``Tab`` = 4 spaces) is important!\n", "\n", "Here ``CONDITION`` is an expressiong evaluating to a ``bool``, which is either ``True`` or ``False``. Basic ingredients for such conditions:\n", "* ``A == B``, ``A != B`` for checking equality (or not-equality)\n", "* ``A <= B``, ``A > B`` etc for comparisons of two values\n", "* Logical operations: ``Cond1 and Cond2``, ``Cond1 or Cond2``, ``not Cond1``\n", "\n", "It is possible to omit the ``else`` part, in which case nothing is done if ``CONDITION`` is not satisfied." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Given real parameters $p,q$ of the quadratic equation\n", "$$\n", "x^2 + p x + q = 0\n", "$$\n", "write some code which prints the set of solutions $x \\in \\mathbb{R}$ (which you have to compute yourself, since solving equations only comes later in the lecture).\n", "\n", "*Hint:* It's never too late in life to look at the [formula for the solutions of a general quadratic equation](https://en.wikipedia.org/wiki/Quadratic_formula)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution:** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that we can have an ``if``-block inside another ``if``- or ``else``-block, using double indentation (and so on):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A = -6\n", "\n", "if A.is_prime():\n", " if A == 2:\n", " print('A is an even prime')\n", " else:\n", " print('A is an odd prime')\n", "else:\n", " if A < 0 and (-A).is_prime():\n", " print('A is negative, but -A is a prime.')\n", " else:\n", " print('A is not a prime, since it factors as:')\n", " print(factor(A))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Python warmup: for-loops\n", "Sometimes we want to perform an operation for all $n$ in a range of values. This can be accomplished by a ``for``-loop. As an example, below we compute the sum of the numbers $n=0,1, \\ldots, 100$:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "count = 0\n", "for n in range(101):\n", " count = count + n\n", "print(count)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The general pattern is:\n", "```\n", "for n in ITERABLE:\n", " do_something()\n", "```\n", "Above, we have used ``range(N)`` as the ``ITERABLE``, which outputs the numbers $0,1, \\ldots, N-1$, which is why we had to take ``range(101)`` to sum from $0$ to $100$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Count for how many of the numbers $n=0,1, \\ldots, 2022$ the value $\\sin(n)$ is negative." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Similarly, we have the variations:\n", "* ``range(N0, N)`` for the numbers $N_0, N_0+1, \\ldots, N-1$,\n", "* ``range(N0, N, d)`` for the numbers $N_0, N_0+d, N_0+2d, \\ldots, N_0+k\\cdot d$, where $k$ is maximal such that $N_0+k\\cdot d

\n", "*Hint 1:* Since the number of digits of an integer roughly doubles when taking its square, we can estimate that $a$ has more decimal digits than the [number of atoms in the universe](https://en.wikipedia.org/wiki/Eddington_number). Keep in mind that the code you use for solving the exercise must run on a computer which is part of the universe!

\n", "*Hint 2:* If you have ignored Hint 1, you probably at some point want to click on ``Kernel -> Interrupt`` in the menu to stop the computation, and maybe also on ``Kernel -> Restart`` to clear your memory." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Factorization\n", "We can also compute the prime factorization of an integer:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "u = factor(99); u" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(u)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To actually extract the information from this factorization, to use it in further computations, the following conversions are useful:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "list(u)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dict(u)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Find the largest $m \\geq 1$ such that the number $100!$ is divisible by $2^m$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Conversely, we can look up the primes in the interval $[a,b-1]$ using ``primes(a,b)``:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "primes(4,19)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oops, this function returns a **generator**, i.e. an iterable that can be used in a ``for`` loop, without having to first compute all the numbers it will put out:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for p in primes(1,10^100):\n", " print(p)\n", " sleep(1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To just look at the numbers, you can convert this generator object into a list:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "list(primes(4,19))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Python int vs. SageMath Integer\n", "Remember the exercise from the first lecture to create a multiplication table of the integers from $1$ to $10$:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "matrix([[a*b for a in range(1,11)] for b in range(1,11)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see what happens instead if we wanted to create a *division* table:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "matrix([[a/b for a in range(1,11)] for b in range(1,11)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By golly, what happened? It turns out that the integers that ``range`` spits out are actually of type ``int`` in Python, and not of type ``Integer``:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for i in range(10):\n", " print(type(i))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Therefore, the division above is a division of ``int`` values, which returns a ``float``:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = int(3)/int(7); a" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To repair this, you can convert either numerator or denominator of the fraction into an ``Integer``:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "b = ZZ(int(3))/int(7); b" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(b)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Thus a nice and mathematically accurate division table can be obtained as follows:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "matrix([[ZZ(a)/b for a in range(1,11)] for b in range(1,11)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This type of conversion works more generally:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "c = 6/2\n", "(c,type(c))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "d = ZZ(c)\n", "(d,type(d))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "An integer $a$ is a perfect power if there exist integers $b,e$ with $e>1$ such that $a=b^e$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "[a.is_perfect_power() for a in [3, 9, 6]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For the integers $1, \\ldots, 20$ print line by line whether they are perfect powers or not, e.g. the output should start like this:\n", "```\n", "1 True\n", "2 False\n", "3 False\n", "4 True\n", "5 False\n", "...\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Rational numbers\n", "If you want to do an exact computation with real numbers (e.g. in linear algebra), it is best when you can stay inside the rational numbers, since they have an exact representation as a fraction. Many operations we saw for Integers above work analogously for Rationals:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = 24/9; a" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(a.numerator(), a.denominator())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "b = QQ(1.45); b" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "factor(b)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Some more useful functions (which also work for integers or real numbers):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = - 5/3\n", "floor(a) # rounding down" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ceil(a) # rounding up" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sign(a) # the sign" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "abs(a) # absolute value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Among the numbers of the form $p/q$ for $p,q \\in \\{1, \\ldots, 20\\}$, which is closest to $\\pi$?

\n", "*Hint:* Have a variable storing the best approximation you have so far, and when going through all numbers $p/q$ replace the current optimum if one of them comes closer." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Real and complex numbers\n", "We already saw that ``RR`` and ``CC`` are the fields of real and complex numbers, implemented with floating-point arithmetic. In particular, the computations here are no longer exact:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "piRR = RR(pi); piRR" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sin(2*piRR)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = CC(- pi * I); a" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "exp(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since we mostly talk about symbolic computations in this course, we won't go deeper into this topic for now, but here are some links where you can find more information:\n", "* [Computing with real numbers](https://fredrikj.net/math/ejcim2020_joh_en.pdf)\n", "* [Fixed and\n", "Arbitrary Precision Numerical Fields](https://doc.sagemath.org/pdf/en/reference/rings_numerical/rings_numerical.pdf)\n", "* [Sage Quickstart for Numerical Analysis](https://doc.sagemath.org/html/en/prep/Quickstarts/NumAnalysis.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Algebraic numbers\n", "One nice field in which exact computations are possible is the field $\\overline{\\mathbb{Q}}$ of **algebraic numbers**. These are complex numbers which are a zero of some polynomial with rational coefficients. The unique such polynomial of minimal degree and with leading coefficient $1$ is called the **minimal polynomial**." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "z = QQbar(3/2 + I); z" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "z.minpoly()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "z^2 - 3*z + 13/4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then we can do things like taking roots of an algebraic number. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "u = sqrt(z); u" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Even though below it is displayed as a decimal number, behind the scenes it still remembers its exact representation:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "u.minpoly() # for some reason this produces an error on the SageMath installation at the University" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then we can do fun things, like compute an expansion of a real algebraic number as a continued fraction:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "w = sqrt(QQbar(2)); w" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "continued_fraction(w)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This says that\n", "$$\n", "\\sqrt{2} = 1 + \\frac{1}{2 + \\frac{1}{2 + \\frac{1}{2+ \\ldots} }}\n", "$$\n", "If you haven't seen it, it's a fun exercise to prove this!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Compute the minimal polynomial and continued fraction of the golden ratio\n", "$$\n", "\\phi = \\frac{1 + \\sqrt{5}}{2}\\,.\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Finite fields\n", "Given a prime number $p$, there exists the **finite field**\n", "$$\\mathbb{F}_p = \\mathbb{Z}/p\\mathbb{Z}$$\n", "of integers modulo $p$, which has precisely $p$ elements. More generally, for a prime power $q=p^r$, $(r \\geq 1)$, there exists a unique field $\\mathbb{F}_q$ with $q$ elements. It is *not* given by $\\mathbb{Z}/q \\mathbb{Z}$ though! Instead it is given as an extension\n", "$$\n", "\\mathbb{F}_q = \\mathbb{F}_p[z]/(f(z)),\n", "$$\n", "where $z$ is a variable and $f \\in \\mathbb{F}_p[z]$ is an irreducible polynomial of degree $r$.\n", "\n", "This finite field can be created in SageMath using ``FiniteField(q)`` (or ``GF(q)`` for short)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "GF(9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we actually need to write elements of $\\mathbb{F}_q$, we can use the following line to specify the variable used in the definition:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "R.

\n", "*Hint:* There is a function in SageMath giving you a list of all prime powers $q$ up to $n-1$. Can you guess its name and confirm with Tab-completion?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Symbolic expressions\n", "We have already seen in some examples that SageMath can do computations involving formal variables. These happen in the so-called **Symbolic Ring**, which is denoted by ``SR`` in SageMath. \n", "\n", "### Creating and comparing symbolic expressions\n", "To get started, we declare some variable names using the function ``var``." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('a,b')\n", "f = (a+b)^3; f" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(f)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f in SR" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then we can ask to perform operations, like expanding the formula we entered above:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "expand(f)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also try to check whether two formulas are equivalent:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1 = (a^2+2*a*b+b^2)/(a+b); t1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t2 = a+b; t2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1 == t2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "bool(t1 == t2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is not restricted to algebraic equations:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "bool(sin(a)^2 + cos(a)^2 == 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Try to check the following identities, some of which are true and some of which are false. Which one does SageMath get wrong?\n", "$$\n", "a \\leq \\max(a,b)\n", "\\\\\n", "\\exp(a) \\cdot \\exp(b) = \\exp(a+b)\n", "\\\\\n", "\\frac{1}{\\frac{1}{a}-\\frac{1}{b}} = \\frac{a \\cdot b}{a - b}\n", "\\\\\n", "\\frac{1}{2}(a+b) \\leq \\max(a,b)\n", "\\\\\n", "(a+b+c)^2 = a^2 + b^2 + c^2 + 2 \\cdot(ab + ac + bc)\n", "\\\\\n", "\\sin\\left(\\frac{\\pi}{4}\\right) = \\frac{1}{\\sqrt{2}}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Substitution\n", "We can make variable substitutions as follows:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('a,b,c,d')\n", "f = a^2 + b*c; f" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f.subs({a:b, c:b+1})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the argument of ``f.subs`` is a dictionary, sending variables appearing in ``f`` to their new values. Alternatively, we can treat ``f`` as if it was a function, and call it (but specifying the names of the variables as follows):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f(a=2,b=3,c=4)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "f(a=d,b=d,c=d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Formal sums\n", "We can also evaluate some formal summations, e.g. the famous identity\n", "$$\n", "1 +2 + \\ldots + n = \\frac{n(n+1)}{2}\n", "$$\n", "Indeed, to compute\n", "$$\n", "\\sum_{a=a_0}^{a_1} f(a)\n", "$$\n", "we use ``sum(f,a,a0,a1)``, where ``a`` is a variable and ``f`` is again a symbolic expression." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('n')\n", "g = sum(a,a,1,n); g" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The answer is again a symbolic expression, so we can e.g. substitute some value for ``n`` or compute a further symbolic sum:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g.subs({n:100}) # The famous sum that Gauss allegedly computed in elementary school" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('m')\n", "sum(g,n,1,m)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solving equations\n", "Maybe you have wondered why writing ``f == g`` for two symbolic expressions does not immediately give either ``True`` or ``False``, but again a symbolic expression:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g == 5050" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(g == 5050)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The reason is that we can now use this expression to state an equation (or a system of equations) that we want to solve:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve(g == 5050, n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second argument is the variable for which we want to solve. To specify multiple equations (or inequalities) we give a list of these as the first argument of ``solve``:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve([g == 5050, n>=0], n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To get an output that can be used in further computations, we can specify the optional parameter ``solution_dict=True`` to obtain a list of dictionaries giving our solutions:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve([g == 5050, n>=0], n, solution_dict=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('a,b')\n", "L = solve(a^2 - b^2 == 0, b, solution_dict=True); L" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for l in L:\n", " print((a^2 - b^2).subs(l))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we can also solve for multiple variables:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var('y')\n", "solve([x*y==0, (x-1)*(y-1)==0],[x,y])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Solve the following (systems of) equalities for the variables $x,y,n,\\ldots$:\n", "$$\n", "x^3 + 2 x^2 - 21 x + 18 = 0, \\\\\n", "x^2 + p x + q = 0,\\\\\n", "\\sum_{k=0}^n 2^k = 4095\\\\\n", "x^2 + y^2 = 1, x + y = 1\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also add some [assumptions](https://doc.sagemath.org/html/en/reference/calculus/sage/symbolic/assumptions.html) about the variables:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solve(x^3==1, x, solution_dict=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "assume(x, 'real')\n", "solve(x^3==1, x, solution_dict=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is how we get rid of the assumptions again:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "forget(assumptions())\n", "solve(x^3==1, x, solution_dict=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Assignments" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Given a number $d \\in \\{2,3, \\ldots, 9\\}$ here are the rules of a game named $d$-Blup:\n", "\n", "The participants stand in a circle and count upwards starting from $1$, except that for every number either divisible by $d$ or ending on the digit $d$, they have to say \"Blup\" instead. If you say something wrong or take too long, you are out, and the others start again. \n", "\n", "A correct $3$-Blup would start as follows:\n", "```\n", "Player 1 : \"1\"\n", "Player 2 : \"2\"\n", "Player 3 : \"Blup\"\n", "Player 4 : \"4\"\n", "...\n", "Player 11 : \"11\"\n", "Player 12 : \"Blup\"\n", "Player 13 : \"Blup\"\n", "...\n", "```\n", "Given ``d``, write a program that prints the first 50 things the players need to say, i.e.\n", "```\n", "1\n", "2\n", "Blup\n", "4\n", "...\n", "```\n", "*Hint:* Recall that given integers ``a,b`` with ``b`` nonzero, you can compute the remainder of the division of ``a`` by ``b`` using ``a % b``." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution:** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "The [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture) states that for the function\n", "$$\n", "f : \\mathbb{Z}_{\\geq 1} \\to \\mathbb{Z}_{\\geq 1}, n \\mapsto \n", "\\begin{cases}\n", "3n+1 & \\text{for $n$ odd},\\\\\n", "n/2 & \\text{for $n$ even}\n", "\\end{cases}\n", "$$\n", "and any positive integer $n$, the sequence $n$, $f(n)$, $f(f(n))$, $\\ldots$ eventually hits the number $1$. Test the Collatz conjecture for the first $100$ integers.

\n", "*Hint:* The ``while``-loop\n", "```\n", "while CONDITION:\n", " do_something()\n", "```\n", "repeats the following code block until the ``CONDITION`` becomes ``False``." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "The Pólya conjecture states that given a natural number $n>1$, there are among the set\n", "$$\\{1, \\ldots, n\\}$$\n", "at least as many elements with an odd number of prime factors as elements with an even number of prime factors. Here prime factors are counted with multiplicity, i.e. $12 = 2 \\cdot 2 \\cdot 3$ has $3$ prime factors according to this definition.\n", "* Test the Pólya conjecture for the integers $2 \\leq n \\leq n_0$, for an $n_0$ of your choice.\n", "* Google the Pólya conjecture." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution:** (uncomment to see)

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise\n", "Given an integer $c \\geq 0$ let $T_c \\subseteq \\mathbb{Z}^2$ be the set of points in $\\mathbb{Z}^2$ contained in the triangle spanned by $(0,0), (0,c), (c,0)$. Or in other words\n", "$$\n", "T_c = \\{(x,y) \\in \\mathbb{Z}^2 : x,y \\geq 0, x+y \\leq c\\}.\n", "$$\n", "We claim that the function\n", "$$\n", "g : \\mathbb{Z}_{\\geq 0} \\to \\mathbb{Z}, c \\mapsto \\sum_{(x,y) \\in T_c} x \\cdot y\n", "$$\n", "is given by a polynomial in $c$. Compute this polynomial and check your result in a few cases." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Solution** (uncomment to see)

\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.1", "language": "sage", "name": "sagemath" }, "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.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }