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?

Why not substitute integer values $> 6$ for $t$ in your formula for the general solution? One of $a,b$ is going to be negative anyway for large enough $c$ — P Vanchinathan, Sep 18 '16 at 11:20
Are you asking about POSITIVE solutions? If so, then edit your question. — Piquito, Sep 18 '16 at 12:22
@Piquito there are obviously infinite solutions if negative numbers are included. The OP should mention it though — N.S.JOHN, Sep 18 '16 at 13:14

score 1 · Answer 1 · answered Sep 18 '16 at 22:41

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)\}$$

answered Sep 18 '16 at 22:41

Piquito

29,594

Nice solution. $c = 331$ is the minimum number satisfies the condition. But for $a = 8, b = 41$ we get maximum number which is $425$. Why we have to choose $a = 8$? because $x$ ranges from $0$ to $8$. – Ramakrishna S Sep 19 '16 at 04:08
What you say, dear friend, it is not true. If you take, for example, $b=36$ and $a$ positive arbitrary then you have exactly the following six positive solutions: $(a,36),(a+9,29),(a+18,22),(a+27,15),(a+36,8),(a+45,1)$. For other values of the parameter $t$ you get non-positive solutions. But the value of $c$ has no upper bound being $c=7a+324$. Am I wrong? – Piquito Sep 19 '16 at 08:44
Here $b-7t > 0$ So for values 0 to 5 we have six solutions. But for t = 6 where $7t$ is 42 we get 7 solutions. So I took $t = 41$. Subsequently, largest value of $a = 8$, we get the following solutions $(x,y)\in{(8,41),(17,34),(26,27),(35,20),(44,13),(53,6)}$. So largest value of $c = 425$. Oh, for a = 9, also we get 6 solutions. Where $c = 432$ – Ramakrishna S Sep 19 '16 at 11:19
Yes I am wrong because with $a$ large, negative values of $t$ produce more than six positive solutions. It is interesting to see if your $425$ is actually the maximun. I bet that yes. Later I will see it. – Piquito Sep 19 '16 at 14:52
@user97674: Yes it is the maximun! Following the reasoning above $a$ can not be greater than $8$ (because if and $a\gt 9$ then we can take a negative value for the parameter $t$ yielding still a positive solutions besides of the six enumerated) and $b$ can not be greater than $41$. This gives for the constant $c$ your value $425$. In fact it is the required maximun. – Piquito Sep 19 '16 at 23:33

Old Peter · Answer 2 · 2016-09-20T11:22:49.140

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$

G Cab · Answer 3 · 2016-09-19T16:50:46.177

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.

score 0 · Answer 4 · answered Sep 19 '16 at 17:23

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$.

Exactly 6 integer solutions

4 Answers4