Factorials

[Nataly-Mak]

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

Применяем преобразование A(A+1)B^2=(AB)(AB+B)
322*(322+1)*12636* 4435200^2
(322*4435200)*(322*4435200+4435200)*12636
1,2,3,9,27,36,324,351,322,12636,4435236,4435200, 1428134400, 1432569600, 2045901926154240000, 25852016738884976640000
Итого 15 операций

Ну, тут, по-моему, главное было найти вот это хорошее разложение:

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

А уж применить оптимальную схему вычисления этого выражения, наверное, догадался бы каждый.

Кстати, я где-то писала об этой интересной находке:

$104006 = 322 \cdot (322+1)=322^2+322=323^2-323=2 \cdot 7 \cdot 17 \cdot 19 \cdot 23$

Не пошла чуточку дальше

[Pavlovsky]

dimkadimon
Я достаточно много времени уделил поиску преобразований, но увы ничего другого не нашел.

Перебор основным алгоритмом я организовал так: порог на длину последовательности задавал на единицу хуже рекордного. Причем алгоритм не останавливался на первом найденом решении, а продолжал работать пока не будут найдены все последовательности меньше или равные заданному порогу. Затем просматривал все найденные последовательности, на возможность применить преобразование.
Посмотрел свои решения.

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

половины моих решений дотачивалось этим преобразованием!

Тут я немного соврал. Практически все мои решения получены преобразованием A(A+1)B^2=(AB)(AB+B).

[dmd]

21! (база 1,2,4,6,24):

$(6 x (6 x + 6) (6 x + x))^2 (6 x + 6 + 4) ((6 x + 6) (6 x + x) - 6)$

[Nataly-Mak]

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

Ну, тут, по-моему, главное было найти вот это хорошее разложение:

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

А уж применить оптимальную схему вычисления этого выражения, наверное, догадался бы каждый.

Сейчас по приведённому разложению организовала поиск решения в программе mertz.

1 этап
ищу все решения для числа 12636 в 8 шагов. Найдено 279 решений.

2 этап
от найденных последовательностей ищу решения, в которых 9-ым шагом появляется число 322. Найдено 15 решений:

1,2,3,4,9,36,39,324,12636,322
1,2,3,6,18,21,324,39,12636,322
1,2,3,6,18,36,324,39,12636,322
1,2,3,6,36,39,108,324,12636,322
1,2,3,6,9,36,39,324,12636,322
1,2,3,9,12,108,324,117,12636,322
1,2,3,9,12,27,39,324,12636,322
1,2,3,9,12,36,39,324,12636,322
1,2,3,9,18,21,324,39,12636,322
1,2,3,9,18,36,324,39,12636,322
1,2,3,9,27,36,324,351,12636,322
1,2,3,9,27,36,39,324,12636,322
1,2,3,9,81,162,78,160,12636,322
1,2,3,9,81,162,78,161,12636,322
1,2,3,9,81,162,78,324,12636,322

3 этап
от найденных решений ищу решения для числа 4435200 в 11 шагов. Найдено только одно решение:

found 1 solutions for 4435200 in 11 steps
1,2,3,9,27,36,324,351,12636,322,4435236,4435200

Последним этапом выполняем 4 операции и получаем готовое решение:

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

[wanderers]

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

dimkadimon
Сейчас уместно привести сообщение YuriiS на форуме ПЕН:
http://e-science.ru/forum/index.php?s=& ... t&p=393039

Цитата:

Если у кого есть желание и минута свободного времени, то развейте "страшные" слухи по поводу 19! на dxdy: это как раз самый благоприятный вариант из всех возможных для компьютерной реализации - у меня он проходит за неуловимые доли секунды. При расчете не учитывалась специфика 19!, а использовался общий подход.

YuriiS участник конкурса (см. Yurii Sigolaev).

У меня есть предположение, что здесь речь идёт о поиске только одного решения, а не всех 9 решений (а и всех-то, кажется, не 9 ), но могу ошибаться. Хотя трудно поверить, что полный поиск для 19! может выполниться за "неуловимые доли секунды"
Это всё-таки решения в 13 шагов!

