On a Generalization of the Coin Exchange Problem for Three Variables

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

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

, the largest integer not representable by the form

with the

's nonnegative integers.

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

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 India Sujith Vijay Department of Mathematics Rutgers University -- New Brunswick Piscataway, NJ 08854 USA

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

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