2014 dxdy logo

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

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




 
 Теория чисел
Сообщение02.11.2012, 00:59 
Проверить, можно ли представить число $N\in \mathbb N$ в виде: $6a+9b+20c, a,b,c\in\mathbb N$. Думал, делить сперва на 20, потом остаток на 9 и последний остаток на 6, но фигня получается. Как подступиться?

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 02:42 
Аватара пользователя
$6a+9b+20c=N$
Наименьший по модулю коэффициент при неизвестных - $6$.
$6(a+b+3c)+3b+2c=N$
Полагаем $k=a+b+3c$. Отсюда можно выразить, например, $b=k-a-3c$. Подставляем в уравнение.
$6k+3(k-a-3c)+2c=N$
$9k-3a-7c=N$
Повторяем процедуру, пока не удастся выразить $a,b,c$ через два параметра с целыми коэффициентами.

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 06:32 
В виде $a_1x_1+...+a_nx_n$ представляются все числа, кратные $\gcd(a_1,...,a_n)$. В общем виде доказывается алгоритмом Евклида.

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 06:57 
Sonic86
Не все. $a_i$ - натуральные :wink:

-- Пт ноя 02, 2012 07:59:59 --

Точно не уверен, но даже для 3 чисел решено только в частном случае. Имеется ввиду наименьшее число, начиная с которого все будут представимы. Алгоритмов проверки, конечно же, полно

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 07:22 
Да, точно, я про целые говорил :-(
Где-то у нас даже задача была на эту тему: дана конкретная линейная форма над $\mathbb{N}$ с НОД=1 и найти наибольшее число, ей не представимое. Сейчас найду...
Арифметическая задача прямо из жизни

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 07:45 
Sonic86, спасибо!
Проблема Фробениуса! Сэкономили мне полчаса поисков :D . А то у меня застряла в голове и покоя не давала.

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 07:46 
vlad_light в сообщении #638967 писал(а):
Проверить, можно ли представить число $N\in \mathbb N$ в виде: $6a+9b+20c, a,b,c\in\mathbb N$. Думал, делить сперва на 20, потом остаток на 9 и последний остаток на 6, но фигня получается. Как подступиться?
Легко убедиться, что начиная с 79, любое число представимо (достаточно представить 6 подряд). Ну а до 78 не сложно перебрать.

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 07:50 
Sonic86 в сообщении #638984 писал(а):

Интересное совпадение. Здесь числа те же самые что и у ТС

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 10:43 
Аватара пользователя
Cash в сообщении #638979 писал(а):
Точно не уверен, но даже для 3 чисел решено только в частном случае.

Почему в частном? Для трёх чисел с $gcd=1$ представимы все, за исключением конечного числа. Остальные предствимы если только некоторый треугольник содержит внутри точку с целыми координатами.
Для данного случая этот треугольник образуется пересечением прямых $3x=N,\, 20x+2y=7N,\, 20x+3y=7N$
Если нуль считается натуральным, то граница треугольника включается, если не считается, то выключается.

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 10:54 
Значит есть способ найти все числа, не представимые в виде $p_1x_1+p_2x_2+p_3x_3$
где $p_i$ - простые числа, порядка, скажем $10^{12}$?

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 11:00 
Cash в сообщении #639049 писал(а):
Значит есть способ найти все числа, не представимые в виде $p_1x_1+p_2x_2+p_3x_3$
где $p_i$ - простые числа, порядка, скажем $10^{12}$?

В принципе он есть :-) А вот какова скорость алгоритмов - это конечно да...

 
 
 
 Re: Теория чисел
Сообщение02.11.2012, 11:14 
Нашел в вики.
http://en.wikipedia.org/wiki/Numerical_semigroup
Для трех чисел нет формулы, вычисляющей наибольшее непредставимое, но есть эффективные алгоритмы его нахождения. Приведенный там Rödseth's algorithm имеет логарифмическую скорость выполнения и числа порядка $10^{12}$ должен щелкать как семечки.

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


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