Factorials

[mertz]

Natalya, it was a memory error that I fixed.

The Run button is where I test. I was working on A216999. I will remove the button when I figure out Natalya's odd number problem.

326876 = 2^2 * 11 * 17 * 19 * 23

sequences can only have the numbers 1, 2, 4, 11, 17, 19, 23. none are possible.

1,2,4,5 no
1,2,4,6 no
1,2,4,8 no
1,2,4,16 no

[Nataly-Mak]

Ещё решения для числа 4200 в 9 шагов (ограничение: только чётные числа):

...
1,2,4,6,36,30,35,1050,1225,4200
1,2,4,6,36,30,35,1050,2100,4200
1,2,4,6,36,30,35,1050,5,4200
1,2,4,6,36,30,35,1080,1050,4200
1,2,4,6,36,30,35,1080,140,4200
1,2,4,6,36,30,35,120,1050,4200
1,2,4,6,36,30,35,120,1080,4200
...

Тут вообще чудеса
В этом решении:

1,2,4,6,36,30,35,1080,1050,4200

зачем число 35 нужно
Мало того, что оно нечётное, так оно и совсем здесь без надобности.
Ведь решение прекрасно получается и без числа 35:

1,2,4,6,36,30,1080,1050,4200

Правда, это решение уже не в 9 шагов, а в 8.

Так сколько же фактически будет решений для числа 4200 в 9 шагов, если решения составляются только из чётных чисел
Интересный вопрос.
Кто-нибудь знает ответ?

[whitefox]

mertz
Вот решение для 326876 состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876

Именно его я хотел найти, но обрезка Non-Factor ищет решения состоящие только из делителей 326876.

А что ответите про Chain Search?

[Nataly-Mak]

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

Вот решение для 326876 состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876

Именно его я хотел найти, но обрезка Non-Factor ищет решения состоящие только из делителей 326876.[/code]

Извините, что вмешиваюсь.
Вы, значит, хотите, чтобы при поиске числа 326876 учитывались только делители 28!
Хорошее требование

[whitefox]

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

Вы, значит, хотите, чтобы при поиске числа 326876 учитывались только делители 28!
Хорошее требование

Решение для числа 326876 ищется не само по себе, а как часть решения для 28!
Логично чтобы оно строилось из делителей 28!

[mertz]

Цитата:

It means that you want to search for the number 326876 into account only the divisors of 28! Good call

I could add an option to select your factor number.

[Nataly-Mak]

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

Решение для числа 326876 ищется не само по себе, а как часть решения для 28!
Логично чтобы оно строилось из делителей 28!

Ну да, и я говорю: хорошее требование.
Однако... реализация его, как мне кажется, не совсем проста.
Надо проверять все делители 28!, которых не так мало.

[whitefox]

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

I could add an option to select your factor number.

Думаю это будет полезно.

-- 01 май 2013, 16:50 --

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

Надо проверять все делители 28!, которых не так мало.

Не очень.
Всего 882000.

[Nataly-Mak]

whitefox
сейчас проверила: решений для числа 326876 в 10 шагов, состоящих только из чётных чисел, всего 67.
Это хвост массива решений:

...
1,2,4,8,10,64,4096,4086,32688,326880,326876
1,2,4,8,10,64,4096,4086,40860,326880,326876
1,2,4,8,10,64,80,4096,4086,326880,326876
1,2,4,8,64,68,72,4608,4540,326880,326876
1,2,4,8,64,72,4608,4536,4540,326880,326876
1,2,4,8,64,72,4608,4544,4540,326880,326876
1,2,4,8,64,72,4608,4604,331488,326880,326876
1,2,4,8,64,72,4608,4604,331488,326884,326876
1,2,4,8,64,72,4608,4604,331488,331480,326876
1,2,4,8,64,72,4608,4604,331488,331484,326876
1,2,4,8,64,72,4608,4604,4540,326880,326876
1,2,4,8,64,72,4608,4612,4540,326880,326876
1,2,4,8,64,72,4608,4612,4604,331488,326876
1,2,4,8,64,72,70,4608,4900,331776,326876
1,2,4,8,64,72,70,5184,4900,331776,326876
1,2,4,8,64,72,70,576,4900,331776,326876
1,2,4,8,64,72,70,576,646,506,326876

Решение, приведённое вами, здесь есть.
Зачем вам обрезка по Non-Factor да ещё не для самого числа 326876, а для 28!

Если можно, покажите, что вы дальше делаете с показанным вами решением для числа 326876 в 10 шагов (с указанной обрезкой)? Вы получаете из него оптимальное решение для 28!

Между делом, запустила поиск решения для 28! от этой вашей последовательности. Так просто, интересно --- достроится или нет? Хотя здесь добавляется аж 6 шагов, что у меня за разумное время не выполняется программой.
Я ввела оба ограничения: только делители 28! и только чётные числа.

[mertz]

New version. Fixed odd number in even only solutions. Fixed a crash caused by a misplaced Mutex. Same links as before.

[Nataly-Mak]

mertz
быстро вы работаете.
Я не успеваю тестировать новые версии
Спасибо!

[whitefox]

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

сейчас проверила: решений для числа 326876 в 10 шагов, состоящих только из чётных чисел, всего 67.
Зачем вам обрезка по Non-Factor да ещё не для самого числа 326876, а для 28!

Если можно, покажите, что вы дальше делаете с показанным вами решением для числа 326876 в 10 шагов (с указанной обрезкой)? Вы получаете из него оптимальное решение для 28!

