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

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

\n", "\n", "\n", "## Instructors: \n", "\n", "* **Evans Ocansey**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Day 13 — Perfection and Practice with Divisors and Interacts\n", "\n", "\n", "The outline of the this notebook is as follows:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Table of Contents: " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Today, we will spend the first part of class mostly in lecture mode, where I will share fascinating facts about $\\sigma$—hopefully inspiring you to see how exploration often leads to meaningful results!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Revisiting Definitions\n", "Let me once again define the $\\tau$ and $\\sigma$ functions:\n", "\n", "1. **$\\tau(n)$**: The number of divisors of $n$. \n", " Example: $\\tau(6) = 4$ because the divisors of $6$ are $1, 2, 3, 6$.\n", "\n", "2. **$\\sigma(n)$**: The sum of divisors of $n$. \n", " Example: $\\sigma(6) = 12$ because $1 + 2 + 3 + 6 = 12$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall from yesterday's lecture that these functions are already implemented in Sage: \n", "- $\\tau$ is `number_of_divisors`\n", "- $\\sigma$ is `sigma` with $k=1$." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "@interact\n", "def _(n=range_slider(1,150,1,(1,20))):\n", " top = n[1]\n", " bottom = n[0]\n", " cols = ((top-bottom)//10)+1\n", " T = [cols*[r'$n$',r'$\\sigma(n)$',r'$\\frac{\\sigma(n)}{n}$']]\n", " list = [[i,sigma(i),(sigma(k=1, n=i)/i).n(digits=3)] for i in range(bottom,top+1)]\n", " list.extend((10-(len(list)%10))*['',''])\n", " for k in range(10):\n", " t = [item for j in range(cols) for item in list[k+10*j]]\n", " T.append(t)\n", " return table(T)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "source": [ "If $\\sigma(n) = C_n \\cdot n$, do any of these have $C_n \\geq 3$?\n", "\n", "How would we *get* such numbers?\n", "\n", "- Well, we would need lots of factors relative to the size of the number.\n", "- Numbers with lots of small prime divisors should have more factors.\n", "- Could we multiply lots of small prime numbers together?\n", "\n", "Let's try a few small numbers of this kind:\n", "\n", "- $N = 2 \\cdot 3 \\cdot 5 = 30$\n", "- $N = 2^2 \\cdot 3 \\cdot 5 = 60$\n", "- $N = 2^3 \\cdot 3^2 \\cdot 5 = 360$\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "sigma(k=1, n=30)/30.; sigma(k=1, n=60)/60.; sigma(k=1, n=360)/360." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's a good sign! Let's try it a bit more systematically in an interact.\n", "\n", "### Interactive Exploration with SageMath\n", "\n", "Use the following interact to explore numbers $N$ of the form:\n", "$$\n", "N = 2^{a} \\cdot 3^{b} \\cdot 5^{c},\n", "$$\n", "where $a, b, c$ are non-negative integers. We aim to compute $\\sigma(N)$ and determine if $C_N = \\frac{\\sigma(N)}{N} \\geq 3$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "@interact\n", "def systematic_sigma(a=(0, 5), b=(0, 5), c=(0, 5)):\n", " N = 2^a * 3^b * 5^c\n", " sigma_N = sigma(k=1, n=N)\n", " C_N = sigma_N / N\n", " html(f\"

Results for $N = 2^{a} \\\\cdot 3^{b} \\\\cdot 5^{c}$:

