1
$\begingroup$

Ex: $2+2+3$, $2+3+2$, $3+2+2$ these are three ways to get a sum of $7$ with $3$ and $2$. But my example is with $5$ and $2$ and a sum of $29$.

I believe there are three ways to get a sum of $29$ by using fives and nines. But is there any formula for this? What if I want to check the sum of $500$ or $1 000 0000$ using $5$ and $2$?

$\endgroup$
4
  • $\begingroup$ See Diophantine equations, brilliant.org/wiki/linear-diophantine-equations-one-equation $\endgroup$
    – true blue anil
    Commented Nov 24, 2022 at 17:54
  • $\begingroup$ You say your example is with 5 and 2, but you also say you think there are 3 ways to get a sum of 29 with 5 and 9. Which one is it? 5 and 2 or 5 and 9? $\endgroup$
    – user920957
    Commented Nov 24, 2022 at 19:38
  • $\begingroup$ Does the order of the summands matter? If not this is the number of ways to get $5a+2b=29$. Which as $5\times 2 = 2\times 5$ for every solution $5a + 2b=29$ we'd have $5(a-2) + 2(b+5)$ is a solution. To get the solution with the biggest $a$ we'd figure that $29\equiv 4\pmod 5$ and solve for the smallest $2b\equiv 4\pmod 5$ and that is $b =2$ so we have $5\cdot 5 + 2\cdot 2 =29$ for $a=5, b=2$ and we will have $a = 5-2x$ and $b=2+5x$ for enough $x$ so that $5-2x\ge 0$. That is $x=\lceil \frac 52\rceil = 3$. There are $3$ solution $5\cdot 5+2\cdot 2; 5\cdot 3+2\cdot 7; 5\cdot 2 + 2\cdot 12$. $\endgroup$
    – fleablood
    Commented Nov 24, 2022 at 19:46
  • 1
    $\begingroup$ Okay, order matters. For each value of $5(a-2x)+2(b+2x)$ we must figure there are ${a+b\choose a-2x}$ ways to order the $5$s and $2$ so get $\sum_{x=0}^{\lceil \frac 52\rceil} {a+b \choose a-2x}$ ways to do it. $\endgroup$
    – fleablood
    Commented Nov 24, 2022 at 19:50

1 Answer 1

Reset to default
2
$\begingroup$

Here's an observation: $(x^2+x^3)^k$ is a polynomial whose $x^n$ coefficient is the number of ways to get $n$ by using $k$ total $2$'s and $3$'s. So, if we don't care how many total we use, the $x^n$ coefficient of the geometric series $$ \sum_{k=0}^\infty (x^2+x^3)^k = \frac{1}{1-x^2-x^3} $$ is the number of ways of getting $n$ using any number of $2$'s and $3$'s. The first terms of this are $$ \frac{1}{1-x^2-x^3} = 1+x^2+x^3+x^4+2x^5+2x^6+3x^7+4x^8+5x^9+7x^{10}+\cdots. $$ This supports what you found, that there are three ways to get $7$.

Getting a nice closed-form formula depends on factoring the denominator, if possible, to do partial fractions to represent this as a sum of geometric series. That's one way to calculate a particular coefficient. Another is to just go through with polynomial long division, which isn't so bad, but it will take a while to (by hand) figure out how many ways there are to get ten million!

For fives and nines, the corresponding rational function is $$ \sum_{k=0}^\infty(x^5+x^9)^k = \frac{1}{1-x^5-x^9} = 1+x^5+x^9+x^{10}+2 x^{14}+x^{15}+x^{18}+3 x^{19}+x^{20}+3 x^{23}+4 x^{24}+x^{25}+x^{27}+6 x^{28}+5 x^{29} + \cdots. $$ This says there are five ways of getting $29$, not three.

Another way to understand this, rather than using power series, is that to calculate the number of ways $f(n)$ of getting $n$ with fives and nines, you can calculate $f(n-5) + f(n-9)$ since you add together the number of ways where the last number chosen is a five and the number of ways where the last number chosen is a nine. Then you make a table starting with $n=0$ with $f(0)=1$ (since there is one way to get $0$). By calculating the values of this function at consecutive numbers, you get to reuse previous calculations. (This is equivalent to the long division approach.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .