eulerbooks/notebooks/problem0078.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "683859dd",
   "metadata": {},
   "source": [
    "# [Coin Partitions](https://projecteuler.net/problem=78)\n",
    "\n",
    "SageMath once again makes this pretty trivial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "48a703c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55374"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import count\n",
    "\n",
    "for n in count(1):\n",
    "    if number_of_partitions(n) % 1000000 == 0:\n",
    "        break\n",
    "\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec850c78",
   "metadata": {},
   "source": [
    "Theoretically, we could create a generating function like we did in [problem 31](https://projecteuler.net/problem=76) or [problem 76](https://projecteuler.net/problem=76) to solve this, and could even use $\\mathbb{Z}_{1000000}$ as our base ring to handle the modulus automagically, but since the answer is pretty large, it would be impractical to construct the function with the required precision.\n",
    "\n",
    "Instead, if you'd like to implement the [partition function](https://w.wiki/EoNj) yourself, Euler's [pentagonal number theorem](https://en.wikipedia.org/wiki/Pentagonal_number_theorem) leads to a useful recurrence equation:\n",
    "$$p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - p(n - 22) - p(n - 26) + \\cdots$$\n",
    "Here, the numbers are the [generalized pentagonal numbers](https://en.wikipedia.org/wiki/Pentagonal_number). As base cases, $p(0) = 1$ and $p(n) = 0$ for negative $n$, so the infinite series eventually converges.\n",
    "\n",
    "We can directly translate this equation into an implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c8dd39e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def p(n, modulus):\n",
    "    if n < 0:\n",
    "        return 0\n",
    "    \n",
    "    if n == 0:\n",
    "        return 1\n",
    "    \n",
    "    total = 0\n",
    "    limit = floor((1 + sqrt(1+24*n)) / 6)\n",
    "    \n",
    "    # we reverse the range so smaller p(n) values are calculated first and cached\n",
    "    # this helps avoid hitting Python's maximum recursion depth\n",
    "    for k in reversed(range(1, limit + 1)):\n",
    "        total += (-1)^(k+1) * (p(n - polygonal_number(5, k), modulus) + p(n - polygonal_number(5, -k), modulus))\n",
    "        total %= modulus\n",
    "    \n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df91171b",
   "metadata": {},
   "source": [
    "Note that SageMath uses libraries like [FLINT](https://flintlib.org/doc/partitions.html) with faster - but much more technical - methods, like the Hardy-Ramanujan-Rademacher formula. This implementation is much easier to both understand and write, but is less performant.\n",
    "\n",
    "## Relevant sequences\n",
    "* Partition numbers: [A000041](https://oeis.org/A000041)\n",
    "* Generalized pentagonal numbers: [A001318](https://oeis.org/A001318)\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
}