Том 29, номер 2, 2022 г., Стр. 24-37

УДК 519.7
Леонтьев В. К.
О проблеме Фробениуса

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

Ключевые слова: диофантово уравнение, проблема Фробениуса, теорема Сильвестра, производящая функция, метод коэффициентов.

DOI: 10.33048/daio.2022.29.728

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

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

Литература

[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., Torã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., Torã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 с.