Factorials

[Pavlovsky]

Думал что за странная фамилия ОливОс. Пока не догадался, он грек ОлИвос!

[Nataly-Mak]

На конкурсе сменился лидер

Цитата:

1 24.95 Tomas Rokicki Palo Alto, California, United States 20 Feb 2013 05:02

[Pavlovsky]

Готовлюсь к субботнему кодингу. Еще одна нижняя оценка.
Пусть мы хотим вычислить выражение: $x_1^{n_1}\dots x_k^{n_k}$. Пусть все $n_1,\dots,n_k$ различны. Привести общий случай к этому частному, элементарно. Тогда $L(x_1^{n_1}\dots x_k^{n_k}) \ge 2k-2$. Равенство достигается тогда, когда числа $n_1,\dots,n_k$ образуют аддитивную последовательность без использования дополнительных чисел.

Пример 1:
5^3*7^2*143*144^4
L>=2*4-2=6

Пример 2:
35^2*144^4*323
L>=3*2-2=4

-- Ср фев 20, 2013 12:05:50 --

Пример использования нижней оценки. Пусть у нас есть последовательность (1,2,3,9,81,80,77) из этих чисел, путем умножения мы хотим получить число 11!=39916800. Необходимо найти все разложения числа 39916800 на сомножители (числа берутся из нашей начальной последовательности), так чтобы оно вычислялось не более чем за 3 умножения. Тогда общая длина последовательности вычисления 11! будет 9.
Варианты разложения на сомножители и их оценка:
81*80^2*77 L>=3
9^2*80^2*77 L>=3
3^4*80^2*77 L>=4
3^2*9*80^2*77 L>=4

Получается, что только варианты 81*80^2*77 и 9^2*80^2*77 дают искомую длину последовательности 9 для 11!

[dimkadimon]

Образовалась интересная задача: как в решении найти лишние числа? Например в 1, 2, 3, 4, 6, 24 число 3 лишнее и его можно убрать не теряя результат. Для каждого числа можно найти все пары родителей (числа которые дают даное число). Потом начиная с конца можно найти наиболее короткий путь. Числа которые не в этом пути лишние. Например самый короткий путь тут:

24 = 6*4
6 = 4+2
4 = 2*2
2 = 1+1

Получается что число 3 не нужно. Есть ли лучше способ?

-- 20.02.2013, 16:33 --

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

На конкурсе сменился лидер

Вот это борьба! Кстати обнаружен ещё один рекорд на 5 баллов. Возможно какое то время у них было 25.00.

[Pavlovsky]

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

24 = 6*4
6 = 4+2
4 = 2*2
2 = 1+1

24 = 6*4
6 = 3+3
3 = 2+1
2 = 1+1

24 = 6*4
6 = 3*2
3 = 2+1
2 = 1+1

Та же длина 4. Получается 3 совсем не лишнее.

Задачу можно обобщить на случай пассивных чисел (в терминологии Наталии). Чтоб не путаться в определениях даю свое определение пассивного числа.

Определение. Пассивным числом будем называть число в последовательности, которое участвует в формировании только одного из последующих чисел.

Поиск пассивных чисел и попытка их заменить более подходящим числом, более интересная тема при оптимизации последовательности.

-- Ср фев 20, 2013 13:11:15 --

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

Кстати обнаружен ещё один рекорд на 5 баллов. Возможно какое то время у них было 25.00.

Опс а мой результат не уменьшился. Значит новый рекорд установлен для N=33 или N=35.

Лучше наверно писать 5 пунктов. 1 пункт = 0,01 балла.

[dimkadimon]

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

24 = 6*4
6 = 3*2
3 = 2+1
2 = 1+1

Та же длина 4. Получается 3 совсем не лишнее.

Но 24 = 6*4 а 4 не сделали...

[Pavlovsky]

Это уже Оливос работает.

55 20.25 Valery Pavlovsky Ekaterinburg, Russia 20 Feb 2013 14:37

