Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.6

On a Generalization of the Coin Exchange Problem for Three Variables

Amitabha Tripathi
Department of Mathematics
Indian Institute of Technology
Hauz Khas
New Delhi - 110016

Sujith Vijay
Department of Mathematics
Rutgers University -- New Brunswick
Piscataway, NJ 08854


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.

Full version:  pdf,    dvi,    ps,    latex    

Received December 20 2005; revised version received September 12 2006. Published in Journal of Integer Sequences September 12 2006.

Return to Journal of Integer Sequences home page