2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 О числе Фробениуса.
Сообщение20.09.2007, 21:03 
Заслуженный участник


09/02/06
4365
Москва
Купил очередную книжку Арнольда "Экспериментальное наблюдение математических фактов".
Последний параграф посвящён определению максимального целого числа $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$).

 Профиль  
                  
 
 Re: О числе Фробениуса.
Сообщение21.09.2007, 01:22 
Модератор
Аватара пользователя


11/01/06
5538
Руст писал(а):
На самом деле это число несложно вычисляется и при k>2. Только явные формулы усложняются.

Не верю! :lol:
Цитирую (с заменой тамошнего $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$ - срочно публикуй :!:

 Профиль  
                  
 
 Re: О числе Фробениуса.
Сообщение21.09.2007, 07:11 
Заслуженный участник


09/02/06
4365
Москва
maxal писал(а):
Если у тебя есть явная формула хотя бы для $k=4$ - срочно публикуй :!:

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group