# zbMATH — the first resource for mathematics

A generalization of Sylvester’s and Frobenius’ problems of numerical semigroups. (English) Zbl 0789.11017
Let $${\mathcal A}$$ be a set of $$t$$ natural numbers (coin denominations) and let $$q$$ be a natural number. The classical change problem deals with functions of $${\mathcal A}$$ which are the number, $$\nu_ n$$, of changes of a money sum $$n$$ in terms of $${\mathcal A}$$ (Euler), the number, $$\Omega$$, of omitted money sums $$n$$ (with $$\nu_ n=0$$; Sylvester), and the largest, $$g$$ $$(=N)$$, of those omitted $$n$$’s $$(g=\infty$$ is allowed; $$g=-1$$ if $$\Omega = 0$$; Frobenius). Given any $$\kappa \in \mathbb{Z}$$, a modular change problem deals with $$\Omega_ \kappa$$, $$N_ \kappa$$ and $$\nu_{n \kappa}$$ (functions of $$({\mathcal A},q))$$ under the requirement that the number of coins in a change of $$n$$ be congruent to $$\kappa$$ modulo $$q$$. Finiteness of $$g({\mathcal A},q):=\max_ \kappa N_ \kappa$$ is proved to be equivalent to the conjunction of $$\gcd A=1$$ and $$\gcd (q,a_ 2-a_ 1,\dots, a_ t-a_{t-1})=1$$. Then formulae for $$N_ \kappa$$ and $$\Omega_ \kappa$$ are found, they are made explicit if $$t=2$$, and efficient pseudo-polynomial algorithms are devised in general case. An asymptotically sharp Erdős-Graham-type upper bound for $$g({\mathcal A},q)$$ is found. Open problems are stated.

##### MSC:
 11D04 Linear Diophantine equations 11Y16 Number-theoretic algorithms; complexity
Full Text: