Factorials

[Nataly-Mak]

Итак, положение России на конкурсе:

Цитата:

5 Israel 4
10 China 4
12 Russia 19
29 India 16
88 Vietnam 8
95 Indonesia 1
101 Japan 5
162 Philippines 1
213 Singapore 1
284 Taiwan 1
333 Iran 1
337 Hong Kong 1
343 Thailand 1
385 Sri Lanka 1

Почётное 3-е место
Зато по количеству участников на первом месте.
Не взяли качеством, взяли количеством

[wanderers]

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

wanderers в сообщении #713888 писал(а):

И 23! вписывается также в парадигму (y, x, a).

Вот это

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

и есть та самая парадигма?

Цитата:

n!=(x*a)(x*a+a)*y

Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц. Хотя сам алгоритм не так прост: на c это несколько тысяч операторов (к сожалению, отладить полностью алгоритм для случая (y, x, a) к 10 апреля не сумел, по этой причине даже не удалось к этому времени посчитать 27!, т.к. 11 апреля отбыл в командировку и появился только утром 20 апреля. Надеялся, что успею выловить баги, но это случилось только поздним вечером 20 апреля). И потом, в вашей записи решения лишняя операция.

[dimkadimon]

wanderers в сообщении #713899 писал(а):

Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц.

Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?

[wanderers]

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

wanderers в сообщении #713899 писал(а):

Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц.

Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?

Такая задача перед конкурсантами не ставилась: я действовал в рамках поставленной задачи. Мне вот более интересно, с чего это победители конкурса людям мозги "компостируют"?

P.S.
Я уже ранее писал, что достаточно взглянуть на решения для 13!, 14!, 15!, 16! и 17!, чтобы понять, что все оптимальные решения достаточно разнообразны и не вписываются в мой метод.

[Nataly-Mak]

wanderers в сообщении #713899 писал(а):

Существуют решения с x=322 и с x=223...

Может быть, с x=224?

$23! = 224 \cdot (224+1) \cdot 1330560^2 \cdot 289731$

[dimkadimon]

wanderers в сообщении #713906 писал(а):

Такая задача перед конкурсантами не ставилась: я действовал в рамках поставленной задачи. Мне вот более интересно, с чего это победители конкурса людям мозги "компостируют"?

P.S.
Я уже ранее писал, что достаточно взглянуть на решения для 13!, 14!, 15!, 16! и 17!, чтобы понять, что все оптимальные решения достаточно разнообразны и не вписываются в мой метод.

Перефразирую свой вопрос. Может ли ваш метод набрать 25 в конкурсе? Мой опыт показал что найти оптимальные решения для N<=27 не достаточно, так как найти оптимальные решения для N>27 гораздо сложнее.

Например для больших N вашей таблицы может не хватить. Конечно таблицу можно увеличить, но она будет расти очень быстро и время просмотра этой таблицы тоже будет расти.

[Nataly-Mak]

wanderers в сообщении #713899 писал(а):

И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23!

1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

Но здесь решение в 15 шагов. Разве для 23! есть решение в 14 шагов?

[wanderers]

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

wanderers в сообщении #713899 писал(а):

Существуют решения с x=322 и с x=223...

Может быть, с x=224?

$23! = 224 \cdot (224+1) \cdot 1330560^2 \cdot 289731$

Уточняю: расчет 23! и 24! проводился на более примитивном уровне, т.к. к этому времени отладка для (y, x, a) была еще не завершена: как только появлялось решение или группа решений, я снимал задачу. Но для расчета 27! этот метод для меня уже не годился, т.к. более часа я не готов был ждать решения.

[Nataly-Mak]

Ничего не поняла в вашем уточнении.

Пожалуйста, приведите парадигму для x=223 в виде числового разложения.
Я такое разложение не нашла, а нашла то, что показано выше (x=224).

Да, и где вы видите в моём решении для 23! лишнюю операцию?

