Arithmetic Frobenius

Let's do Bonus 1. The number we're looking for is called the Frobenius number $g(n,n+1,n+2)$ . The claim is that this number equals $n\lfloor n/2 \rfloor - 1,$ so that for $n=17$ the answer is $17 \cdot 8 - 1 = \fbox{135}.$

To prove this, note that it is possible to find a sequence of $n$ representable numbers starting at $n \lfloor n/2 \rfloor,$ as follows. Each of the given 3-tuples $(a,b,c)$ represents $n \cdot a + (n+1) \cdot b + (n+2) \cdot c.$ $\begin{aligned} n\lfloor n/2 \rfloor &= (\lfloor n/2 \rfloor,0,0) \\ n\lfloor n/2 \rfloor +1 &= (\lfloor n/2 \rfloor - 1,1,0) \\ n\lfloor n/2 \rfloor + 2 &= (\lfloor n/2 \rfloor - 1,0,1) \\ n\lfloor n/2 \rfloor + 3 &= (\lfloor n/2 \rfloor - 2,1,1) \\ &\vdots \\ n\lfloor n/2 \rfloor + n-1 &= \begin{cases} (0,0,\lfloor n/2 \rfloor) & \text{ if } n \text{ is odd} \\ (0,1,\lfloor n/2\rfloor - 1) & \text{ if } n \text{ is even} \end{cases} \end{aligned}$ and so we can represent any number $m$ larger than these by noting that $m-nq$ is one of the numbers in this range, so we can represent $m-nq$ and then add $q$ to the first coordinate of the representation to get a representation for $m.$

So this shows that $g(n,n+1,n+2) \le n\lfloor n/2 \rfloor - 1.$ The proof concludes by showing that $n\lfloor n/2 \rfloor - 1$ is not representable. To see this, consider the equation modulo $n.$ Note that $n\lfloor n/2 \rfloor - 1$ is congruent to $n-1$ mod $n.$ And a number represented by a 3-tuple $(a,b,c)$ is congruent to $b+2c$ mod $n.$ Also note that for a representation $(a,b,c)$ of $n\lfloor n/2 \rfloor -1,$ we would have $a+b+c < \lfloor n/2 \rfloor.$ So $b+2c$ is a nonnegative integer which is (because of this last restriction) $\le 2(\lfloor n/2 \rfloor - 1).$ This is strictly smaller than $n-1,$ so there is no way to represent a number that small which is congruent to $n-1$ mod $n.$

(If this is confusing, it might help to consider the example $n=17.$ The point is that $135$ is one less than a multiple of $17,$ and a representation $(a,b,c)$ of $135$ would have to have $a+b+c < 8,$ but there is no way to have $b+2c=16$ if $a+b+c<8;$ the best we could do would be to take $a=b=0$ and $c=7$ which would give $b+2c=14.$ )

For Bonus 2 and 3, there is a general formula that is proved in much the same way as the above. I leave the details to you. :) $g(n,n+d,\ldots,n+sd) = \left( \left\lfloor \frac{n-2}{s} \right\rfloor +1\right) n + (n-1)(d-1) - 1.$