О проблеме Фробениуса

О проблеме Фробениуса

Леонтьев В. К.
Дискретный анализ и исследование операций, 29, 2, 24-37 (2022)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2022.29.728

Аннотация:

Рассматривается классическая проблема Фробениуса (проблема монет Фробениуса). С помощью метода производящих функций находится выражение для числа решений диофантова уравнения. В качестве следствия из этого результата вытекает известная теорема Сильвестра. Кроме того, получено не только выражение для числа Фробениуса, но и формулы для тех значений переменных, на которых это число достигается. Проблематика данной работы тесно связана с задачами дискретной оптимизации, а также с криптографическими методами защиты информации. 
Табл. 1, библиогр. 25.

Литература:
  1. Sylvester J. J. Problem 7382 // Educ. Times, J. Coll. Precept. 1883. V. 36, No. 266. P. 177.
     
  2. Curran Sharp W. J. Problem 7382. Solution // Educ. Times, J. Coll. Precept. 1883. V. 36, No. 271. P. 315.
     
  3. Sylvester J. J. Problem 7382 // Mathematical questions with their solutions: From the “Educational Times”. V. 41. London: C. F. Hodgson, 1884. P. 21.
     
  4. Арнольд В. И. Экспериментальное наблюдение математических фактов. М.: МЦНМО, 2006. 119 с.
     
  5. Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. М.: Юрайт, 2017.
     
  6. Erdös P., Graham R. L. On a linear Diophantine problem of Frobenius // Acta Arithmetica. 1972. V. 21. P. 399–408.
     
  7. Alfonsín J. R. The Diophantine Frobenius problem. London: Oxford Univ. Press, 2005.
     
  8. Arnold V. I. Arithmetical turbulence of selfsimilar fluctuations statistics of large Frobenius numbers of additive semigroups of integer // Moscow Math. J. 2007. V. 7, No. 2. P. 173–193.
     
  9. Арнольд В. И. Слабые асимптотики числа решений диофантовых задач // Функцион. анализ и его прил. 1999. Т. 33, № 4. С. 65–66.
     
  10. Фомичёв В. М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов // Прикл. дискрет. математика. 2014. № 2. С. 88–96.
     
  11. Curtis F. On formulas for the Frobenius number of a numerical semigroup // Math. Scand. 1990. V. 67. P. 190–192.
     
  12. Tripathi A. Formulae for the Frobenius number in three variables // J. Number Theory. 2017. V. 170. P. 368–389. 
     
  13. Савельев В. П., Шевченко В. Н. Задача Фробениуса для трёх чисел // Сб. статей Междунар. науч.-практ. конф. М: ЕФИР, 2019. С. 10–15.
     
  14. Song K. 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. 2020. V. 57, No. 3. P. 623–647. 
     
  15. Rosales J. C., Branco M. B., Torrão D. The Frobenius problem for Thabit numerical semigroups // J. Number Theory. 2015. V. 155. P. 85–99.
     
  16. Rosales J. C., Branco M. B., Torrão D. The Frobenius problem for repunit numerical semigroups // Ramanujan J. 2016. V. 40. P. 323–334.
     
  17. Rosales J. C., Branco M. B., Torrão D. The Frobenius problem for Mersenne numerical semigroups // Math. Z. 2017. V. 286. P. 741–749.
     
  18. Nijenhuis M. A minimal-path algorithm for the “money changing problem” // Amer. Math. Mon. 1979. V. 86. P. 832–835.
     
  19. Фомичёв В. М. Эквивалентные по Фробениусу примитивные множества чисел //Прикл. дискрет. математика. 2014. № 1. С. 20–26.
     
  20. Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977. 281 с.
     
  21. Леонтьев В. К., Гордеев Э. Н. Производящие функции в задаче о ранце // Докл. Академии наук. 2018. Т. 481, № 5. С. 478–480.
     
  22. Леонтьев В. К., Гордеев Э. Н. О некоторых комбинаторных свойствах задачи о рюкзаке // Журн. вычисл. математики и мат. физики. 2019. Т. 59, № 8. С. 1439–1447.
     
  23. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностр. лит., 1963. 287 с.
     
  24. Сидоров Ю. В., Федорюк М. В., Шабунин М. И. Лекции по теории функций комплексного переменного. М.: Наука, 1989. 480 с.
     
  25. Харди Г. Г. Двенадцать лекций о Рамануджане. М.: Ин-т компьют. исслед., 2002. 336 с.

Исследование выполнено при поддержке Российского фонда фундаментальных исследований (проект № 20–01–00645).

Леонтьев Владимир Константинович
  1. Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН, 
    ул. Вавилова, 40, 119333 Москва, Россия

E-mail: vkleontiev@yandex.ru

Статья поступила 6 декабря 2021 г. 
После доработки — 19 января 2022 г. 
Принята к публикации 21 января 2022 г.

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.

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.
     
  6. 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]).