Какое наименьшее количество множителей требуется вычеркнуть?

[Ktina]

Какое наименьшее количество множителей требуется вычеркнуть из числа 2016! так, чтобы произведение оставшихся множителей оканчивалось на 2016?

Иными словами, чему равен 2016-й член последовательности 0 0 1 0 2 2 5 2 5...?

[gris]

В преддверии празднования торжествующего феминизьма некогда и подумать над интересной задачей. Не лезет, батька, ничего в голову. Даже сметана на помогает.
Ясно, что всегда можно вычеркнуть всю середину факториала. Ясно, что можно оставить сомножители $2016$. Но это же далеко не минимум. Необходимо к вычёркиванию всё, что делится на $10$.
Вот для предыдущего числа $2015$ хотя бы много, что придётся вычеркнуть. Во-первых, все чётные числа. Во вторых, все делящиеся на $5$ кроме одного.
Призываю любителей поделиться идеями!

[Yadryara]

gris в сообщении #1104523 писал(а):

Необходимо к вычёркиванию всё, что делится на $10$.

Вы хотели сказать, все $403$ сомножителя, которые делятся на $5$ ?

[gris]

Я хотел сказать, что в этой задаче можно рассуждать. Например, у меня получились очень милые детские рассуждения для $10!$. Вот и стало интересно, существуют ли взрослые для очень больших чисел
Можно попробовать подобраться к задаче сзади. То есть набрать максимальное число различных натуральных чисел не больших $N$, так чтобы их произведение кончалось на $N$. Тут идея разложить само число на множители, а также числа, которые не меняют конца произведения.
Потом можно спрятать повторяющиеся числа в попарных произведениях. Например:

$2016=1\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 7$

$10001=73\cdot 137$

$20001=3\cdot 59\cdot 113$

$30001=19\cdot 1579$

И это даёт $1\cdot 2\cdot 4\cdot 6\cdot 7\cdot 9\cdot 38\cdot 59\cdot 73\cdot 113\cdot 137\cdot 1579=12098217720962016$

Конечно, тут тоже наличествует тупой перебор. Да и докуда перебирать, если вот $56321230001=31\cdot 53\cdot 89\cdot 283\cdot 1361$

Вместе с тем, количество чётных сомножителей может быть большим. Например, $22016=2^9\cdot 43$. Чего-то мне кажется, что я в упор не вижу простого решения

[fractalon]

Компьютерное решение (динамическим программированием) показало, что достаточно вычеркнуть все кратные $5$ и ещё одно число $1449$.

[Yadryara]

Иными словами, результат выражения

$$\frac{2016!}{5^{403}\cdot403!\cdot1449}$$

заканчивается на $2016$ ?

-- 07.03.2016, 09:02 --

Это $4627$-значное число, но вот концовку мне Alpha не показывает...

[gris]

Можно все умножения делать по модулю $10000$. Собственно, я так и считал прямо в эксельке, уповая, что не придётся залезать в мудрёную динамику fractalon. Как подсказал Yadryara, подготовил столбец из $2016-403$ чисел, перемножил их все, оставляя только 4 последние цифры. Кончается на $1184$. Приготовился постепенно удалять из столбца числа по одному, потом по два... Хотел даже анализировать вначале только последнюю цифру, но перебор неожиданно закончился на первом же проходе.
Итак, $K_{2016}=1612$.
Жалко, что не получилось теоретически
.

[fractalon]

Математическое решение, видимо, должно было заключаться в том, чтобы мы перемножили все множители кроме кратных пяти по модулю $10000$, а потом по этому же модулю разделили результат на 2016. И тут магическим образом оказалось бы, что это одно из оставшихся чисел.

(Оффтоп)

И ничуть там не мудрёная динамика: $d_{n,k}$ - минимальное количество множителей, которое нужно вычеркнуть из $n!$ чтобы последними четырьмя цифрами было число $k$. Решает за $O(nk)$, порядка $10^7$ операций. Хорошая машина за секунду управится (моя, правда, не управилась).

[gris]

А как можно разделить $1184$ на $2016$ по модулю $10000$?
Я только перебором могу
Я под математическим решением понимал не требующее компьютера под рукой. То есть эта задача вполне годится для школьников-программеров, а вот если в лесу? При каком $N$ эта задача интересна и не обременительна для решения на листочке бумаги? Я думаю, что какие-то формулы существуют для умножения по модулю прогрессий. Впрочем, для решения подобных задач всегда есть искушение перед подумать начирикать примитивный скрипт. А уж если серьёзный пакет имеется...

[venco]

Исключить надо как минимум 404 множителя - 403 кратных 5, и одно из $199+625k$.

[Aritaborian]

Yadryara в сообщении #1104787 писал(а):

Это $4627$-значное число, но вот концовку мне Alpha не показывает...

Не беспокойтесь. Mathematica мне показала. Заканчивается. Если хотите, могу переслать число полностью вам в ЛС ;-D

[grizzly]

Yadryara в сообщении #1104787 писал(а):

Это $4627$-значное число, но вот концовку мне Alpha не показывает...

Не то чтобы в лесу, но за 2 минуты я заставил Альфу показать все цифры этого числа. Чтобы обхитрить, я задал вопрос чуточку сложнее (добавил ещё 5 в знаменатель):

$$\frac{2016!}{5^{404}\cdot403!\cdot1449}$$

[Ktina]

gris
Yadryara
fractalon
venco
Aritaborian
grizzly
Спасибо!

[Yadryara]

venco в сообщении #1104950 писал(а):

Исключить надо как минимум 404 множителя - 403 кратных 5, и одно из $199+625k$.

А вот и ответ в общем виде. Ежели не хочется вычёркивать $1449$, к вашим услугам $199$ или $824$.

Почему множитель $625$ ?

Не забывая, что любое целое число, оканчивающееся на $2016$, делится на $16$, получим:

$10000k+2016 = 16(625k+126)$.

Вопрос ещё и в том, можно ли более-менее кратко объяснить, откуда берётся $199$...

grizzly в сообщении #1104963 писал(а):

Не то чтобы в лесу, но за 2 минуты я заставил Альфу показать все цифры этого числа. Чтобы обхитрить, я задал вопрос чуточку сложнее (добавил ещё 5 в знаменатель):

$$ \frac{2016!}{5^{404}\cdot403!\cdot1449}$$

Очень ловко! Как догадались?

Действительно, стоит только сделать результат не целым, а рациональным, как "Альфа" начинает показывать даже столь длинные числа целиком. Причём показывает сразу же, даже без нажатия кнопки "More digits"!

-- 08.03.2016, 06:23 --

Если желаешь увидеть чему точно равно огромное число $2016!$, превращаешь его в рациональное, разделив на большее простое. Например на $2111$. Вуаля! Ответ готов!

[fractalon]

gris в сообщении #1104905 писал(а):

А как можно разделить $1184$ на $2016$ по модулю $10000$?

Для этого надо разделить $74$ на $126$ по модулю $625$ (просто поделил все числа на $16$, чтобы модуль и делитель стали взаимопростыми).
Это делается просто, можно и на бумажке, с помощью обратного элемента по модулю. А это через алгоритм Евклида: http://e-maxx.ru/algo/reverse_element

Отсюда и $625$ и $119$.