Factorials

[Pavlovsky]

Забавно. 999999*(999999+1) является делителем 37!

-- Чт мар 07, 2013 09:56:23 --

Проверил все числа до 10-ти миллионов.
5142500*(5142500+1) является делителем 26!
5909760*(5909760+1) является делителем 34!
7474999*(7474999+1) является делителем 37!

[dimkadimon]

Pavlovsky в сообщении #692023 писал(а):

macroxue выложил точные текущие рекорды. Проверил их на своих данных, все верно.

Большое спасибо! Рекорды тут все.

Pavlovsky в сообщении #691877 писал(а):

Есть 13 для 19!. Мои компьютеры и программы ну очень глупые. Сколько времени не могли найти рекорд. А я немного подумал и ручками собрал решение.

Поздравляю, это большое достижение! Я 13 только недавно нашёл. Жду вас в десятке :)

[Nataly-Mak]

dimkadimon в сообщении #692040 писал(а):

Поздравляю, это большое достижение! Я 13 только недавно нашёл. Жду вас в десятке :)

Да, да, я тоже поздравляю и жду в десятке

Pavlovsky
на вас смотрит вся Россия
Зона 24+ уже от вас недалеко. Осилите! Ну, а там... придётся попыхтеть, наверное.

-- Чт мар 07, 2013 09:31:35 --

Pavlovsky в сообщении #692032 писал(а):

Проверил все числа до 10-ти миллионов.
5142500*(5142500+1) является делителем 26!
5909760*(5909760+1) является делителем 34!
7474999*(7474999+1) является делителем 37!

2*(2+1) тоже является делителем 26! и 34! и 37!
а также
3*(3+1)
4*(4+1)
и т.д.

[Pavlovsky]

Естественно маленькие числа не интересны. Нужны большие числа.
Суть идеи такова.
У меня есть все начальные последовательности длиной 8 и меньше. Берем число например 5142500*(5142500+1) которое является делителем 26! Проверяем все начальные последовательности, на предмет возможности построения числа 5142500 или (5142500+1) за небольшое количество операций. Если это возможно, достраиваем начальную последовательность до чисел 5142500,(5142500+1). Далее запускаем Оливоса. После получения решения, используем простое алгебраическое свойство для уменьшения решения на единицу.

[Nataly-Mak]

Программа mertz говорит, что для числа 5142500 нет решений в 8 шагов.
В 9 шагов программа нашла два решения:

5142500 = [9] 1,2,3,5,25,22,17,550,302500,5142500
5142500 = [9] 1,2,3,5,25,22,17,550,9350,5142500

Что же, это тоже неплохо. Имеем начальную последовательность в 9 шагов; далее сразу приписываем (5142500+1), имеем уже 10 шагов.
Ну, а теперь надо сделать последний множитель. Какой он будет? Сейчас посчитаю.

У меня для 26! решение в 18 шагов.

[Pavlovsky]

Nataly-Mak в сообщении #692059 писал(а):

Программа mertz говорит, что для числа 5142500 нет решений в 8 шагов

Надо проверить еще число 5142501, может его построить легче.

[Nataly-Mak]

Pavlovsky в сообщении #692060 писал(а):

Надо проверить еще число 5142501, может его построить легче.

Да, я об этом уже подумала. Сейчас проверю, хотя вряд ли это число составить проще, чем число 5142500.
И последний множитель получается огромный: 15250017484800. Собрать его тоже непросто.

Для числа 5142501 не найдено решений и в 9 шагов, в 10 шагов найдены; здесь первые 9 решений, я прервала программу:

found 9 solutions for 5142501 in 10 steps
5142501 = [10] 1,2,4,16,20,22,484,10648,10647,5153148,5142501
5142501 = [10] 1,2,4,16,20,22,484,483,10626,5142984,5142501
5142501 = [10] 1,2,4,16,20,22,484,483,10648,10647,5142501
5142501 = [10] 1,2,4,16,20,22,484,483,10648,5142984,5142501
5142501 = [10] 1,2,4,16,20,22,484,483,233772,5142984,5142501
5142501 = [10] 1,2,4,16,64,68,272,273,18564,18837,5142501
5142501 = [10] 1,2,4,16,64,68,272,273,74529,5067972,5142501
5142501 = [10] 1,2,4,16,64,68,69,272,273,18837,5142501
5142501 = [10] 1,2,4,16,64,68,69,272,273,74529,5142501

[Pavlovsky]

15250017484800=2^21×3^7×5^2×7×19
Как видите в разложении числа на простые множители преобладают маленькие простые числа. Такие числа строить легче.

-- Чт мар 07, 2013 11:18:14 --

Nataly-Mak в сообщении #692062 писал(а):

Собрать его тоже непросто.

Мне легче у меня есть мегаОливос.

-- Чт мар 07, 2013 11:26:06 --

Мда крутая у mertz программа. Я так быстро формировать последовательности не умею. Жаль AZ запретил ее публикацию для всех.

[Nataly-Mak]

Да, вижу, уже разложила.
Такое, например, разложение получается:
$K = 798\cdot (138240)^2$

Что такое мегаОливос, если не секрет?

[Pavlovsky]

Nataly-Mak в сообщении #692067 писал(а):

Что такое мегаОливос, если не секрет?

Не понял. Ведь все это подробно обсуждалось. Берем начальную последовательность и используя только операцию умножения строим заданный N!

-- Чт мар 07, 2013 11:31:27 --

Nataly-Mak в сообщении #692067 писал(а):

$K = 798\cdot (138240)^2$

Квадрат это хорошо. Есть большие шансы уменьшить конечное решение на единицу.

[Nataly-Mak]

Я тоже не поняла.
Если мы берём начальную последовательность по вашей последней идее, то каким боком к ней пришить последний множитель K=15250017484800? Этот множитель надо составлять отдельно, а потом на него умножить предыдущий результат
5142500*5142501.

[Pavlovsky]

$26! = (5142500 \cdot 138240) \cdot(5142500 \cdot 138240 + 138240) \cdot 798$

Итого 4 операции. Осталось составить последовательность содержащую числа 798,138240,5142500 и к ее длине прибавить 4 финальных операции. Задача уже не пугает огромными числами.

-- Чт мар 07, 2013 11:42:35 --

Nataly-Mak в сообщении #692069 писал(а):

то каким боком к ней пришить последний множитель K=15250017484800?

Набрать это число, используя операцию умножения и числа которые есть в последовательности. Естественно это не всегда возможно (а если возможно не всегда количество операций получится маленьким). Надо перебрать все начальные последовательности.

[Nataly-Mak]

Преобразования вы хорошо выполнили
Действительно, осталось чуть-чуть: получить в начальной последоваетельности числа 798, 138240 и 5142500. И содержать эта последовательность должна как можно меньше членов.
Для оптимального решения сколько получается членов?

[Pavlovsky]

Для 26! рекорд 15 операций. То есть последовательность должна содержать 12 чисел (11 операций). Неужели программе mertz это не по силам?!

[Nataly-Mak]

Да, всё верно.
Число 5142500 представляется последовательностью из 10 членов, но чисел 798 и 138240 в этой последовательности нет (ни в одном из вариантов), и добавить их быстро не удаётся.

Пример получился не очень удачный.