Factorials

[whitefox]

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

Что изменилось бы в показанном мной поиске, если бы у меня не было "такой информации" (что оптимальное решение для данного разложения существует)???
Ровным счётом ничего не изменилось бы!

Для данного разложения не изменилось бы.
Но это разложение единственное приводящее к оптимальному решению, а нам пришлось бы проверять все возможные разложения. Именно для этого и нужно сокращение пространства поиска, чтобы проверка каждого разложения выполнялась максимально быстро.

-- 01 май 2013, 18:22 --

Выполняя обрезку Non-Factor только по делителям числа 4200 мы быстро найдём около 5000 решений в 9 шагов, но вот достроить их до решения 7983360 в 11 шагов при обрезке Non-Factor для делителей 7983360 уже не получится.

-- 01 май 2013, 18:24 --

Проверил, и без обрезки достроить не получится.
Так, что при построении решения для 4200 нужно брать именно делители 22!, делителей 4200 никак не достаточно.

[Nataly-Mak]

whitefox в сообщении #718331 писал(а):

Но это разложение единственное приводящее к оптимальному решению, а нам пришлось бы проверять все возможные разложения.

Ну почему же единственное?
Я нашла оптимальные решения для 21!,25!, 30!
И для этих разложений я тоже не знала, что они дают оптимальное решение.
И тем не менее, нашла решения без всяких вообще ограничений (даже на чётные числа).

Цитата:

Именно для этого и нужно сокращение пространства поиска, чтобы проверка каждого разложения выполнялась максимально быстро.

Ну, а проверка всех разложений этим кустарным методом вообще нереальна
Всё это по-хорошему надо полностью автоматизировать.
А я все разложения проверяла этим примитивным способом. Сколько их проверила? 50? 100? А сколько не проверила? Много сотен!

-- Ср май 01, 2013 18:28:30 --

whitefox в сообщении #718331 писал(а):

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

Выполняя обрезку Non-Factor только по делителям числа 4200 мы быстро найдём около 5000 решений в 9 шагов, но вот достроить их до решения 7983360 в 11 шагов при обрезке Non-Factor для делителей 7983360 уже не получится.

-- 01 май 2013, 18:24 --

Проверил, и без обрезки достроить не получится.

Опять не поняла юмора.
Я же привела решения именно найденные от решений для 4200 в 9 шагов с ограничением - только чётные числа (посмотрите цитату в предыдущем посте).
Ограничение не по делителям числа 4200, а ограничение - только чётные числа.
Таких решений программа выдала 4332, но фактически их ещё меньше (была ошибка в программе и в решениях попадались нечётные числа).

[whitefox]

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

Ну почему же единственное?
Я нашла оптимальные решения для 21!,25!, 30!
И для этих разложений я тоже не знала, что они дают оптимальное решение.
И тем не менее, нашла решения без всяких вообще ограничений (даже на чётные числа).

Единственное для 28! (может есть и другие, но нам сие не известно).

[Nataly-Mak]

Цитата:

Так, что при построении решения для 4200 нужно брать именно делители 22!, делителей 4200 никак не достаточно.

Да не надо брать вообще никаких делителей
Достаточно строить решения из чётных чисел.
Вы, похоже, мои сообщения не читаете

-- Ср май 01, 2013 18:40:26 --

whitefox в сообщении #718343 писал(а):

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

Ну почему же единственное?
Я нашла оптимальные решения для 21!,25!, 30!
И для этих разложений я тоже не знала, что они дают оптимальное решение.
И тем не менее, нашла решения без всяких вообще ограничений (даже на чётные числа).

Единственное для 28! (может есть и другие, но нам сие не известно).

Повторюсь: ничего не изменилось бы в моём поиске, если бы я не знала, что это разложение даёт оптимальное решение.
Привела примеры других разложений, о которых ничего не знала, но решения оптимальные по ним нашла. И поиск вёлся вообще без всяких ограничений. И нашлось всё это довольно быстро (не за сутки и не за часы, а за минуты).
И вы сами сейчас в этом убедились на вашем же примере для 28!
Без всяких ограничений решение находится за минуты.

