Exactly 6 integer solutions

Question

I am trying to find the greatest value of $"c"$ for which $7x + 9y = c$ has exactly six solutions over positive integers.

My approach: Let one of the solution = $(a, b)$

General solution is $(a + 9t, b - 7t)$

For values t = 0, 1, 2, 3, 4, 5 we get 6 solutions.

Also $b - 7t$ should be positive.

So maximum value of $b$ is 41.

I am struck at this point how to find the maximum value of $a$ subject to the condition $7a + 9b = c$ is maximum.

Any help?

Answer 1

When you don´t restraint the values $(x,y)$ the general solution is given by $(x,y)=(a+9t,b-7t)$ and there are infinitely many solutions hence, in order to have exactly six solutions we take positive or non-negative ones. We take positive solutions.

It follows one can take the values $t=0,1,2,3,4,5$ so $7t\in\{0,7,14,21,28,35\}$ which implies $35\lt b\lt 42$. For each of these six values of $b$, we can take any $a$ so we get a value of $c$ and the equation admits exactly six positive solutions for all value of $a$, $b$ being fixed. It is clear that does not exist a maximum for $c$ because $a$ can be arbitrarily large.

But we can search a minimum $c$. Take $b=36$ and $a=1$; this gives the value $$c=7 \cdot 1+9\cdot36=\color{red}{331}$$ and the equation $$7x+9y=331$$ which admits exactly the following six positive solutions: $$(x,y)\in\{(1,36),(10,29),(19,22),(28,15),(37,8),(46,1)\}$$

Answer 2

I have assumed $x>0$ and $y>0$.

There are, IMHO, precisely 63 values of $c$ which give exactly six solutions. The smallest is $c=331$, the maximum is $c=441$. For $c=441$, $(x,y)=(9,42),(18,35),(27,28),(36,21),(45,14),(54,7)$

I found this with a simple program to calculate $c$ from $x$ and $y$ for a very generous $(x,y)$ range, accumulating the number of solution for each $c$ and retaining just the first values found for $(x,y)$. Then I reran the program, writing out the $(c,x,y)$ values for the above range.

I found a clear pattern emerging from the results; the maximum number of solutions increases as $c$ grows, but that was not the question.

Although there is nothing wrong with using $(a,b,t)$, I could see no easy way to find the lowest $(a,b)$ values for a set. Please let me know if you need any further details.

Added 20 Sept 2016

I've noticed that exactly 6 solutions is not unique. My data shows that, for exactly $N$ solutions, there are 63 values of $c$ for $N=2$ up to $N=300$

Answer 3

So, if (a,b) is a solution of $7x + 9y = c$ then $(a+n,b+m)$, with $7n + 9m = 0$, is also a solution.
But this approach does not look promising.

A different way is to consider that $$ \sum\limits_{0\, \leqslant \,c} {N(c)\,z^{\,c} } = \frac{1} {{\left( {1 - z^{\,7} } \right)\left( {1 - z^{\,9} } \right)}} $$ with $N(c)$ indicating the number of non-negative solutions.
If you expand the RHS, you will notice that in order to get exactly 6 solutions, $c$ will span from $315$ to $425$, but of course not all the values therein provide exactly $6$ solutions.
Then you could proceed and examine the constant term of the Laurent series for $$ \frac{1} {{z^{\,6} \left( {1 - z^{\,7} } \right)\left( {1 - z^{\,9} } \right)}} $$ Still another way is to resort to Popoviciu's Theorem, which in this case gives $$ N(c) = \frac{c} {{63}} - \left\{ {\frac{{4c}} {9}} \right\} - \left\{ {\frac{{4c}} {7}} \right\} + 1 $$ with $\left\{ x \right\} = x - \left\lfloor x \right\rfloor $.
This provides an easiest way to compute the required min and max values for $c$ and also how many and which they are.

Now the problem you posed is known as "The Coin Exchange Problem of Frobenius" and widely discussed in various papers, e.g. in this paper and in this other paper.

Answer 4

Imagine a line of slope $-\frac{7}{9}$, initially extending through the origin and making its way "northeastward"—that is, sliding in the direction of positive $x$ and positive $y$. As it does so, it traverses a lattice of points with non-negative integer coordinates. (It will be simpler, computationally, to consider non-negative points, and the answer can be translated to positive points without much difficulty.) G Cab's observation that additional solutions can be obtained from existing solutions is in fact exactly on point.

Consider that the minimum sum $c$ for which a given number of solutions exist can be obtained by considering those situations where a solution of the form $(0, y)$ and one of the form $(x, 0)$ both exist. Simple consideration of the slope shows that we have $k+1$ solutions whenever the endpoint solutions are $(0, 7k)$ and $(9k, 0)$. For instance, we have $6$ solutions for $k = 5$, which gives us $c = 9 \times 35 = 7 \times 45 = 315$. This can be translated to the positive-point case simply by adding $315+7+9 = 331$.

The maximum sum $c$ for which a given number of solutions exist is a bit trickier, but note that we essentially want to "just miss" a solution to the left of the $y$-axis, and "just miss" another solution below the $x$-axis. Since a solution at $x = 9$ means that we have a solution also at $x = 0$, we want our first solution to lie at $x = 8$, and then we have further solutions separated by intervals of length $9$: $x = 17, 26, 35, 44, 53$, and then we want to just miss a solution at $x = 62$. That would-be solution would have $y = -1$, which means that the actual solutions, counting back toward the $y$-axis, would have intervals of length $7$: $y = 6, 13, 20, 27, 34, 41$.

Any of these solutions $(8, 41), (17, 34), \ldots, (53, 6)$ will yield the same maximum value of $c = 7 \times 8 + 9 \times 41 = 7 \times 17 + 9 \times 34 = \cdots = 425$. The positive-point case can again be obtained by adding $425+7+9 = 441$.