Volume 29, No 2, 2022, P. 24-37

UDC 519.7
V. K. Leontiev
On the Frobenius problem

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.

DOI: 10.33048/daio.2022.29.728

Vladimir K. Leontiev¹
1. Dorodnitsyn Computing Center,
40 Vavilov Street, 119333 Moscow, Russia
e-mail: vkleontiev@yandex.ru

Received December 6, 2021
Revised January 19, 2022
Accepted January 21, 2022

References

[1] J. J. Sylvester, Problem 7382, Educ. Times, J. Coll. Precept. 36 (266), 177 (1883).

[2] W. J. Curran Sharp, Problem 7382. Solution, Educ. Times, J. Coll. Precept. 36 (271), 315 (1883).

[3] J. J. Sylvester, Problem 7382, in Mathematical Questions with Their Solutions: From the “Educational Times”, Vol. 41 (C. F. Hodgson, London, 1884), p. 21.

[4] V. I. Arnol’d, Experimental Observations of Mathematical Facts (MTsNMO, Moscow, 2006) [Russian].

[5] V. M. Fomichev and D. A. Mel’nikov, Cryptographic Methods of Information Security (Yurayt, Moscow, 2017) [Russian].

[6] P. Erdös and R. L. Graham, On a linear Diophantine problem of Frobenius, Acta Arithmetica 21, 399–408 (1972).

[7] J. R. Alfonsín, The Diophantine Frobenius Problem (Oxford Univ. Press, London, 2005).

[8] V. I. Arnol’d, Arithmetical turbulence of selfsimilar fluctuations statistics of large Frobenius numbers of additive semigroups of integer, Moscow Math. J. 7 (2), 173–193 (2007).

[9] V. I. Arnol’d, Weak asymptotics for the numbers of solutions of Diophantine problems, Funkts. Anal. Prilozh. 33 (4), 65–66 (1999) [Russian] [Funct. Anal. Appl. 33 (4), 292–293 (1999)].

[10] V. M. Fomichev, Estimates for exponent of some graphs by Frobenius’s numbers of three arguments, Prikl. Diskretn. Mat., No. 2, 88–96 (2014) [Russian].

[11] F. Curtis, On formulas for the Frobenius number of a numerical semigroup, Math. Scand. 67, 190–192 (1990).

[12] A. Tripathi, Formulae for the Frobenius number in three variables, J. Number Theory 170, 368–389 (2017).

[13] V. P. Savelyev and V. N. Shevchenko, The Frobenius problem for three numbers, in Proc. Int. Scientific Practice Conf. (EFIR, Moscow, 2019), pp. 10–15 [Russian].

[14] K. Song, The Frobenius problem for numerical semigroups generated by the Thabit numbers of the first, second kind base $b$ and the Cunningham numbers, Bull. Korean Math. Soc. 57 (3), 623–647 (2020).

[15] J. C. Rosales, M. B. Branco, and D. Torrão, The Frobenius problem for Thabit numerical semigroups, J. Number Theory 155, 85–99 (2015).

[16] J. C. Rosales, M. B. Branco, and D. Torrão, The Frobenius problem for repunit numerical semigroups, Ramanujan J. 40, 323–334 (2016).

[17] J. C. Rosales, M. B. Branco, and D. Torrão, The Frobenius problem for Mersenne numerical semigroups, Math. Z. 286, 741–749 (2017).

[18] M. Nijenhuis, A minimal-path algorithm for the “money changing problem”, Amer. Math. Mon. 86, 832–835 (1979).

[19] V. M. Fomichev, Primitive sets of numbers equivalent by Frobenius, Prikl. Diskretn. Mat., No. 1, 20–26 (2014) [Russian].

[20] G. P. Egorychev, Integral Representation and Computing of Combinatorial Sums (Nauka, Novosibirsk, 1977) [Russian].

[21] V. K. Leontyev and Eh. N. Gordeev, Generating functions in the Knapsack problem, Dokl. Akad. Nauk 481 (5), 478–480 (2018) [Russian] [Dokl. Math. 98 (1), 364–366 (2018)].

[22] Eh. N. Gordeev and V. K. Leontyev, On combinatorial properties of the Knapsack problem, Zh. Vychisl. Mat. Mat. Fiz. 59 (8), 1439–1447 (2019) [Russian] [Comput. Math. Math. Phys. 59 (8), 1380–1388 (2019)].

[23] J. Riordan, An Introduction to Combinatorial Analysis (John Wiley Sons, New York, 1958; Izd. Inostr. Lit., Moscow, 1963 [Russian]).

[24] Yu. V. Sidorov, M. V. Fedoryuk, and M. I. Shabunin, Lectures on the Theory of Functions of a Complex Variable (Nauka, Moscow, 1989) [Russian].

[25] G. H. Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work (AMS, Providence, RI, 1999; Inst. Komput. Issled., Moscow, 2002 [Russian]).