[whitefox]

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

Опять не поняла юмора.
Я же привела решения именно найденные от решений для 4200 в 9 шагов с ограничением - только чётные числа (посмотрите цитату в предыдущем посте).
Ограничение не по делителям числа 4200, а ограничение - только чётные числа.
Таких решений программа выдала 4332, но фактически их ещё меньше (была ошибка в программе и в решениях попадались нечётные числа).

Эд заложил в своей программе использование двух эвристик:
1. использовать в решение только чётные числа
2. использовать только делители N!

Я и отметил, что вторая эвристики реализована не совсем верно.
Она сработает если мы будем искать непосредственно N!
Но если мы строим N! по частям, то есть будем искать какой-то делитель N!, то как в примере с 4200 и 22!, решение найдено не будет.

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

-- 01 май 2013, 18:49 --

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

Да не надо брать вообще никаких делителей
Достаточно строить решения из чётных чисел.
Вы, похоже, мои сообщения не читаете

Читаю.
И очень внимательно.

Вы говорите о том, что в данных примерах эвристики чётных чисел вполне достаточно.

Полностью с этим согласен.

Но я-то говорил о совершенно другом -- о том что эвристика делителей N! в программе Эда реализована не совсем верно.

[Nataly-Mak]

whitefox в сообщении #718350 писал(а):

Эд заложил в своей программе использование двух эвристик:
1. использовать в решение только чётные числа
2. использовать только делители N!

Сие мне известно

Цитата:

Но я-то говорил о совершенно другом -- о том что эвристика делителей N! в программе Эда реализована не совсем верно.

И это мне было понятно с самого начала --- чего вы хотите от программы Эда.

А я всё время говорила о том, что реализовывать вторую эвристику так, как требуете вы, совсем не нужно.
И у меня есть тому как минимум 5 примеров - оптимальные решения для N=21,22,25,30 и 28 (по приведённому вами сейчас разложению).
Во всех этих примерах решения строятся без второй эвристики в какой бы то ни было её реализации. Ну вот совсем она не использовалась тут

P.S. Я использовала сейчас вторую эвристику (вместе с первой), когда достраивала ваше решение для числа 326876 сразу до 28!
(найденные 9 решений приведены выше)

[whitefox]

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

А я всё время говорила о том, что реализовывать вторую эвристику так, как требуете вы, совсем не нужно.
И у меня есть тому как минимум 5 примеров - оптимальные решения для N=21,22,25,30 и 28 (по приведённому вами сейчас разложению).
Во всех этих примерах решения строятся без второй эвристики в какой бы то ни было её реализации. Ну вот совсем она не использовалась тут

Эд выложил программу для общего пользования.
То что Вы не пользуетесь второй эвристикой не означает, что ей никто не будет пользоваться. А потому она должна быть реализована корректно.

[Nataly-Mak]

whitefox в сообщении #718365 писал(а):

Эд выложил программу для общего пользования.

Это мне тоже известно.

Цитата:

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

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

А говорила я о том, что в приведённом вами конкретном примере для 28! пользоваться этой эвристикой совсем не нужно (как, впрочем, и в 4 других примерах оптимальных решений).
Решения находятся очень быстро только с использованием первой эвристики (как для 22! и 28!) или вообще без всяких ограничений (как в случаях для N=21,25,30).

Если же добавить эту эвристику при поиске решений для промежуточных чисел (например, числа 326876 или числа 4200), то это наверняка приведёт к замедлению поиска, так как будут проверяться все делители N!.
Так что, ещё не известно, ускорим мы таким способом поиск или замедлим его.
Я склонна думать, что замедлим.
Одним словом, наша дискуссия зашла в тупик. Оба оппонента остаются при своём мнении.
Никто никого не переубедил.

[mertz]

