{ "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 05 — 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)" ] }, { "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", "\n", "And so forth. Can you think of questions that you can explore experimentally? I can think of two questions: \n", "\n", " * Which positive integers can be written as a sum of two squares?\n", " * Which ones cannot?\n", "\n", "You will explore these questions next week. Please use the rest of the time to catch up on previous notebooks that you were not able to complete. You can also start doing your homework assignments. The tutors and myself will be going round to help. " ] }, { "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 }