[Pavlovsky]

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

Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?

Естественно нет. Но оцените решение для 37! на единицу хуже оптимального.

1,2,3,9,18,36,648,666,443556
37!=666*651*443555*34^2*650^2*443520^3*648^2*2^2
После преобразования получается решение в 21 операцию.

Используется начальная последовательность всего в 8 операций (9 чисел). Процедура разложения на множители работает не просто быстро, а очень быстро. То есть получить решение для 37! в 21 операцию можно используя очень скромные вычислительные ресурсы!
Конечно, если бы мы взяли начальную последовательность
1,2,3,9,18,36,648,666,443556,651,443520,443520*651
Тогда мы бы нашли решение в 21 операцию и без преобразований. Но удлинить последовательность на три числа это означает рассмотреть более 100 тысяч вариантов. То есть без применения преобразования, поиск бы шел в сотни тысяч раз дольше!

[wanderers]

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

wanderers в сообщении #713899 писал(а):

И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23!

x=322
y=12636
a=4435200
У вас
1.x+1
2.x*(x+1)
3.(x*(x+1))*y
4.a*a
5.[(x*(x+1))*y]*(a*a)
У меня
1.x*a
2.x*a+a
3.(x*a)*(x*a+a)
4.[(x*a)*(x*a+a)]*y

Ваш второй вопрос не понял.

[Nataly-Mak]

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

wanderers в сообщении #713899 писал(а):

И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23!

1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

Но здесь решение в 15 шагов. Разве для 23! есть решение в 14 шагов?

Ещё раз, пожалуйста, посмотрите на моё решение.
В нём же 15 шагов. В 14 шагов вроде нет решения для 23!

Цитата:

У вас
1.x+1

Где вы видите в моём решении (x+1)?

Второй вопрос.
Вы пишете, что есть решение для x=223.
Я прошу привести это решение, ну или хотя бы разложение для x=223.

[wanderers]

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

Где именно лишняя операция? В решении для 23!

Второй вопрос.
Вы пишете, что есть решение для x=223.
Я прошу привести это решение

Вы писали:
$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$
В такой записи 5 операций.

1,2,3,9,27,36,324,323,351,12636,4435236,4435200,1428134400,1432569600,2045901926154240000,25852016738884976640000

x=323
y=12636
a=4435200
1.x*a
2.x*a-a
3.(x*a)*(x*a-a)
4.[(x*a)*(x*a-a)]*y

[Nataly-Mak]

wanderers в сообщении #713957 писал(а):

Вы писали:
$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$
В такой записи 5 операций.

Где 5 операций?
Я нахожу число 4435200 за 11 шагов:

1,2,3,9,27,36,324,351,12636,322,4435236,4435200

Это понятно?
В вашем решении ведь то же самое! Число 4435200 стоит в последовательности 11-ым шагом:

1,2,3,9,27,36,324,323,351,12636,4435236,4435200 

Разве не так?

Далее завершаю вычисление 23! за 4 операции!

1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

Где вы видите какие-то 5 операций?
Вы привязались к своему решению и не хотите понять решение, которое чуть-чуть отлично от вашего.

Это разложение

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

можно записать и так:

$23! = 323\cdot (323-1) \cdot 12636 \cdot 4435200^2$

Никакой разницы нет абсолютно.

[Pavlovsky]

Прочитал описание алгоритмов лидеров. Понравилось:
tomrokicki

Цитата:

Fifth, I pregenerated all possible equations a+b=c where a and b are
relatively prime and a, b, and c are all factors of 37!. There turns
out to be only a small number of these, and they fit in a small hash
table, so I was able to use this to restrict the additions and
subtractions I performed to those resulting in factors, efficiently.
(Side puzzle for those who haven't done it already: how fast can you
generate all of these equations, and how many are there?)

Это к вопросу как складывать, вычитать числа представленные ввиде разложения на простые множители.