Solution of equation of the form $n = 1234a + 56b + 7c$

Question

I have $n = 1234a + 56b + 7c$.

Is there a way to check if a triplet $(a,b,c)$ exists, such that all three are non-negative?

Answer 1

Essentially, as Arthur mentions in the comments, this is a version of the Coin problem, finding out which values $n$ can be achieved using coins of value $1234, 56,$ and $7$.

The coin of value $56$ (and hence the variable $b$) does not change which values of $n$ are possible, as any value of $b$ can also be achieved by modifying the value of $c$ (since $7 \mid 56$). This simplifies the analysis to a two coin problem for which the answer is well-described in the wikipedia article.

However to go through the process, it's apparent that only multiples of $7$ are possible for $n<1234$. Above that, since $1234 \equiv 2 \bmod 7$, values of $n \equiv k \in \{0,2\} \bmod 7$ are possible up to $2468$, which then opens up $n\equiv 4 \bmod 7$, etc until $6\times 1234 = 7404$ fills the last gap of $n \equiv 5 \bmod 7$. The $6$ values prior to that are also achievable, of course, so the largest number for which there is no non-negative $(a,b,c)$ combination possible is $n=7404-7 = 7397$.