103 lines
2.5 KiB
Plaintext
103 lines
2.5 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "c09827d4",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Counting Summations](https://projecteuler.net/problem=76)\n",
|
|
"\n",
|
|
"We want $p(100) - 1$, where $p(n)$ is the [partition function](https://w.wiki/EoNj). We subtract 1 because $p(n)$ counts $n$ by itself as a partition of $n$, but we only want partitions composed of two or more numbers.\n",
|
|
"\n",
|
|
"Guess what? SageMath has this built-in."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "1e4ff844",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"190569291"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"number_of_partitions(100) - 1"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "d06d7ff2",
|
|
"metadata": {},
|
|
"source": [
|
|
"Alternatively, if we think of this problem like [problem 31](https://projecteuler.net/problem=31) - just with coins of every possible denomination instead of only a few - we can adapt any of our approaches to that problem, where we construct a generating function."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "bba7ef34",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"190569291"
|
|
]
|
|
},
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"R.<x> = PowerSeriesRing(ZZ, default_prec=101)\n",
|
|
"G = 1 / prod(1 - x^n for n in range(1, 100))\n",
|
|
"G[100]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "681d7716",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Partition numbers: [A000041](https://oeis.org/A000041)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"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": 5
|
|
}
|