268 lines
13 KiB
Plaintext
268 lines
13 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e5793a3a",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Coin Sums](https://projecteuler.net/problem=31)\n",
|
|
"\n",
|
|
"The easiest thing to do here is... let SageMath do the whole thing for us."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "9bedec84",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"73682"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"Partitions(200, parts_in=(1,2,5,10,20,50,100,200)).cardinality()"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "44f7d7da",
|
|
"metadata": {},
|
|
"source": [
|
|
"But that's boring, and there's a *very* cool way to solve this problem using [generating functions](https://en.wikipedia.org/wiki/Generating_function).\n",
|
|
"\n",
|
|
"## Generating functions\n",
|
|
"If you're not familiar, a generating function is a way of expressing a sequence as coefficients of a [formal power series](https://en.wikipedia.org/wiki/Formal_power_series). For example, the generating function for the Fibonacci sequence is\n",
|
|
"$$0x^0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + \\cdots$$\n",
|
|
"\n",
|
|
"The seemingly trivial series $(1, 1, 1, 1, \\ldots)$ has an equally simple generating function\n",
|
|
"$$1 + x + x^2 + x^3 + x^4 + \\cdots$$\n",
|
|
"which converges to $\\frac{1}{1-x}$ for $-1 < x < 1$. (Note that we don't really care about the interval of convergence, because we're not going to be evaluating this function directly. Here, $x$ is called an indeterminate.)\n",
|
|
"\n",
|
|
"If this is your first time seeing generating functions, it's probably not obvious how they can help us solve this problem. Let's look at some related, simpler problems to lead us towards understanding.\n",
|
|
"\n",
|
|
"## Trivial change-making\n",
|
|
"First, consider an (almost trivial) question: how many ways can you make 0 cents, 1 cent, 2 cents, and so on using *only* 1 cent coins? It's not a trick question; there's one way for each, since you only have 1 cent coins to use! (1, 1, 1, 1, 1, 1, ...)\n",
|
|
"\n",
|
|
"Similarly, how many ways can you make 0 cents, 1 cent, 2 cents, etc. using only 2 cent coins? Answer: every even value has one way of making change, and every odd value has zero ways (1, 0, 1, 0, 1, 0, ...). Similarly, with only 5 cent coins, there is one way to make change for every multiple of 5, and zero ways for every other value (1, 0, 0, 0, 0, 1, ...).\n",
|
|
"\n",
|
|
"We can express the answers to each of these questions as sequences, and therefore as generating functions:\n",
|
|
"$$\\begin{align}\n",
|
|
"1 + x + x^2 + x^3 + \\cdots = \\frac{1}{1-x}\\\\\n",
|
|
"1 + x^2 + x^4 + x^6 + \\cdots = \\frac{1}{1-x^2}\\\\\n",
|
|
"1 + x^5 + x^{10} + x^{15} + \\cdots = \\frac{1}{1-x^5}\\\\\n",
|
|
"\\end{align}$$\n",
|
|
"One way to interpret these functions that will be very useful later: for each term, the exponent represents the money amount you're trying to make change for, while the coefficient represents the number of ways to make change for that amount (in these functions, we only have 0 and 1 as coefficients, but sit tight...).\n",
|
|
"\n",
|
|
"## Not-so-trivial change-making\n",
|
|
"Now we can jump to a more interesting question: if we have 1, 2, and 5 cent coins, how many ways can we make 7 cents? It's not too difficult to enumerate all six ways by hand:\n",
|
|
"$$\\begin{align}\n",
|
|
"5 + 2 \\\\\n",
|
|
"5 + 1 + 1 \\\\\n",
|
|
"2 + 2 + 2 + 1 \\\\\n",
|
|
"2 + 2 + 1 + 1 + 1 \\\\\n",
|
|
"2 + 1 + 1 + 1 + 1 + 1 \\\\\n",
|
|
"1 + 1 + 1 + 1 + 1 + 1 + 1\n",
|
|
"\\end{align}$$\n",
|
|
"But we can also use the generating functions we came up with above to find the total. One way is to cut off each infinite series after the $x^7$ term, then multiply them all together."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "74c5fe00",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"x^18 + x^17 + 2*x^16 + 2*x^15 + 3*x^14 + 4*x^13 + 5*x^12 + 6*x^11 + 5*x^10 + 6*x^9 + 5*x^8 + 6*x^7 + 5*x^6 + 4*x^5 + 3*x^4 + 2*x^3 + 2*x^2 + x + 1"
|
|
]
|
|
},
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"G(x) = (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7)*(1 + x^2 + x^4 + x^6)*(1 + x^5)\n",
|
|
"G(x).expand()"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "03d52995",
|
|
"metadata": {},
|
|
"source": [
|
|
"Our answer is then simply the coefficient of the $x^7$ term (sometimes denoted $[x^7]G(x)$), which is 6, as expected.\n",
|
|
"\n",
|
|
"But how in the world does *that* work? Consider just part of the above calculation.\n",
|
|
"$$(1 + x^2 + x^4 + x^6)(1 + x^5) = 1 + x^5 + x^2 + x^7 + x^4 + x^9 + x^6 + x^{11}$$\n",
|
|
"The terms of the resulting product are written in the same order as you would probably get when distributing by hand. I'm going to try to give an interpretation for the first few resulting terms (remember what we said before about the meanings of the exponents and coefficients):\n",
|
|
"* $1 \\times 1 = 1$: There's **one way** to make change for **0 cents** with only 2 cent coins, and **one way** to make change for **0 cents** with only 5 cent coins. Therefore, there's **one way** to make change for **0 cents** using both 2 cent and 5 cent coins.\n",
|
|
"* $1 \\times x^5 = x^5$: There's **one way** to make change for **0 cents** with only 2 cent coins, and **one way** to make change for **5 cents** with only 5 cent coins. Therefore, there's **one way** to make change for **5 cents** using both 2 cent and 5 cent coins.\n",
|
|
"* $x^2 \\times 1 = x^2$: There's **one way** to make change for **2 cents** with only 2 cent coins, and **one way** to make change for **0 cents** with only 5 cent coins. Therefore, there's **one way** to make change for **2 cents** using both 2 cent and 5 cent coins.\n",
|
|
"* $x^2 \\times x^5 = x^7$: There's **one way** to make change for **2 cents** with only 2 cent coins, and **one way** to make change for **5 cents** with only 5 cent coins. Therefore, there's **one way** to make change for **7 cents** using both 2 cent and 5 cent coins.\n",
|
|
"\n",
|
|
"Now let's try multiplying this result by the rest of the function:\n",
|
|
"$$(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7)(1 + x^2 + x^4 + x^5 + x^6 + x^7 + x^9 + x^{11})$$\n",
|
|
"Here, I'll do interpretations of a select few terms:\n",
|
|
"* $1 \\times x^7 = x^7$: There's **one way** to make change for **0 cents** with only 1 cent coins, and **one way** to make change for **7 cents** with 2 and 5 cent coins. Therefore, there's **one way** to make change for **7 cents** using 1, 2, and 5 cent coins.\n",
|
|
"* $x \\times x^6 = x^7$: There's **one way** to make change for **1 cent** with only 1 cent coins, and **one way** to make change for **6 cents** with 2 and 5 cent coins. Therefore, there's **one way** to make change for **7 cents** using 1, 2, and 5 cent coins.\n",
|
|
"* $x^3 \\times x^4 = x^7$: There's **one way** to make change for **3 cents** with only 1 cent coins, and **one way** to make change for **4 cents** with 2 and 5 cent coins. Therefore, there's **one way** to make change for **7 cents** using 1, 2, and 5 cent coins.\n",
|
|
"\n",
|
|
"Notice that each of these select terms represent a different way to make change for 7 cents. Therefore, together they represent 3 ways to make change for 7 cents with 1, 2, and 5 cent coins. There are 3 more products that result in $x^7$ ($x^2 \\times x^5$, $x^5 \\times x^2$, and $x^7 \\times 1$), and when we are done distributing, we combine like terms, which results in $6x^7$. As a reminder, the exponent represents the amount we are making change for, and the coefficient represents the number of ways to make change for that amount with the denominations we're using.\n",
|
|
"\n",
|
|
"Note that the polynomial multiplication gives us not just the number ways to make change for 7 cents, but for *all* cent totals from 0 to 7. The higher degree terms are inaccurate since we cut them off in the original series for our computation, but if we didn't do this, and instead worked with \n",
|
|
"$$(1 + x + x^2 + x^3 + \\cdots)(1 + x^2 + x^4 + x^6 + \\cdots)(1 + x^5 + x^{10} + x^{15} + \\cdots)$$\n",
|
|
"we would have a generating function for the number of ways to make change for *any* amount using 1, 2, and 5 cent coins. Since these series also have closed forms, we can express the generating function more succinctly as\n",
|
|
"$$G(x) = \\frac{1}{(1-x)(1-x^2)(1-x^5)}$$\n",
|
|
"\n",
|
|
"## The original problem\n",
|
|
"Just like the simpler problems above, each $n$th term in this generating function gives the number of ways to make change for $n$ pence using 1, 2, 5, 10, 20, 50, 100, and 200 pence coins.\n",
|
|
"$$G(x) = \\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}$$\n",
|
|
"Therefore, to solve this problem, we just need to find $[x^{200}]G(x)$.\n",
|
|
"\n",
|
|
"If we weren't using SageMath, we'd probably want to do something like what we did above, where we cut off each infinite series after the $x^{200}$ term, then multiply those polynomials and find the $x^{200}$ term of the product. Polynomial multiplication is implemented in libraries like [NumPy](https://numpy.org/doc/stable/reference/generated/numpy.polynomial.polynomial.polymul.html), or you can implement it yourself - either by naively distributing like above, or more efficiently with [convolutions](https://en.wikipedia.org/wiki/Convolution), which in turn are implemented using a [Fast Fourier transform](https://en.wikipedia.org/wiki/Fast_Fourier_transform)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "c351c248",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"73682.0"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"from numpy.polynomial import Polynomial\n",
|
|
"\n",
|
|
"degree = 200\n",
|
|
"\n",
|
|
"ones = Polynomial([1 for _ in range(0, degree + 1)])\n",
|
|
"twos = ones(Polynomial.basis(2)).cutdeg(degree)\n",
|
|
"fives = ones(Polynomial.basis(5)).cutdeg(degree)\n",
|
|
"tens = ones(Polynomial.basis(10)).cutdeg(degree)\n",
|
|
"twenties = ones(Polynomial.basis(20)).cutdeg(degree)\n",
|
|
"fifties = ones(Polynomial.basis(50)).cutdeg(degree)\n",
|
|
"hundreds = ones(Polynomial.basis(100)).cutdeg(degree)\n",
|
|
"twohundreds = ones(Polynomial.basis(200)).cutdeg(degree)\n",
|
|
"\n",
|
|
"G = ones * twos * fives * tens * twenties * fifties * hundreds * twohundreds\n",
|
|
"G.coef[degree]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "60169571",
|
|
"metadata": {},
|
|
"source": [
|
|
"With SageMath, another possibility is to use the function as written, and instead calculate its 200th [Taylor polynomial](https://en.wikipedia.org/wiki/Taylor_series)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "33bbc1a4",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"73682"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"G(x) = 1/prod(1 - x^k for k in (1, 2, 5, 10, 20, 50, 100, 200))\n",
|
|
"G(x).taylor(x, 0, 200).coefficient(x^200)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "4584583b",
|
|
"metadata": {},
|
|
"source": [
|
|
"Yet another possibility is to construct the generating function as a member of the [power series ring](https://en.wikipedia.org/wiki/Formal_power_series) over the integers. This is the most abstract method, but is faster than the Taylor series method."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 5,
|
|
"id": "c2a5db7e",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"73682"
|
|
]
|
|
},
|
|
"execution_count": 5,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"R.<x> = PowerSeriesRing(ZZ, default_prec=201)\n",
|
|
"G = 1 / prod(1 - x^k for k in (1, 2, 5, 10, 20, 50, 100, 200))\n",
|
|
"G[200]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "32707270",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Number of ways to make change with Euro currency (same values as this problem until $n=500$): [A057537](https://oeis.org/A057537)\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
|
|
}
|