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.

11D04 Linear Diophantine equations
11Y16 Number-theoretic algorithms; complexity
PDF BibTeX Cite
Full Text: DOI EuDML