Как я понимаю, Yurii Sigolaev сильно "загнул". Давайте рассмотрим одно из решений для 19!:
1, 2, 4, 16, 14, 18, 224, 220, 324, 104976, 23514624, 23514400, 5173217280, 19!
В свете описанного мною выше подхода имеем:
x=104976
a=224
y=220
x*a=23514624
x*a-a=23514400
(x*a)*(x*a-a)=5173217280
(x*a)*(x*a-a)*y=19!
Но (x), (a) и (y) находятся в первой десятке! Что это значит? А это значит то, что решение уже забито в моей базе данных (я писал, что последовательности в моей базе данных состоят из 10 чисел, а точнее, устроены еще более хитро: в виде буквы "T", о чем я писал во втором моем сообщении), т.е. уже никаких расчетов делать нет необходимости - необходим только поиск уже готового решения!!! А база занимает у меня порядка 600 мегабайт. Делим 600 на 14 (число доступных ядер на моих трех компах) и получаем порядка 40 мегабайт. Но такую порцию информации за неуловимые доли секунды с харда не считать. Так что Yurii Sigolaev - это барон Мюнхаузен в чистом виде. Еще не забываем, что требуется далеко не секунды для генерации таблиц, в которых и "зарыта собака" эффективного и однообразного решения конкурсной задачи. Хотя Yurii Sigolaev может пользовался более феноменальным алгоритмом, который я описал: это необходимо спросить у него. Весьма вероятно, что он имел в виду расчетное время: тогда он прав - нет даже и неуловимых долей секунды, о которых он писал. Теперь о трудностях с 28!: строчка (111838662144 1651104000) в сгенерированной мною таблице является 282-ой!!! Это и обусловило трудности нахожденя решения (не у меня - поиск решения моим методом длится несколько секунд на 14 ядрах).

[whitefox]

Gerbicz в сообщении #674406 писал(а):

This puzzle is good for small kids to play with numbers and operations.

Gerbicz в сообщении #713295 писал(а):

In spoj I would set these problems to the tutorial section, ideal for small kids, up to 12 years.

Гы-гы-гы
Это такая методика -- объявить "детской" задачу которую не можешь решить.

Эзоп писал(а):

Под лозами лиса, терзаясь голодом,
До виноградных гроздьев вспрыгнуть силилась,
Но не смогла, и уходя, промолвила:
«Еще незрел он: не люблю кислятины!»
Кто на словах порочит непосильное.
Свое здесь должен видеть поведение.

Та же басня в английском переводе:

Aesop писал(а):

Driven by hunger, a fox tried to reach some grapes hanging high on the vine but was unable to, although he leaped with all his strength. As he went away, the fox remarked, 'Oh, you aren't even ripe yet! I don't need any sour grapes.' People who speak disparagingly of things that they cannot attain would do well to apply this story to themselves.

[Nataly-Mak]

Мне удалось воспользоваться другим преобразованием, предложенным Pavlovsky:

$A(AC-1)B^2=AB(ABC-B)$

Правда, решение получено не оптимальное, а 16 шагов, но у меня и 16 шагов очень долго не получалось.
Разложения под это преобразование нашёл whitefox, таких разложений очень много.

$24! =191600640^2 \cdot 323 \cdot (323 \cdot 162-1)$

Решение:

1,2,3,9,81,162,324,323,171,13851,13842,191600964,191600640,61887006720,10025695088640,10025503488000,620448401733239439360000

Pavlovsky
у вас есть оптимальные решения, полученные на основе приведённого преобразования?

[Pavlovsky]

Преобразование можно использовать для получения оптимального решения для 24!
Начальная последовательность: 1,2,4,16,18,324,308,104976
Разложение: 24!=104976*104975*18*322*(308*320)^2
Преобразование: (104976*308*320)*(104976*308*320-308*320)*18*322
Решение:
1,2,4,16,18,324,308,104976, 320, 322, 98560,10346434560,10346336000, 107047688359772160000, 1926858390475898880000, 620448401733239439360000

[wanderers]

Хочу отметить, что 24! вписывается в парадигму (y, x, a).

[Pavlovsky]

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

Pavlovsky
у вас есть оптимальные решения, полученные на основе приведённого преобразования?

Преобразование $A(AC-1)B^2=AB(ABC-B)$ мне удалось применить лишь однажды для 23!

[wanderers]

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

[Pavlovsky]

wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются.

[Nataly-Mak]

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

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

Вот это

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

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

Цитата:

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

Она единственная для 23! или есть другие?

[wanderers]

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

wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются.

Я об этом и не думаю: просто считаю, что приводимая мною информация как раз и поможет сократить ваше время для обдумывания.

[dimkadimon]

На сайте есть оптимальные решения в которых есть +/-1. Можно ли их улучшить преобразованиями? Например:

N=29:
1, 2, 4, 8, 64, 68, 544, 540, 539, 552, 34560, 35100, 18918900, 653837184000, 360918125568000, 360264288384000, 130025911672642675802112000000, 8841761993739701954543616000000

N=31:
1, 2, 3, 4, 12, 14, 168, 672, 675, 8100, 7425, 7424, 1247400, 1255500, 838252800, 1052426390400000, 1052427228652800, 7813219745518387200, 8222838654177922817725562880000000

N=35:
1, 2, 4, 6, 36, 35, 216, 220, 864, 880, 874, 899, 30240, 785726, 6652800, 6683040, 5227277932800, 44460928512000, 232409630482575939993600000, 10333147966386144929666651337523200000000

N=36:
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 265914909018965606400000, 371993326789901217467999448150835200000000

N=37:
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 50361071569256448000, 51759990223958016000, 2068866205391165380939751620608000000, 13763753091226345046315979581580902400000000
1, 2, 4, 6, 36, 35, 37, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 55915302848409875160533827584000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000