|
On the Frobenius problem
V. K. Leontiev Dorodnitsyn Computing Center, 40 Vavilov Street, 119333 Moscow, Russia
Abstract:
The classical Frobenius problem (the Frobenius coin problem) is considered. Using the method of generating functions, a formula is found for the number of solutions of the Diophantine equation associated with this problem. Special attention is paid to the case of two variables, which is considered to be investigated, but there are no rigorous proofs in some of its aspects. As a consequence of the result obtained in this work, both the well-known Sylvester theorem (expressions for the Frobenius number) and formulas for those values of variables on which this number is achieved follow. The problems of this work are closely related to algorithms for solving discrete optimization problems, as well as cryptographic methods in information security. Tab. 1, bibliogr. 25.
Keywords:
Diophantine equation, Frobenius problem, Sylvester's theorem, generating function, coefficient method.
Received: 06.12.2021 Revised: 19.01.2022 Accepted: 21.01.2022
Citation:
V. K. Leontiev, “On the Frobenius problem”, Diskretn. Anal. Issled. Oper., 29:2 (2022), 24–37
Linking options:
https://www.mathnet.ru/eng/da1296 https://www.mathnet.ru/eng/da/v29/i2/p24
|
Statistics & downloads: |
Abstract page: | 501 | Full-text PDF : | 33 | References: | 28 | First page: | 15 |
|