О числе Фробениуса.

[Руст]

Купил очередную книжку Арнольда "Экспериментальное наблюдение математических фактов".
Последний параграф посвящён определению максимального целого числа $M(a_1,a_2,...,a_k)$, что все целые $X$ больше этого представляются в виде линейной комбинации с неотрицательными целыми коэффициентами

$$X=\sum_{i=1}^kx_ia_i$$

а само это число не представляется.Здесь все $a_i$ натуральные числа не имеющего общего делителя больше 1. При $k=2$ это число давно вычислено Сильвестром и равен $M(a,b)=ab-a-b$. На самом деле это число несложно вычисляется и при $k>2$. Только явные формулы усложняются. Предлагаю в качестве задачи решить проблему для $k=3$, т.е. вычислить $M(a,b,c)$ ($a,b,c$ - взаимно простые $((a,b),c)=1$).

[maxal]

Руст писал(а):

На самом деле это число несложно вычисляется и при k>2. Только явные формулы усложняются.

Не верю!
Цитирую (с заменой тамошнего $n$ на $k$):

An explicit solution is known for $k=3$ (Selmer and Beyer 1978, Rödseth 1978, Greenberg 1988).
...
Fast algorithms are also known for three numbers, but the more general problem for an arbitrary number of numbers is known to be NP-hard. No closed-form solution is known for $k>3$.

Если у тебя есть явная формула хотя бы для $k=4$ - срочно публикуй

[Руст]

maxal писал(а):

Если у тебя есть явная формула хотя бы для $k=4$ - срочно публикуй

Дело в том, что формула сводится к maxmin по переменным, пробегающим примерно гиперкуб с соответствующими сторонами, когда все попарно взаимно простые. Формулу конечного вида без maxmin и мне удалось получить только при $k=2$ и $k=3$.