Очень эффективной оказалась эвристика -- строить решение для N! только из делителей N!

Так как $28! =1651104000^2\cdot326876\cdot342144$ и все три числа делят 28!, найдём решение для 326876 состоящее только из делителей 28!, продолжим его до 342144 (также используя только делители 28!), полученную последовательность продолжаем до 1651104000 (опять используя только делители 28!), выполняем три завершающих умножения и получаем решение для 28! состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144, 1651104000
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144, 1651104000, 2726144418816000000, 891111183044898816000000, 304888344611713860501504000000

[Nataly-Mak]

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

Очень эффективной оказалась эвристика -- строить решение для N! только из делителей N!

Так как $28! =1651104000^2\cdot326876\cdot342144$ и все три числа делят 28!, найдём решение для 326876 состоящее только из делителей 28!, продолжим его до 342144 (также используя только делители 28!), полученную последовательность продолжаем до 1651104000 (опять используя только делители 28!), выполняем три завершающих умножения и получаем решение для 28! состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876

Итак, от найденных мной 67 решений для числа 326876 в 10 шагов (состоящих только из чётных чисел) выполняю первый этап по вашему сценарию: достраиваю до числа 342144:

found 3 solutions for 342144 in 12 steps
1,2,4,8,64,72,70,5184,4900,331776,326876,10368,342144
1,2,4,8,64,72,70,5184,4900,331776,326876,336960,342144
1,2,4,8,64,72,70,5184,4900,331776,326876,66,342144

[ограничение Non-Factor не действует здесь]
Сейчас пойду выполнять от найденных решений второй этап - достраивание до числа 1651104000.
Получится?

А почему же не получится?
Вот оно:

found 1 solutions for 1651104000 in 13 steps
1,2,4,8,64,72,70,5184,4900,331776,326876,336960,342144,1651104000

Вывод: совершенно напрасно вы морочили голову с обрезкой Non-Factor (да ещё по делителям 28!). Всё прекрасно получается с одним ограничением: только чётные числа. Решений очень мало даже на первом этапе - всего 67.

-- Ср май 01, 2013 17:34:16 --

Обалдеть
Программа поиска решений от вашей последовательности для числа 326876 закончила работу!
Программа работала всего 39 мин. 15 сек. Фантастика!

found 9 solutions for 304888344611713860501504000000 in 16 steps
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,111838662144,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,111838662144,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,891111183044898816000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,932733956031381504000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,564915326976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,891111183044898816000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,564915326976000,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,564915326976000,932733956031381504000000,304888344611713860501504000000

Вот! Сразу в лоб от числа 326876 достроилось до 28!
И можно точно так же достроить, начиная от всех 67 решений для числа 326876, только в этом случает программа будет намного дольше выполняться.

P.S. Интересно: в этих решениях сначала найдено число 1651104000, а потом число 342144.

[whitefox]

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

Вывод: совершенно напрасно вы морочили голову с обрезкой Non-Factor (да ещё по делителям 28!). Всё прекрасно получается с одним ограничением: только чётные числа. Решений очень мало даже на первом этапе - всего 67.

В данном частном случае всё прекрасно получается и без каких-либо ограничений.
На моей машине за три минуты находятся все 187 решений в 10 шагов для 326876, за несколько секунд они достраиваются до 5 решений в 12 шагов для 342144, а достройка до одного решения в 13 шагов для 1651104000 выполняется вообще мгновенно.

Всё дело в том, что нам известно, что разложение $28! =1651104000^2\cdot326876\cdot342144$ даёт оптимальное решение.
Но когда такой информации нет, пространство поиска слишком велико, и разумно использовать упомянутую выше эвристику для его существенного сокращения.

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

Выше Вы описывали с какими трудностями столкнулись при поиске решения для 22!
Их бы не было ищи Вы решение для 4200 состоящее из делителей 22! и продолжив затем его до решения для 7983360, также состоящее из делителей 22!
1,2,4,6,24,144,864,840,5040,4200,9240,7983360

[Nataly-Mak]

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

Всё дело в том, что нам известно, что разложение $28! =1651104000^2\cdot326876\cdot342144$ даёт оптимальное решение.
Но когда такой информации нет, пространство поиска слишком велико, и разумно использовать упомянутую выше эвристику для его существенного сокращения.

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

-- Ср май 01, 2013 18:14:21 --

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

Выше Вы описывали с какими трудностями столкнулись при поиске решения для 22!
Их бы не было ищи Вы решение для 4200 состоящее из делителей 22! и продолжив затем его до решения для 7983360, также состоящее из делителей 22!
1,2,4,6,24,144,864,840,5040,4200,9240,7983360

Если вы внимательно читали эти самые описанные мной трудности, то должны были бы заметить, что и в этом примере я прекрасно вышла из положения, введя ограничение при поиске решений для числа 4200 в 9 шагов - только чётные числа!
И это дало решение за считанные минуты.
Никаких ограничений по делителям 22! я не использовала.

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

И вот! Чего не сообразила надо было искать решения для числа 4200 в 9 шагов только с чётными числами!
Ищу сейчас такие решения, программа выдаёт всего 4332 решения.

Теперь беру эти 4332 решения для числа 4200 и достраиваю их до числа 7983360 в два шага.
Вот они - эти решения:

found 2 solutions for 7983360 in 11 steps
1,2,4,6,24,144,864,840,5040,4200,9240,7983360
1,2,4,6,24,36,864,840,5040,4200,9240,7983360

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