{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\"drawing\"\n", "

Experimental Mathematics Using SageMath — AIMS-ZA-2024-25

\n", "\n", "\n", "## Instructors: \n", "\n", "\n", "* **Evans Ocansey**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Day 06 — New Experiments: Sum of Squares and Plotting \n", "\n", "[comment]: <> (

Day 02 — Introduction to SageMath: A Mathematics Software for All

)\n", "\n", "\n", "\n", "\n", "The outline of the this notebook is as follows:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Table of Contents: \n", "* [ ] [Reviewing the Frobenius Problem](#reviewing-the-frobenius-problem)\n", " * [Last Thoughts on the Conductor](#last-thoughts-on-the-conductor)\n", "* [ ] [New Experiment — Sum of Squares ](#new-experiment-sum-of-squares)\n", " * [Exploratory Questions — Sum of Squares ](#exploratory-questions-sum-of-squares)\n", "* [ ] [More Plotting and Graphics in Two Dimensions](#more-plotting-and-graphics-in-two-dimensions)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reviewing the Frobenius Problem \n", "Our motivational problem is the following: \n", " - Given positive integers $a$ and $b$, what numbers $m$ can be written in the form $a\\,x+b\\,y$, where $x,\\,y \\in \\mathbb{Z}_{\\ge0}$? \n", "\n", "Given positive integers $a$ and $b$ if there is a positive integer $c$, with $c = a\\,x + b\\,y$ such that for all positive integers $n \\ge c$, there are non-negative integers $x$ and $y$ with $n = a\\,x + b\\,y$, then $c$ is called the *conductor* of $a$ and $b$. In other words, $c_{\\{a,b\\}}$ is the smallest positive integer that can be written as $a\\,x + b\\,y$ such that all positive integers greater than or equal to $c_{\\{a,b\\}}$ are also writable. We will denote the conductor of $a$ and $b$ by $c_{\\{a,b\\}}$. \n", "On the other hand, the largest positive integer $f$ that can not be written as $f = a\\,x + b\\,y$ is called the *Frobenius number* of $a$ and $b$. We will denote this by $f_{\\{a,b\\}}$.\n", "\n", "It has already led to several related questions. Hopefully you were able to explore the following questions and made interesting _conjectures_.\n", "\n", " - Given two positive integers $a$ and $b$, how many numbers can not be written as $a\\,x + b\\,y$ with $x,\\,y\\in\\mathbb{Z}_{\\ge0}$?\n", " - If $a$ is even and $b$ is odd, what is the Frobenius number? \n", " - If $a$ is even and $b$ is even, what is the Frobenius number? \n", " - If $a$ is odd and $b$ is odd, what is the Frobenius number? \n", " - If $a$ and $b$ are prime numbers, what is the Frobenius number? \n", " - Given two positive integers $a$ and $b$, can we find a formula or some other means of computing the Frobenius number?\n", " - If $a,\\, b \\in \\mathbb{Z}_{>0}$ and $\\gcd(a, b) \\neq 1$, does the Frobenius number exist?\n", "\n", "Here are some questions that we possed together in class: \n", "- Given that either $a = 1$ or $b = 1$, but not both, is it possible to define a Frobenius number, $f_{\\{a,b\\}}$ and a conductor, $c_{\\{a,b\\}}$? If so what is it?\n", "- If $a$ and $b$ have a common factor greater than $1$, does there exist a Frobenius number, $f_{\\{a,b\\}}$ and a conductor, $c_{\\{a,b\\}}$?\n", "- If $a$ is even and $b$ is odd what is the Frobenius number and conductor?\n", "- If $f_{\\{a,b\\}}=\\infty$ for $a,\\,b \\in \\mathbb{Z}_{>0}$, is it always true that the conductor, $c_{\\{a,b\\}}$ is also infinity. How about the vice-versa of this statement?\n", "- Is there a case such that given $a,\\,b \\in \\mathbb{Z}_{>0}$ there exists a Frobenius number, $f_{\\{a,b\\}}$ but not a conductor, $c_{\\{a,b\\}}$?\n", "- What is the existence condition for a Frobenius number, $f_{\\{a,b\\}}$ and a conductor, $c_{\\{a,b\\}}$ given $a, b\\in\\mathbb{Z}_{>0}$?\n", "- If $a,b\\in\\mathbb{Z}_{>0}$ and there exist a Fronbenius number, $f_{\\{a,b\\}}$ and a conductor, $c_{\\{a,b\\}}$, is there a relationship between:\n", " - $f_{\\{a,\\,b\\}}$ and $c_{\\{a,\\,b\\}}$?\n", " - $f_{\\{a,\\,b\\}}$, $a$, and $b$?\n", " - $c_{\\{a,\\,b\\}}$, $a$, and $b$?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Last Thoughts on the Conductor \n", "\n", "Are there more questions we can explore about the Frobenius problem?\n", "\n", "- What if instead of two positive integers $a$ and $b$, we have more than $3$ positive integers $a, b, c$? \n", "\n", "**Question**: Is there such a thing as a *conductor* or a *Frobenius number* for a set of _three_ integers?\n", "That is, is there a conductor for numbers of the form $n=5x+8y+7z$, for the set $\\{5,8,7\\}$?\n", "\n", " * Well, what about for $\\{3,4,7\\}$?\n", " * Okay, what about $\\{3,4,6\\}$?\n", " * Ah, but what about $\\{3,4,5\\}$?\n", "\n", "**Question**: We observed from our experiments with two positive integers $a$ and $b$ that the existence criterion for the Frobenius number $f_{\\{a,b\\}}$ is that $a$ and $b$ must be coprime, i.e., $\\gcd(a, b)=1$. Would this criterion also hold for the case of three positive integers: $a$, $b$, and $c$?\n", "\n", "\n", "Do you think there a formula for the Frobenius number $f_{\\{a,b\\}}$, and the conductor $c_{\\{a,b\\}}$?  What about for bigger sets of integers, for example, for three positive integers $a$, $b$, and $c$?\n", "\n", " * For sets of two, it turns out there is a _complete answer_ which some of you have either discovered it already or busy discovering.\n", " * For sets of three numbers, like $n=5\\,x+8\\,y+7\\,z$, there is an efficient algorithm, but no exact formula.\n", "\n", "Notice the connection between theory and practice!  Solving this problem could easily solve a \"real-life\" business problem, so a good algorithm would be very important. But finding such an algorithm requires exploration and experimentation like we have been doing. \n", "\n", "This [video](https://www.youtube.com/watch?v=vNTSugyS038) gives us a practical application of the Frobenius problem in real life." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Click [**here**](#day-05-toc) if you want to go back to the table of content of this notebook. Otherwise, continue to the next [**Section**](#new-experiment-sum-of-squares)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## New Experiment — Sum of Squares \n", "\n", "With that in mind, let's begin our next exploration. Hopefully you have had some fun experimenting with the condunctor problem. Today we will introduce a new problem to keep up the fun spirit of experimental mathematics. Namely, what numbers can be written in the form $n=a^2+b^2$?\n", "\n", "Here are a cases that do and do not work.\n", "\n", " * $2 = 1^2+1^2$ works;\n", " * $3$ does not work, since we only allow integers.  $1+1$ is too small, $1^2+2^2=5$ is too big;\n", " * $4$ actually does work, because we allow $4 = 0^2+2^2$.  (That's just one of our rules; you could play a different game if you wanted.);\n", " * That means $1=1^2+0^2$ works.\n", " * $5$ works.\n", "And so forth. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exploratory Questions — Sum of Squares \n", "Can you think of questions that you can explore experimentally? Last Friday, we formulated the following questions. I also added extra questions.\n", "\n", "1. Which positive integers can be written as a sum of two squares?\n", "2. Which ones cannot be written?\n", "3. Are numbers that can be represented as a sum of two squares always odd or always even? Or do they vary?\n", "4. What are the sum of squares that are even or odd integers?\n", "5. Is the sum of squares of two numbers generally even or odd? What factors influence this?\n", "6. What are the sum of squares that are perfect squares? What is the probability that the sum of squares is a perfect square? When is this condition true?\n", "7. If $a$ is a factor of $b$, under what conditions is the sum of their squares a perfect square?\n", "8. Can either $a$ or $b$ be a factor of the sum of their squares?\n", "9. For which values of $a$ and $b$ is the sum of their squares a prime number?\n", "10. Can there be two or more distinct pairs of $a$ and $b$ that yield the same sum of squares? If so, what are these pairs?\n", "11. Is the sum of the squares of two consecutive integers always odd? If not, when does it differ?\n", "12. If $a$ and $b$ are both odd, is the sum of their squares odd or even?\n", "13. If $a$ is odd and $b$ is even, what is the sum of their squares?\n", "14. If $a$ is the only even prime (i.e., $2$) and $b$ is an odd prime, is the sum of their squares a prime number?\n", "15. Which numbers can be written as a sum of squares of two prime numbers?\n", "16. Which positive integers can be expressed as the sum of squares of their factors? Are there identifiable patterns?\n", "17. Given $a$ and $b$ are both prime, under what conditions is $a^2 + b^2$ also prime?\n", "18. Are there forms other than $x^2 + 0^2$ for representing a square root as a sum of squares?\n", "\n", "Each question could reveal patterns or conjectures. Let's proceed systematically as follows:\n", "\n", " - **Identify** when the statement holds true or false.\n", " - **Analyze patterns** in the results generated.\n", " - **Make conjectures** about underlying rules or relationships based on observed patterns." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Let us start by working with pens and paper.\n", "- I will create a table on the board for us to fill it out.\n", "- We will divide ourselves into groups and try the case for $n$ running from $1$ to $100$ to fillout the table.\n", "- We will study the table to see if we can observe some patterns in the data and make some interesting conjectures.\n", "- When we are done, we will go to the computer lab and see how we can translate the table we have created using an appropriate Python datatype.\n", "- Once we have the tabular data correctly encoded, we will further explore our questions in groups using SageMath." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Hopefully you have tried some examples. Now let us have ourselves in groups and explore our questions using _SageMath_. As you explore, try to write your observation. Later on I will call on the spokesperson of a group to report their findings." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sorted([a^2 + b^2 for a in [0..10] for b in [0..10]])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sum_of_squares_database = dict(); sum_of_squares_database" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sum_of_squares_database[0] = [(0,0)]; sum_of_squares_database" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sum_of_squares_database[1] = [(0,1), (1, 0)]; sum_of_squares_database" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sum_of_squares_database[2] = [(1,1)]; sum_of_squares_database" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "list(sum_of_squares_database.values())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "list(map(len, list(sum_of_squares_database.values())))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "my_list = list()\n", "for value in list(sum_of_squares_database.values()):\n", " my_list.append(len(value))\n", "my_list" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "After a while, we will come back and I will ask you about possible ways to rethink the problem on the sum of squares. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Can you think of a way to solve this problem? _Hint: What do you know about equations of this form $n = a^{2} + b ^{2}$?_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This brings up the question of how to do such plotting in the first place? We will look at this in more detail in the next [**Section**](#more-plotting-and-graphics-in-two-dimensions)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## More Plotting and Graphics in Two Dimensions \n", "There is absolutely no way we could cover all the graphics in _SageMath_ (or the program that does it for _SageMath_, matplotlib) in one day, or even a week. We will look at a bunch of different resources you have access to, and see lots of different plot types. As we go through these resources, think of how they will be of use in solving our new experiment or where you could have used them some time back in your academic career. I definitely do not know everything about the plotting command. Nevertheless, you may interrupt me with your question so that we can explore the solution together. \n", "\n", " * We will begin with the online documentation on [advanced 2D-plotting](https://doc.sagemath.org/html/en/prep/Advanced-2DPlotting.html) in the built-in live documentation. \n", " * There are two very important pages with many, MANY examples - the documentation for [plot](http://www.sagemath.org/doc/reference/plotting/sage/plot/plot.html) and that for [showing graphics](http://www.sagemath.org/doc/reference/plotting/sage/plot/graphics.html#sage.plot.graphics.Graphics.show).\n", " * The [general plotting reference](http://www.sagemath.org/doc/reference/plotting/index.html) - there are a lot of surprises, like animation, etc.\n", "\n", "Remember, you should feel free to stop listening for a while if you want to try something out! \n", "Once we've seen enough examples, please either start using _SageMath_ to explore the sums of squares, _or_ try to recreate your favorite graphic using _SageMath_!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.4", "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.11.2" }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }