Теория чисел

[vlad_light]

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

[Someone]

$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$ через два параметра с целыми коэффициентами.

[Sonic86]

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

[Cash]

Sonic86
Не все. $a_i$ - натуральные

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

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

[Sonic86]

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

[Cash]

Sonic86, спасибо!
Проблема Фробениуса! Сэкономили мне полчаса поисков . А то у меня застряла в голове и покоя не давала.

[VAL]

vlad_light в сообщении #638967 писал(а):

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

Легко убедиться, что начиная с 79, любое число представимо (достаточно представить 6 подряд). Ну а до 78 не сложно перебрать.

[Cash]

Sonic86 в сообщении #638984 писал(а):

Арифметическая задача прямо из жизни

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

[bot]

Cash в сообщении #638979 писал(а):

Точно не уверен, но даже для 3 чисел решено только в частном случае.

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

[Cash]

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

[Sonic86]

Cash в сообщении #639049 писал(а):

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

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

[Cash]

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