\")\n", " html(f\"$N = {N}$\")\n", " html(f\"$\\\\sigma(N) = {sigma_N}$\")\n", " html(f\"$C_N = \\\\frac{{\\\\sigma(N)}}{{N}} = {C_N}$\")\n", " if C_N >= 3:\n", " return html(\"Good news! $C_N \\\\geq 3$\")\n", " else:\n", " return html(\"$C_N < 3$. Keep exploring!\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is also another version of interact for exploration" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "@interact\n", "def _(n=[1..15]):\n", " pretty_print(html(fr\"Try $2^{n}\\cdot 3^{n}\\cdot 5^{n}={2^n*3^n*5^n}$\"))\n", " pretty_print(\n", " html(\n", " fr\"Then $\\sigma({2^n*3^n*5^n})={sigma(k=1, n=2^n*3^n*5^n)}={sigma(k=1, n=2^n*3^n*5^n)/(2^n*3^n*5^n)}\\cdot {2^n*3^n*5^n} \\approx {(sigma(k=1, n=2^n*3^n*5^n)/(2^n*3^n*5^n)).n(digits=3)}\\cdot {2^n*3^n*5^n}$\"\n", " )\n", " )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You'll notice that although we quickly go above 3, we don't seem to get much further. Why? \n", "\n", "For a full answer to that, we would need a formula for $\\sigma$, which you have alredy discovered." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can continue with this idea to explore further. Experiment with different values in the interact and see how $\\sigma(N)$ grows relative to $N$. Consider trying:\n", "- Numbers with even more small prime factors,\n", "- Higher powers of primes,\n", "- Combinations of both.\n", "\n", "Keep asking questions:\n", "- Why does $C_N$ seem to plateau after a certain point? \n", "- How do the factors of $N$ influence $\\sigma(N)$?\n", "- Is there a mathematical bound for $C_N$?\n", "\n", "This exploration can help develop deeper intuition about $\\sigma$ and its behavior." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "(sigma(k=1, n=2^4 * 3^4 * 5^4 *7)/(2^4*3^4*5^4*7)).n(digits=3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "num = prod([p^4 for p in primes_first_n(10)])\n", "(sigma(num)/num).n(digits=3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Continuing this for more primes suggests the following fact:\n", "\n", "**Fact:** For any positive $C$, there is a positive integer $n$ such that:\n", "$$\n", "\\sigma(n) > C \\cdot n.\n", "$$\n", "\n", "Trying to prove this might even involve exploring the distribution of primes—are they \"dense\" enough to achieve this?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Perfect Numbers\n", "\n", "There is one particular ratio that is very special. When it is exactly $2$, we say $n$ is a **perfect number**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Historical Context\n", "This definition dates back quite a ways. [Euclid](http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII22.html) defined it at the beginning of his number-theoretic books and mentioned it again over 100 propositions later, proving that certain numbers are perfect—a fitting conclusion, as Dunham highlights in *Journey through Genius*." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Theorem\n", "If $n$ is a number such that $2^n - 1$ is prime, then the (even) number:\n", "$$\n", "2^{n-1} \\cdot (2^n - 1)\n", "$$\n", "is perfect.\n", "\n", "[Euclid's proof](http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX36.html) of this is worth examining. Numbers of the form $2^n - 1$ that are prime also require $n$ to be prime (try proving this!) and are called **Mersenne primes**, named after Marin Mersenne. Mersenne, a 17th-century polymath, was like the internet of his time for Western European scientific circles.\n", "\n", "Today, identifying Mersenne primes is a major example of computer-aided exploration in pure mathematics. For example, the [Great Internet Mersenne Prime Search](http://www.mersenne.org/) (GIMPS) has discovered all the largest known primes, including one with over 17 million digits." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Euler's Converse\n", "Centuries later, Euler proved the converse. Here's the result:\n", "\n", "**Theorem:** \n", "If $n$ is an even perfect number, it can be expressed as the product:\n", "$$\n", "2^{n-1} \\cdot (2^n - 1),\n", "$$\n", "where $2^n - 1$ is a Mersenne prime. Furthermore, all such products are even perfect numbers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Proof (Sketch)\n", "To prove this result, we rely on two key facts:\n", "1. $\\sigma(2^n q) = \\sigma(2^n) \\cdot \\sigma(q)$ if $q$ is odd.\n", "2. $\\sigma(2^n) = 2^{n+1} - 1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Part 1: If $2^n - 1$ is prime\n", "If $2^n - 1$ is prime, then:\n", "$$\n", "\\sigma\\left(2^{n-1} \\cdot (2^n - 1)\\right) = \\sigma\\left(2^{n-1}\\right) \\cdot \\sigma(2^n - 1).\n", "$$\n", "From the facts above:\n", "$$\n", "\\sigma\\left(2^{n-1}\\right) = 2^n - 1, \\quad \\sigma(2^n - 1) = 2^n.\n", "$$\n", "Thus:\n", "$$\n", "\\sigma\\left(2^{n-1} \\cdot (2^n - 1)\\right) = (2^n - 1) \\cdot 2^n = 2 \\cdot \\left[2^{n-1} \\cdot (2^n - 1)\\right].\n", "$$\n", "The sum of divisors is exactly twice the original number, proving it is perfect." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Part 2: The Converse\n", "If $n$ is an even perfect number, it must be divisible by some power of $2$. Let this power be $2^{n-1}$, so that the number is $2^{n-1} q$, where $q$ is odd. Steps:\n", "1. Since the number is perfect:\n", " $$\n", " \\sigma\\left(2^{n-1} q\\right) = 2 \\cdot 2^{n-1} q = 2^n q.\n", " $$\n", "2. Using the property of $\\sigma$:\n", " $$\n", " \\sigma\\left(2^{n-1} q\\right) = \\sigma\\left(2^{n-1}\\right) \\cdot \\sigma(q) = (2^n - 1) \\cdot \\sigma(q).\n", " $$\n", "3. Combining:\n", " $$\n", " 2^n q = (2^n - 1) \\cdot \\sigma(q).\n", " $$\n", " This implies $2^n - 1 \\mid q$. Write $q = (2^n - 1) \\cdot m$.\n", "4. Substituting into the equation:\n", " $$\n", " 2^n \\cdot m = \\sigma(q).\n", " $$\n", " Since $\\sigma(q) \\geq q + m$, this implies $q$ has only two divisors (it is prime). Therefore, $m = 1$, $q = 2^n - 1$, and the perfect number is:\n", " $$\n", " 2^{n-1} \\cdot (2^n - 1).\n", " $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## More About Perfect Numbers\n", "Many claims about perfect numbers have emerged throughout history. For example, Nichomachus, a Hellenistic Roman, claimed that the $n$th perfect number has $n$ digits. While he was more focused on mystical interpretations, this assertion held sway for over a millennium.\n", "\n", "However, we now know this claim is false. For example, the fifth perfect number (associated with $n = 13$) is:\n", "\n", "$$\n", "\\left(2^{13} - 1\\right) \\cdot 2^{12}.\n", "$$\n", "\n", "Its discovery, delayed until the 15th century, showed that the number of digits grows much faster than $n$." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [], "source": [ "(2^13-1)*2^12" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Until the early modern period, such numbers were basically inaccessible. The current known perfect number is $82$ million digits long." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Odd Perfect Numbers\n", "\n", "We haven't yet talked about *odd* perfect numbers.\n", "\n", "**Fact** (due to P. Weiner): \n", "$$\n", "\\text{If } \\sigma(N) = \\frac{5}{3}N, \\text{ then } 5N \\text{ is an odd perfect number.}\n", "$$\n", "\n", "However, we don't know whether this hypothesis is ever true. In fact, we don't even know the answer to the following:\n", "\n", "> **Open Question**: Does there exist an odd perfect number?\n", "\n", "Yikes! This question has remained unanswered for over two and a half millennia." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Known Results About Odd Perfect Numbers\n", "\n", "Although we haven't resolved this question, we do know some things. The following facts can be proved using methods outside of *experimental* math, but we won't explore those proofs in class today:\n", "\n", "1. An odd perfect number cannot be a prime power.\n", "2. An odd perfect number cannot be a product of exactly *two* prime powers.\n", "3. An odd perfect number cannot be a product of exactly *three* prime powers unless the first two are $3^e$ and $5^f$.\n", "\n", "There are many more criteria, some of which are quite complicated. For example, from two ongoing [searches](http://www.lirmm.fr/~ochem/opn/) ([search 2](http://oddperfect.org/index.html)), we know:\n", "\n", "- Must be greater than $10^{1500}$. (Proof for slightly smaller bounds like $10^{1250}$ is confirmed.)\n", "- Has at least 101 prime factors (not necessarily distinct).\n", "- Has at least 9 *distinct* prime factors; if 3 isn't a factor, you need at least 12 distinct primes.\n", "- Largest prime factor must be at least $10^8$.\n", "- Second largest prime exceeds 10,000.\n", "- If $n$ is an odd perfect number, then $n \\equiv 1 \\bmod{12}$ or $n\\equiv 9 \\bmod{36}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Euler's Criterion\n", "\n", "Euler, who completed the characterization of *even* perfect numbers, also derived a significant criterion for odd perfect numbers:\n", "\n", "An odd perfect number must be of the form:\n", "$$\n", "p^e m^2,\n", "$$\n", "where:\n", "- $m$ is odd,\n", "- $p$ is prime,\n", "- Both $p$ and $e$ satisfy:\n", " $$\n", " p \\equiv 1 \\bmod{4} \\text{ and } e \\equiv 1 \\bmod{4}.\n", " $$\n", "\n", "For more details, see this [article about Euler](http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2037%20Odd%20perfect%20numbers%5B1%5D.pdf).\n", "\n", "Odd perfect numbers remain one of the great mysteries of number theory, with many deep results but no definitive resolution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sage Outside the Notebook\n", "\n", "Our final introduction to another interface with Sage is the **Sage cell server**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Sage Cell Server\n", "\n", "The [Sage cell server](http://sagecell.sagemath.org/) is somewhat analogous to Wolfram Alpha and other computational websites. You simply type in a command, and it executes it for you. While it doesn’t have \"memory,\" making it unsuitable for long computations, it is extremely convenient for quick calculations when you are online.\n", "\n", "Let's demo the Sage cell server, by copying one of the interact demonstration in this notebook to the [Sage cell server](http://sagecell.sagemath.org/)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Nested Interacts\n", "\n", "The Sage cell server also allows you to create **nested interacts** for greater flexibility. Here is one example by one of the Sage developers.\n", "\n", "- Explore a [nested interact example](http://sagecell.sagemath.org/?z=eJxzyMwrSS1KTC7h5UpJTVOI18izNda04uVSAIKCIqCkQl6cEYSbmaaQp2CnYAKVBQEHhG6YEMSUXNs8TSR1CNNy44whwqk5xalIKopSS0qL8gCzNCG3&lang=sage)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Embedding Sage Cells in Web Pages\n", "\n", "Another powerful feature of the Sage cell server is the ability to **embed interacts inside other web pages**. This is incredibly useful for various applications:\n", "\n", "- Creating interactive class notes.\n", "- Designing web pages for teaching and sharing concepts.\n", "\n", "- Here is an example: [Using Sage for Interactive Computation](https://math.gordon.edu/ntic/ntic/section-using-computation.html), which includes a suggestion on using experimental evidence about the conductor.\n", "\n", "\n", "These features make the Sage cell server a flexible and powerful tool for sharing and exploring mathematical computations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Interlude for Interacts\n", "\n", "Being able to interact with data and math is one of the most enjoyable features of Sage. This is something we haven’t practiced much in homework, though.\n", "\n", "---\n", "\n", "### Let's Practice!\n", "\n", "Let’s take some time to practice creating these interacts. Can we brainstorm some topics you’d like to interact with? Here are some ideas to get us started:\n", "\n", "- Visualizing arithmetic functions like $\\tau(n)$ and $\\sigma(n)$.\n", "- Exploring prime factorizations and their properties.\n", "- Graphing polynomials and observing how their roots change with coefficients.\n", "- Studying convergence of sequences or series interactively.\n", "- Plotting and exploring number-theoretic functions like the Euler totient function $\\phi(n)$ or the Möbius function $\\mu(n)$.\n", "- Analyzing modular arithmetic or residue classes.\n", "- Visualizing 3D surfaces and transformations.\n", "\n", "---\n", "\n", "Feel free to suggest other topics or areas of interest, and we’ll create interact tools to explore them! \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Key to Making a Good Interact\n", "\n", "Creating an effective interact involves thoughtful planning and simplicity. Follow these steps to make a useful and engaging interact:\n", "\n", "1. **Start with a Non-Interactive Concept** \n", " Begin by identifying something *non-interactive* you want to explore or investigate. \n", " - **Example**: The derivative of a function at a point.\n", "\n", "2. **Add One Interactive Element** \n", " Make *one aspect* of the concept interactive and focus on that. \n", " - **Example**: The point at which you evaluate the derivative.\n", "\n", "3. **Iterate and Enhance** \n", " As you use the interact, you may discover more things to make interactive. Gradually add these. \n", " - **Example**: The function being differentiated (if desired).\n", "\n", "4. **Expand Thoughtfully** \n", " If it adds value, introduce additional interactive elements. Avoid cluttering the interface unnecessarily. \n", " - **Examples**: \n", " - A second function. \n", " - The integral of the function. \n", "\n", "5. **Go Elaborate (If Needed)** \n", " Once the interact is functional and clear, you can add more complex features. \n", " - **Example**: A plot showing the function and its local linear approximation at the point.\n", "\n", "6. **Avoid Unnecessary Additions** \n", " Usability is critical. Don’t add controls or features that don’t serve a purpose. \n", " - **Example**: Allowing users to pick a different text color. *(Why would you?)*\n", "\n", "7. **Provide Explanation** \n", " Always include clear explanations of what the interact does and how to use it. Use `pretty_print(html(...))` for LaTeX or detailed formatting. \n", " - **Commands to use**: \n", " - `print`: For simple text explanations. \n", " - `html`: For more detailed formatting or LaTeX. \n", " - `pretty_print(html(...))`: For combining explanations with LaTeX." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example Steps for a Derivative Interact\n", "1. Start with a non-interactive calculation of the derivative of a function at a point.\n", "2. Make the point of evaluation interactive.\n", "3. Add interactivity to change the function (if desired).\n", "4. Introduce additional elements like the integral of the function or a plot.\n", "5. Keep the interface clean and user-friendly.\n", "\n", "By following these principles, you can create interacts that are not only functional but also engaging and easy to use." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maybe this could be useful for investigating partitions or divisor-related functions or even in your `@interact` group presentations tomorrow." ] }, { "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" } }, "nbformat": 4, "nbformat_minor": 4 }