Factorials

[Nataly-Mak]

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

Полёт нормальный

Ой, на Марс не улетите

[whitefox]

(Оффтоп)

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

Ой, на Марс не улетите

Я по быстрому.
Только до Луны и обратно.

[Nataly-Mak]

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

Работаю по предыдущей версии программы --- от 1 мая (обрезка non-factor есть, но реализована не корректно, по утверждению whitefox).

Эксперимент

Поиск начальных последовательностей для числа 6652800 в 10 шагов;
ставлю галочку в "non-factor".
Программа работает меньше одной минуты, найдено 557 последовательностей
[напомню: без использования эвристики последовательностей было найдено 924, время работы программы - 23 мин. 20 сек. Да, ускорение значительное, но! 367 потерянных последовательностей, среди которых могут быть последовательности, дающие решение].

Второй этап. Ищу от найденных 557 последовательностей число 39970374732288000, добавляя к последовательности 4 шага. Снова ставлю галочку в "non-factor"
Программа работала 1 мин. 26 сек. Найдены всё те же три решения, которые были найдены безо всяких эвристик.

whitefox
можно вопрос?
В описанном эксперименте я нашла все решения для числа 39970374732288000, состоящие только из делителей этого числа (так как использовала обрезку non-factor по делителям этого числа).
Но число 39970374732288000 является делителем 36!, следовательно, все его делители тоже являются делителями 36!

Я никак не возьму в толк, чего вы сейчас ищете
Просветите, пожалуйста.

[whitefox]

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

Я никак не возьму в толк, чего вы сейчас ищете
Просветите, пожалуйста.

Описанный Вами эксперимент я тоже проводил.
Да и оптимальные решения для 36! нам известны.
По существу это одно решение, и состоит оно только из делителей 36!
Так что, я не ищу само решение, а исследую эффективность различных эвристик.

-- 03 май 2013, 09:41 --

Эксперимент завершился.
На этот раз без краха



mertz
Причиной краха было что-то другое.
Тем не менее баг Вы пофиксили.

[Nataly-Mak]

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

Так что, я не ищу само решение, а исследую эффективность различных эвристик.

Да это мне как раз понятно.
Мне хочется понять суть вашего теперешнего эксперимента.

Сама рассуждаю...
Возможно, вы хотите по новой эвристике получить последовательности для числа
39970374732288000, в которых есть делители 36!, не являющиеся делителями искомого числа. Так?
А иначе какой смысл в поиске последовательностей, состоящих из делителей 36!, которые одновременно являются и делителями искомого числа, если этот эксперимент уже проводился. И понятно же, что по обрезке только для делителей искомого числа программа выполнится намного быстрее, чем по обрезке по делителям 36!
Это и подтверждает приведённый эксперимент.

Итак, 37 минут против 1 минуты и... ничего нового не найдено. Всё те же три решения.
Теперь за вами пример, когда по делителям N! решений находится больше, чем по делителям искомого числа.
Если я вообще это правильно понимаю.

-- Пт май 03, 2013 09:49:33 --

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

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

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

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

Вот он --- пример. Верно?
Надо искать решения для 4200 с обрезкой по делителям 22!
Итак... эксперимент века

-- Пт май 03, 2013 10:08:36 --

За 2 мин. 38 сек. найдено 17595 решений для числа 4200 в 9 шагов с non-factor по 22!
Запустила от этих решений программу достраивания до числа 7983360 за 2 шага на страх и риск - слишком много начальных последовательностей.
Программа отработала 7%, решения нашла (Found 2) и зависла.
Да, есть два решения от этих начальных последовательностей.

Заметьте: решений для числа 4200 с обрезкой по делителям 22! получилось намного больше, чем с обрезкой по делителям числа 4200 (более чем в 3 раза).

Напомню, что решения в этом примере были найдены и с применением эвристики "только чётные числа" (когда искались решения для числа 4200).
Сейчас попробую применить сразу обе эвристики.

[whitefox]

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

Сама рассуждаю...
Возможно, вы хотите по новой эвристике получить последовательности для числа
39970374732288000, в которых есть делители 36!, не являющиеся делителями искомого числа. Так?

Нет не так.

Во-первых, никакую новую эвристику я не исследую.
Эвристика всё та же -- строить решение для N! только из делителей N!

Во-вторых, исследовался вопрос -- достаточно ли при построении решения для N! по частям, по указанной выше эвристике, использовать в частном решение только делители соответствующего множителя? Например, при представлении $N! =A\cdot B\cdot C$ достаточно ли при построении $A$ использовать только делители $A$?

В-третьих, так как иногда по второму пункту ответ отрицательный, то исследовался вопрос -- насколько увеличится время работы, если при построении $A$ использовать делители $N!$ вместо делителей $A$?

[Nataly-Mak]

Эксперимент №2 (22!)

1 этап
поиск числа 4200 в 9 шагов с применением сразу двух эвристик:
1. non-factor по 22!
2. только чётные числа

Программа работала 1 мин. 12 сек. Найдено 3318 решений. Вот как мало теперь, это решения, состоящие только из чётных чисел и только из делителей 22!

2 этап
Достраивание всех найденных последовательностей до числа 7983360 за 2 шага.
Здесь сняла все ограничения.
Программа работала 1 мин. 46 сек. Найдено два решения:

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

-- Пт май 03, 2013 10:25:13 --

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

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

Сама рассуждаю...
Возможно, вы хотите по новой эвристике получить последовательности для числа
39970374732288000, в которых есть делители 36!, не являющиеся делителями искомого числа. Так?

Нет не так.

Ну, а проведённые сейчас эксперименты для 22! полностью подтверждают мои мысли.
Увы, мы перестали понимать друг друга

