2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение08.03.2016, 14:36 
Аватара пользователя
fractalon, спасибо. Правда, я имел в виду есть ли такая команда в языках, ну типа $delmod(a;b;m)$, а то всё кодировать пальчики отбить можно :-)

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение10.03.2016, 22:13 
Аватара пользователя
fractalon в сообщении #1105035 писал(а):
Отсюда и $625$ и $119$.

Очепятка? Ведь не $119$, а $199$.

Не разобравшись, как использовать обратный элемент и алгоритм Евклида, решал вот таким способом.

Наше диофантово уравнение:
$$x = \frac{74 + 625a}{126 + 625b}$$
Здесь $a$ и $b$ целые неотрицательные, $1 \le x \le 2016$.

Положив $a=0$ и $b=0$, начал наращивать $a$ на единицу.

$74 + 625\cdot 0 \equiv 74\ (\mod 126)$
$74 + 625\cdot 1 \equiv 69\ (\mod 126)$
$74 + 625\cdot 2 \equiv 64\ (\mod 126)$

Остаток циклически уменьшается на $5$, значит $a = \frac{74 + 126c}5$. Видно, что $a$ будет принимать целые значения при $c = 5k + 1$, где $k = 0,1,2...$

$a = \frac{74 + 126(5k+1)}5 = 126k + 40$

Подставляем:
$$x = \frac{74 + 625(126k + 40)}{126}= 625k + 199$$

Действуя аналогичным способом, можно убедиться, что решений для $b>0$ нет.

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение12.03.2016, 02:08 
Не разобравшись, как использовать обратный алгоритм Евклида, вы его использовали. По крайней мере, его идею. Идея ведь в том, что берётся остаток от деления модуля на делимое (делимое в нашем случае $126$). Здесь остаток будет равен $121$, но $121 \equiv -5 \pmod{126}$, поэтому можно посчитать и за $-5$. Дальше делается такой перевёртыш как вы сделали и всё продолжается итеративно точно так же. Просто здесь удачный случай и алгоритм Евклида работает в два хода (а вообще ходов у него максимум - порядка логарифма; худший пример - применение алгоритма к двум последовательным числам Фибоначчи). Двуходовость алгоритма как бы ещё раз намекает, что задачу нужно было решать так и бумажки достаточно.

А про $119$ и $199$ - да, опечатка.

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение12.03.2016, 06:56 
Аватара пользователя
Понял, что разделить можно и на бумажке. Но как без компьютера получить, что $2016!$ (без кратных пяти, спасибо за поправку) кончается на $1184$ :?:

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение12.03.2016, 12:10 
Аватара пользователя
fractalon в сообщении #1105899 писал(а):
Не разобравшись, как использовать обратный алгоритм Евклида, вы его использовали. По крайней мере, его идею.

Так и думал :-) Спасибо.

fractalon в сообщении #1105899 писал(а):
Идея ведь в том, что берётся остаток от деления модуля на делимое (делимое в нашем случае $126$).

То есть $b$ всегда надо приравнивать к нулю? Похоже, что так. Ведь при бо́льших значениях $b$ никаких новых решений найти не удалось:

$b =   1; a = 990; x = 824$

$b =   2; a = 1390; x = 1449$

gris в сообщении #1105920 писал(а):
Но как без компьютера получить, что $2016!$ кончается на $1184$ :?:

Поправочка. На $1184$ закачивается не $2016!$ , а $\frac{2016!}{5^{403}\cdot403!}$

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение12.03.2016, 14:17 
Аватара пользователя
Кстати, в духе ТС неплохо бы ввести терминологию, чтобы не путаться. Факториал, из которого вычеркнуты все кратные $5$, назовём беспятым.

Гипотеза. Беспятый факториал(БПФ) числа, оканчивающегося на $4$, всегда оканчивается на $24$. А БПФ числа, оканчивающегося на $9$, всегда оканчивается на $76$.

Таким образом, БПФ $2014$ и БПФ $2019$ оканчиваются на $24$ и $76$ соответственно.

Насчёт БПФ 2016. Нетрудно установить, что он оканчивается на $4$ :-)

 
 
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение12.03.2016, 17:21 
Аватара пользователя
Отвечая на вопрос gris'а.

Оказывается, концовки БПФ довольно предсказуемы. Чтобы найти 4-значную концовку для чисел БПФ $n$, оканчивающихся на $16$ или $66$, можно воспользоваться формулой:

$$100((\frac{26(n - 16)}{25} + 31)\mod 100) + 84$$

Что для БПФ $2016$ как раз даёт $1184$. А, к примеру, для БПФ $2906$ нужна формула:

$$100((\frac{26(n - 6)}{25} + 1)\mod 100) + 44$$

Дающая концовку $1744$.

 
 
 [ Сообщений: 22 ]  На страницу Пред.  1, 2


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