On a generalization of the coin exchange problem for three variables

Tripathi, Amitabha ; Vijay, Sujith

Journal of integer sequences, Tome 9 (2006) no. 4

Résumé

Given relatively prime and positive integers $ a_1,a_2,\ldots,a_k$, let $ {\Gamma}$ denote the set of nonnegative integers representable by the form $ a_1x_1+a_2x_2+\cdots+a_kx_k$, and let $ {\Gamma}^{\star}$ denote the positive integers in $ {\Gamma}$. Let $ {\cal S}^{\star}(a_1,a_2,\ldots,a_k)$ denote the set of all positive integers $ n$ not in $ {\Gamma}$ for which $ n+{\Gamma}^{\star}$ is contained in $ {\Gamma}^{\star}$. The purpose of this article is to determine an algorithm which can be used to obtain the set $ {\cal S}^{\star}$ in the three variable case. In particular, we show that the set $ {\cal S}^{\star}(a_1,a_2,a_3)$ has at most two elements. We also obtain a formula for $ g(a_1,a_2,a_3)$, the largest integer not representable by the form $ a_1x_1+a_2x_2+a_3x_3$ with the $ x_i$'s nonnegative integers.

Détail

Classification : 11D04
Keywords: coin exchange problem, linear Diophantine problem of Frobenius