-- Пт май 03, 2013 10:31:09 --

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

Во-вторых, исследовался вопрос -- достаточно ли при построении решения для N! по частям, по указанной выше эвристике, использовать в частном решение только делители соответствующего множителя? Например, при представлении $N! =A\cdot B\cdot C$ достаточно ли при построении $A$ использовать только делители $A$?

Хм, а я разве не то же самое говорила?
См. первый эксперимент для 22!

Вы дали ответ на этот вопрос ещё позавчера:

Цитата:

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

Я подтвердила это в только что проведённом эксперименте.

P.S. А под новой эвристикой я и имела в виду построение частных решений с использованием обрезки по делителям N! Ведь этой эвристики не было в первончальной версии программы Эда.

[whitefox]

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

Ну, а проведённые сейчас эксперименты для 22! полностью подтверждают мои мысли.
Увы, мы перестали понимать друг друга

Простите, не понял -- какие Ваши мысли (отличающиеся от моих) подтвердили эти эксперименты?

[Nataly-Mak]

Пожалуйста, прочтите внимательно мой пост с экспериментом для 22!, а также предыдущий пост.
По-моему, я говорила абсолютно то же самое, что и вы.
И мой эксперимент с решением для числа 4200 подтверждает ваше высказывание (см. цитату).
Если опять не согласны, можете не возражать.
Уже сказала: мы не понимаем друг друга, значит, дискуссия просто бесполезна.

-- Пт май 03, 2013 10:52:16 --

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

Простите, не понял -- какие Ваши мысли (отличающиеся от моих) подтвердили эти эксперименты?

В том и дело, что мои мысли не отличаются от ваших
но вы с этим не согласны, ибо написали: "Нет, не так".

[whitefox]

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

В том и дело, что мои мысли не отличаются от ваших
но вы с этим не согласны, ибо написали: "Нет, не так".

Пардон.
Я действительно не внимательно прочитал следующую Вашу фразу:

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

Возможно, вы хотите по новой эвристике получить последовательности для числа
39970374732288000, в которых есть делители 36!, не являющиеся делителями искомого числа. Так?

И понял её смысл так:
Возможно, вы хотите по новой эвристике получить последовательности для числа
39970374732288000, в которых есть только делители 36!, не являющиеся делителями искомого числа. Так?

[Nataly-Mak]

Эксперимент №3 (22!)

1 этап
поиск решений для числа 7983360 в 11 шагов с использованием двух эвристик:
1. non-factor по 22!
2. только чётные числа

Программа работала 14 мин. 13 сек. Найдено 55064 решения.
Достраивать так много начальных последовательностей до 22! не рискую.
Поступаю просто. Помещаю массив решений в Ворд и проверяю, где есть число 4200.
Это число небходимо, чтобы последовательности достроились до 22!
И вот что обнаруживаю: число 4200 есть только в двух последовательностях:

1,2,4,6,24,144,864,840,5040,4200,9240,7983360
1,2,4,6,24,36,864,840,5040,4200,9240,7983360

Бриллианты!

[Nataly-Mak]

Эксперимент №4 (22!)

1 этап
поиск решений для числа 7983360 в 11 шагов с использованием только одной эвристики - non-factor 22!
Программа работала 1 час 26 мин. 44 сек. Найдено 124518 решений.
Загоняю массив решений в Ворд. Мой допотопный Ворд примерно полчаса разделяет массив на страницы - 2395 страниц! Круто.
Выполняю поиск числа 4200, те же самые две последовательности, которые были найдены в предыдущем эксперименте.
Выполняю поиск числа 4199, ни одной последовательности!

Итак:
$22! = 4200 \cdot 4199 \cdot 7983360^2$

Решения, содержащие число 4200, имеются, а вот решений, содержащих число 4199, нет.
Но не потеряли ли мы такие решения, используя эвристику
Очень интересный вопрос!

mertz
вы можете найти все решения для числа 7983360 в 11 шагов?
Потом надо все эти последовательности проверить --- есть ли в них число 4199.
А также проверить, сколько последовательностей содержат число 4200.

[Nataly-Mak]

Продолжаю эксперименты
Теперь у меня 27!

$27! = 19550 \cdot (19550+1) \cdot 5337446400^2$

Я не знаю, даёт ли это разложение оптимальное решение, но очень хочу узнать, ибо мучила это разложение и не смогла ничего найти.
Трудность с поиском решений для 19550 в 10 шагов.
Решения в 8 и 9 шагов были проверены, они не дали решений.

Сейчас выполнила поиск решений для числа 19550 в 10 шагов полностью (без ограничений, то есть без использования эвристик). Найдено 24183 решения.
Такое количество решений мне не проверить на достраивание
Достраивать надо до числа 5337446400 за 3 шага.
То есть решения надо искать в виде:

a1,a2,a3,...,a10,19550,X,X,5337446400

Существуют ли такие решения?
Базовых последовательностей 24183 штуки.

Я искала и решения для числа 19551 в 10 шагов, их тоже очень много, и этот вариант проверить не смогла.

[mertz]

I found 36234 solutions for 19551 in 10 steps using base 6 sequences.

If you are crashing, turn off "Show Detail".

[Nataly-Mak]

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

I found 36234 solutions for 19551 in 10 steps using base 6 sequences.

А достраивание можете проверить?

a1,a2,a3,...,a10,19550,X,X,5337446400
a1,a2,a3,...,a10,19551,X,X,5337446400

Цитата:

If you are crashing, turn off "Show Detail".

Когда у меня сбой, программа уже не реагирует на нажатие кнопок. Неустранимая авария