Алгоритм стал работать раз в 100 быстрее. Это я его еще не оптимизировал. Рекордов с его помощью не получить, но результаты на уровне 0,9 балла можно получить, за реальное время, вплоть до N=37.

[Xaositect]

Pavlovsky
Я правильно понимаю, что Вы пока рассматриваете только программы, у которых последние несколько операций - это умножение? Возможно, стоит также проверять, нет ли более "хороших" разложений на множители у недалеко отстоящих от факториала чисел? Хотя, конечно, интуитивно кажется, что с этой точки зрения факториал лучше соседей.

[Nataly-Mak]

Опишу подробно несколько алгоритмов, которые я использую для поиска решений в ручном режиме (помогает отличный инструмент - программа mertz, о которой уже рассказала).

Алгоритм №1

Алгоритм основан на свойстве:
2n! = K * (n!) ^ 2
(2n+1)! = K * (n!) ^ 2

Пример:
N=19

19! = 2 ^ 2 * 5 * 11 * 13 * 17 * 19 * (9!) ^ 2
K = 2 ^ 2 * 5 * 11 * 13 * 17 * 19 = 923780

В качестве начальной последовательности берём любое решение для N = 9, например:

1,2,3,9,8,72,70,5040,362880

Следующий член последовательности – это (9!)^2:

1,2,3,9,8,72,70,5040,362880,131681894400

Теперь осталось составить множитель K=923780.
Составление этого множителя сильно зависит от тех чисел, которые даёт нам начальная последовательность.
В случае выбранной начальной последовательности мне удалось довольно быстро составить множитель K в виде произведения двух чисел:

923780=1292*715

Последний шаг:

19! = K*(9!)^2 = 121645100408832000

Это решение у меня получилось в 17 шагов.

Алгоритм №2

Алгоритм основан на свойстве:
n! = (n-1)!*n=(n-2)!*(n-1)*n=...

Пример:
N=21

21!=19*20*21*18!=7980*18!

Пусть у нас есть решение для N=18 в 13 шагов:

1,2,...,6402373705728000

Осталось составить множитель 7980 из тех чисел, которые даёт нам начальная последовательность.
В моём решении это удалось сделать за два шага:

38,7980

Последний шаг:

7980*18!

В результате получилось решение для N=21 в 16 шагов:

1,2,...,6402373705728000,38,7980,51090942171709440000

Алгоритм №3

Алгоритм выложил Pavlovsky.
Я реализовала эту идею для N=19, взяв в качестве начальной последовательности ту, что выложил Pavlovsky:

1,2,4,6,36,1296,1290,1664100,1662804

Хорошая последовательность. Кстати, потом посмотрела в БД mertz, у него тоже есть аналогичная последовательность.

(Оффтоп)

…
"1664000 = [8] 1,2,4,16,20,320,1280,1300,1664000"
"1663488 = [8] 1,2,4,16,18,288,304,92416,1663488"
"1662810 = [8] 1,2,3,6,36,1296,1290,1664100,1662810"
"1662804 = [8] 1,2,3,6,36,1296,1290,1664100,1662804"
"1661521 = [8] 1,2,3,6,36,1296,1290,1289,1661521"
"1661520 = [8] 1,2,3,6,36,1296,1290,1288,1661520"
…

Надо было ещё догадаться, что 1662804 кратно 46189.

Итак, имеем:

19!=1662804*73156608000

Сомножитель получился большой, составить его быстро не получилось; я затратила на это 7 шагов. Последний шаг – умножение. Получено решение в 16 шагов.

Продолжу...

[Nataly-Mak]

Алгоритм №4

Оливос-Павловский

Это очень интересный алгоритм, мне понравился. Я реализовала его для N=19. Правда, улучшения он не дал, но всё равно интересное решение.

Представляем:

19!= 5*35^2*143*144^4*323

Составляем начальную последовательность, содержащую все нужные числа, участвующие в произведении:

