2014 dxdy logo

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

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




 
 Макс. число не представимое в виде суммы двух натуральных.
Сообщение16.06.2008, 12:05 
Подскажите пожалуйста, существует ли формула или алгоритм для определения максимального натурального числа, не представимого в виде суммы двух натуральных? Более формально: есть взаимно простые числа $a,b$. Найти максимальное число $s$, которое нельзя представить в виде $s=xa+yb$ где $x,y$ - неотрицательные целые.

Мне известен способ решения этой задачи через диофантовы уравнения - находятся такие $p,q$ что $ap+bq=1$, откуда получается частное решение уравнения $s=ax+by$, затем анализируется семейство $x'=x-bn$, $y=y+an$ на предмет неотрицательных решений. Подскажите пожалуйста, есть ли более простая формула/алгоритм? Как эта задача обобщается на бОльшее количество переменных? Где может быть изложена теория, связанная с этой задачей?

Арсений Трушин.

 
 
 
 
Сообщение16.06.2008, 13:33 
А чему равно минимальное число $s$, которое можно представить в таком виде? Тут, по-моему, подумать секунд 10-20, и ответ готов, если я правильно понял вопрос.

 
 
 
 
Сообщение16.06.2008, 13:56 
Тут можете посмотреть
http://mathworld.wolfram.com/CoinProblem.html

 
 
 
 
Сообщение16.06.2008, 14:14 
Извините, поторопился... :oops:

 
 
 
 
Сообщение16.06.2008, 14:36 
nworm, огромное спасибо.

 
 
 
 
Сообщение16.06.2008, 19:33 
Аватара пользователя
Это так называемое число Фробениуса: http://mathworld.wolfram.com/FrobeniusNumber.html

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group