Do you want to prune by 326876 AND 28! at the same time?

[Nataly-Mak]

mertz в сообщении #718374 писал(а):

Do you want to prune by 326876 AND 28! at the same time?

mertz
это вы кого спрашиваете?
Я ничего не хочу.
А вот whitefox, кажется, хочет. Но он вам сам скажет, чего он хочет.

[whitefox]

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

Одним словом, наша дискуссия зашла в тупик. Оба оппонента остаются при своём мнении.
Никто никого не переубедил.

Но почему же.
Я с самого начала был согласен с Вами, что эвристики четных чисел вполне достаточно для нахождения решений в приведённых Вами примерах.

Но я не знаю какая эвристика лучше -- первая или вторая.
Хотел это проверить, но столкнулся с проблемой -- при текущей реализации второй эвристики, программа иногда не находит заведомо существующее решение. Пример, оптимальное решение для 22!, содержащее числа 4200, 7983360 и состоящее только из делителей 22!

-- 01 май 2013, 19:58 --

mertz в сообщении #718374 писал(а):

Do you want to prune by 326876 AND 28! at the same time?

Пусть m=326876, M=28!
Думаю, что в общем случае нужно искать решение для m, состоящее только из делителей общего наименьшего кратного чисел m и M -- lcm(m, M) (Least Common Multiple).

[Nataly-Mak]

А тем временем

Цитата:

1 240 Wes Sampson La Jolla, California, United States 1 May 2013 14:11

Здорово!

-- Ср май 01, 2013 21:00:00 --

Поскольку желающих развернуть мою упаковку для 22! не наблюдается, пришлось самой тряхнуть стариной - вспомнить школьную алгебру

И вот он - полином для 22!

$f(x)=764411904 x^{16}-2802843648 x^{15}[phone] x^{14}-3231055872 x^{13}[phone] x^{12}-440598528 x^{11}[phone] x^{10}-12017664 x^9+995328 x^8-36864 x^7$

$f(6)=22!$

Упаковка полинома показана выше. Здесь я как раз развернула упаковку.

Конечно, помог Вольфрам, скормила ему вот это, полученное вручную:

$f(x)=384 x^4(12 x^2-8 x+1)(6 x^2-7 x+1)(384 x^4(12 x^2-8 x+1)(6 x^2-7 x+1)-96 x^3(12 x^2-8 x+1)) $

[whitefox]

Было найдено, по существу, единственное оптимальное решение для 36! из разложения
$36! =6652800\cdot39970374732288000\cdot1398918654701568000$

Это решение может быть построено при помощи эвристики делителей N!
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 265914909018965606400000, 36!

Но эвристика чётных чисел его не найдёт, так как в решение присутствует число 899.

-- 01 май 2013, 22:19 --

Интересно ещё то, что оптимальное решение для 6652800 имеет 9 шагов.
Но при построении решения 36! используется решение для 6652800 из 11 шагов, на 2 шага больше оптимального.

[Nataly-Mak]

whitefox в сообщении #718444 писал(а):

Было найдено, по существу, единственное оптимальное решение для 36! из разложения
$36! =6652800\cdot39970374732288000\cdot1398918654701568000$
Интересно ещё то, что оптимальное решение для 6652800 имеет 9 шагов.
Но при построении решения 36! используется решение для 6652800 из 11 шагов, на 2 шага больше оптимального.

А почему нельзя использовать, например, такое решение для числа 6652800 в 10 шагов:

1,2,4,6,36,35,216,220,864,30240,6652800

?
Хотя и в этом решении есть нечётное число, но решения в 10 шагов найти проще и без всяких эвристик, нежели решения в 11 шагов.

[whitefox]

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

А почему нельзя использовать, например, такое решение в 10 шагов:

Число 6652800 нужно не само по себе, а как часть решения для 36!
Попробуйте продолжить свою последовательность, возможно найдёте второе решение для 36!
Кстати Ваша последовательность тоже отвечает эвристике делителей.