{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![\"drawing\"](\"./images/aims-za-logo.jpeg\")
\n",
"\n",
"\n",
"\n",
"## Instructors: \n",
"\n",
"* **Evans Ocansey**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Day 09 — Pieces of Numbers \n",
"\n",
"[comment]: <> (Day 08 — Introduction to SageMath: A Mathematics Software for All
)\n",
"\n",
"We will spend some time learning about a very simple new concept - one that only requires addition. We'll explore it.\n",
"\n",
"\n",
"The outline of the this notebook is as follows:\n",
"\n",
"\n",
"## Table of Contents: \n",
"[comment]: <> (The simplest addition)\n",
"* [ ] [ Pieces of Numbers](#the-simplest-addition)\n",
" * [Exploration](#exploration)\n",
" * [Exploration 1](#exploration-1)\n",
" * [Questions to Explore](#questions-to-explore)\n",
" * [Exploration Question 1](#exploration-question-1)\n",
" * [Exploration Question 2](#exploration-question-2)\n",
" * [Exploration Question 3](#exploration-question-3)\n",
" * [Exploration Question 4](#exploration-question-4)\n",
" * [Exploration Question 5](#exploration-question-5)\n",
" * [Exploration Question 6](#exploration-question-6)\n",
" * [Exploration Question 7](#exploration-question-7)\n",
" * [Exploration Question 8](#exploration-question-8)\n",
" * [Conjectures to Explore](#conjectures-to-explore)\n",
" * [Exploring Conjecture 1](#exploring-conjecture-1)\n",
" * [Exploring Conjecture 2](#exploring-conjecture-2)\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Pieces of Numbers — The Simplest Addition \n",
"\n",
"\n",
"Here is a question nearly every human could answer.\n",
" \n",
" \n",
"How many ways can you divide a pile of $5$ sticks into (non-empty) piles?\n",
"\n",
"\n",
"\n",
"\n",
"Let's see.\n",
" \n",
" \n",
" \n",
"There is the trivial one where you don't divide it at all. $5=5$.\n",
"There is the one where you just make five piles of one stick each. $1+1+1+1+1=5$.\n",
"You could have four in one pile. That leaves $4+1=5$.\n",
"But if you have three in one pile, there are two ways to do the other two.\n",
"\n",
"$3+2=5$.\n",
"$3+1+1=5$.\n",
"\n",
"\n",
"\n",
"\n",
"Almost done! I guess the only other possibility is if there are piles of $2$ and $1$.\n",
"\n",
" \n",
" \n",
"$2+2+1=5$.\n",
"$2+1+1+1=5$.\n",
"\n",
"That makes seven ways in total. We call these things _integer partitions_. As George Andrews says in [this delightful little book](http://www.cambridge.org/gb/academic/subjects/mathematics/number-theory/integer-partitions): \"An integer partition is a way of splitting a number into integer parts.\" More precisely, a partition of a nonnegative integer $n$ is a representation of $n$ as a sum of positive integers, called summands or parts of the partition. The order of the summands is irrelevant.\n",
"\n",
"\n",
"The function giving the number of partitions of $n$ is called $p(n)$. So our example shows that $p(5)=7$.\n",
"Amazingly, there are _real physics applications_ of this! See [this list of articles](https://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/partitioning.htm) and [this more dubious example](https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE153.HTM). A typical quote: \"The number partitioning problem can be interpreted physically in terms of a thermally isolated noninteracting Bose gas trapped in a one-dimensional harmonic-oscillator potential.\"\n",
" \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exploration \n",
"\n",
"As always we need data that we can explore so let us generate some. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration 1 \n",
"Try to compute $p(n)$ for $n\\leq 10$. Divide up this work in groups! Maybe three or four people should work on each one, and then cross-check their work."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
" $n$ $p(n)$\n",
"├──────┼──────────┤\n",
" $0$ $1$\n",
" $1$ $1$\n",
" $2$ $2$\n",
" $3$ $3$\n",
" $4$ $5$\n",
" $5$ $7$\n",
" $6$ $11$\n",
" $7$ $15$\n",
" $8$ $22$\n",
" $9$ $30$\n",
" $10$ $42$\n",
" $11$ $56$\n",
" $12$ $77$\n",
" $13$ $101$\n",
" $14$ $135$\n",
" $15$ $176$\n",
" $16$ $231$\n",
" $17$ $297$\n",
" $18$ $385$\n",
" $19$ $490$\n",
" $20$ $627$\n",
" $21$ $792$\n",
" $22$ $1002$\n",
" $23$ $1255$\n",
" $24$ $1575$\n",
" $25$ $1958$\n",
" $26$ $2436$\n",
" $27$ $3010$\n",
" $28$ $3718$\n",
" $29$ $4565$\n",
" $30$ $5604$\n",
" $31$ $6842$\n",
" $32$ $8349$\n",
" $33$ $10143$\n",
" $34$ $12310$\n",
" $35$ $14883$\n",
" $36$ $17977$\n",
" $37$ $21637$\n",
" $38$ $26015$\n",
" $39$ $31185$\n",
" $40$ $37338$\n",
" $41$ $44583$\n",
" $42$ $53174$\n",
" $43$ $63261$\n",
" $44$ $75175$\n",
" $45$ $89134$\n",
" $46$ $105558$\n",
" $47$ $124754$\n",
" $48$ $147273$\n",
" $49$ $173525$\n",
" $50$ $204226$"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"table(\n",
" [[f\"${latex(k)}$\", f\"${latex(number_of_partitions(k))}$\"] for k in [0..50]],\n",
" header_row=[r\"$n$\", r\"$p(n)$\"]\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sage has built-in capabilities to compute partitions. There are two classes for integer partitions in Sage, namely *Partition* and *Partitions*. The former takes a list of non-increasing integers representing a partition of a given integer as an argument, while the latter takes a positive integer. We will be working with the *Partitions* class. But let us take a look at the difference between these two classes.\n",
"\n",
"The class *Partition*, with a list of non-increasing integers as its argument, instantiates a fixed partition object with the given input list. For example:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[3, 2, 1, 1, 1]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a_fixed_partition_of_eight_object = Partition([3, 2, 1, 1, 1]); a_fixed_partition_of_eight_object"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"But the class *Partitions*, with an integer as its argument, instantiates a domain containing all the partitions of $n$. For example, we can create a domain for all the partitions of an integer, say, $8$."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Partitions of the integer 8"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all_partitions_of_eight = Partitions(8); all_partitions_of_eight"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can you create all partitions of $5$?"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Partitions of the integer 5"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all_partitions_of_5 = Partitions(5); all_partitions_of_5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With the `list` method, I can list all the partitions of $8$ by doing the following:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[8],\n",
" [7, 1],\n",
" [6, 2],\n",
" [6, 1, 1],\n",
" [5, 3],\n",
" [5, 2, 1],\n",
" [5, 1, 1, 1],\n",
" [4, 4],\n",
" [4, 3, 1],\n",
" [4, 2, 2],\n",
" [4, 2, 1, 1],\n",
" [4, 1, 1, 1, 1],\n",
" [3, 3, 2],\n",
" [3, 3, 1, 1],\n",
" [3, 2, 2, 1],\n",
" [3, 2, 1, 1, 1],\n",
" [3, 1, 1, 1, 1, 1],\n",
" [2, 2, 2, 2],\n",
" [2, 2, 2, 1, 1],\n",
" [2, 2, 1, 1, 1, 1],\n",
" [2, 1, 1, 1, 1, 1, 1],\n",
" [1, 1, 1, 1, 1, 1, 1, 1]]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all_partitions_of_eight.list()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Attention: The data type of the output is not a list "
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"one_part = all_partitions_of_eight.list()[0]; type(one_part)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(,\n",
" )"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"one_part_list = list(one_part); type(one_part_list), type(one_part)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"List all partitions of $5$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Spend some time reading the SAGE documentation on *Partitions*. Get familiar with the syntax and read the remaining part of the notebook."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"Partitions?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Questions to Explore \n",
"\n",
"Let us list some questions that we can explore."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 1 \n",
"\n",
"What are the partitions of $n$ with distinct parts?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 2 \n",
"\n",
"What is $p(n)$ modulo $5$?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 3 \n",
"\n",
"What is $p(n)$ given that all parts are prime?"
]
},
{
"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": [
"### Exploration Question 4 \n",
"\n",
"What is $p(n \\,| \\, \\text{at least } 2 \\text{ or more repeated parts})$?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 5 \n",
"\n",
"What is $p(n)$ given that all parts are greater than $1$ "
]
},
{
"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": [
"### Exploration Question 6 \n",
"The question to explore is: \n",
"\n",
" * _Partitions of $n$ using only _odd_ parts. This is notated $p(n \\mid \\text{ odd parts })$._\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 7 \n",
"\n",
"The question to explore is: \n",
"\n",
" * _Partitions of $n$ using only even parts, or $p(n \\mid \\text{ even parts })$._\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploration Question 8 \n",
"\n",
"The question to explore is: \n",
"\n",
" * _Partitions of $n$ using _distinct_ parts; that is, all the numbers in the partition are different._\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try these out for small (!) $n$. See if you find any possible patterns. Again, it is probably best if some larger groups work together and split up the work to make it more efficient."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Conjectures to Explore \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exploring Conjecture 1\n",
"\n",
"If $n$ is odd, then $p(n \\mid \\text{all parts are even}) = 0$"
]
},
{
"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": [
"### Exploring Conjecture 2 \n",
"\n",
"If $n$ is even, then $p(n \\mid \\text{all parts are even})$ is either $\\frac{n}{2}$ or $\\frac{n}{2}-1$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 10.4",
"language": "sage",
"name": "sagemath"
},
"language": "python",
"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
}