1,2,3,5,7,12,144,143,35,288,323

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

Теперь выполняем серию умножений, и решение готово. Это решение получилось в 16 шагов.

Понятно, что можно сделать много различных разложений N! на произведение данного типа. Сложность в том, чтобы найти самое удачное разложение. Удачное в двух смыслах:
1. в разложение входят множители, для которых можно составить короткую начальную последовательность;
2. разложение должно давать наиболее короткую последовательность умножений.

Если записать:
L=L1+L2
где L - длина готового решения, L1 – длина начальной последовательности, L2 – длина последовательности умножений, понятно, что надо стремиться к минимальности L1 и L2.

Алгоритм №3 применила ещё для нескольких решений.
Например, такая удачная находка:

208012= 2^2*7*17*19*23=322*646

позволила применить этот алгоритм для поиска решений N=23,26.

Ещё один приём - частный случай алгоритма №1:

2n!= K*C*[(n!)^2/C]

Смысл в том, что иногда множитель K*C представить проще, чем множитель K.
Однако приём не всегда применим.
Приведу пример, когда можно применить приём. Это решение для N=9:

1,2,4,8,64,72,70,5184,362880

Теперь следующим членом можно написать не (9!)^2, а (9!)^2/70=1881169920.
Здесь C=70.

[dimkadimon]

Ещё один рекорд. Его скорее всего сделал Tomas Rokicki потому что его очки не упали.

[Pavlovsky]

Xaositect в сообщении #686292 писал(а):

Я правильно понимаю, что Вы пока рассматриваете только программы, у которых последние несколько операций - это умножение?

Несколько это мягко сказано. Я сгенерировал все последовательности длиной 9 и меньше. Сейчас генерирую последовательности длиной 10. А далее использую их в качестве множителей для операций умножения. Получается до 6 операций умножения в конце. Увы этот подход себя исчерпал. Теорема Оливоса здесь не виновата. Оливос готов за считанные минуты обсчитать миллионы начальных последовательностей. Я скормил Оливосу все что у меня было, больше у меня нет. До N<=28 получил приличные результаты. А далее все. Ведь в начальной последовательности должны быть числа кратные всем простым числам <=N. Последовательностей длины 10, содержащих числа кратные всем простым числам, например <=29 очень мало. Оказалось все они плохие для дальнейших операций умножения.

Теперь решаю дилему. Либо выборчно формировать последовательности длины 11 и более. Либо, искать удачные разложения на множители.

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

Понятно, что можно сделать много различных разложений N! на произведение данного типа. Сложность в том, чтобы найти самое удачное разложение. Удачное в двух смыслах:
1. в разложение входят множители, для которых можно составить короткую начальную последовательность;
2. разложение должно давать наиболее короткую последовательность умножений.

Нужны идеи! Нужен Оливос №2.

[Nataly-Mak]

У меня такой фокус получился - "задний ход"

Это решение для N=30, оно состоит из 20 шагов:

1,2,...,204,874,177480,155117520,265252859812191058636308480000000

Здесь 874 и 177480 активные множители, 204 - пассивное число. Всё завершается операциями умножения.

Поставила задачу: как от этого решения получить решение для N=28?
Для этого надо не умножать в конце на 29*30=870. Значит, тогда надо умножить только на 204*874 (заметьте: 177480=870*204).
Замечательно. Выбрасываю активный множитель 177480, остаются два активных множителя: 204 и 874. И готово решение для N=28 в 19 шагов.
Вот такой фокус. Почему "задний ход"? Потому что ищем решение для 28! от решения 30!

Так, 28! поддались немножко, теперь 29! очень плохо - 21 шаг.

[Pavlovsky]

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

Его скорее всего сделал Tomas Rokicki потому что его очки не упали.

Есть первые 25 баллов!

1 25.00 Tomas Rokicki Palo Alto, California, United States 21 Feb 2013 04:37

[Nataly-Mak]

Pavlovsky
вторые 25 баллов должны быть ваши