Factorials

[Pavlovsky]

http://www.wolframalpha.com/input/?i=x%5E2%2Bx%3D923780
Вводите x^2+x=923780

[Nataly-Mak]

А, спасибо большое.
Так я в этой программе факторизацию делаю (ссылку на эту программу malk давал).
Отличная программа, вот и уравнения такого вида решает. Здорово!
Ввела уравнение
$x^2+x=104006$

Получила два решения:
$x_1=-323$
$x_2=322$
А я только одно решение знала - 322.

[mertz]

Цитата:

This time, such was the assistant Mertz , and it is absolutely free! And I did not mean to ask for his help, and he suddenly for no reason, no reason sent me his program

You were the only person I knew used all my previous programs.

[Nataly-Mak]

mertz
мне приятно с вами сотрудничать.

[Nataly-Mak]

Ва-банк оказался неплохим алгоритмом.
Сейчас удалось на 1 шаг улучшить решение для 21!

21! = K*(10!)^2 = 3879876*(10!)^2

Нашла по программе mertz решения для числа 3879876 в 10 шагов, нашлось 21 решение. Удалось выбрать достаточно короткую подпоследовательность для формирования числа 3879876. Получила решение в 15 шагов, всего на 1 шаг больше оптимального.

[mertz]

I think I have a complete search now. No duplicate work.

 (6) 5
 (7) 18
 (8) 68
 (9) 18
(10) 104
(11) 12
(12) 56

Here are the additional solutions found for 8! and 10!

[3]
8!  40320  [8] 1,2,4,6,36,32,35,1120,40320
8!  40320  [8] 1,2,4,6,36,32,35,1152,40320
8!  40320  [8] 1,2,4,6,36,32,35,1260,40320
[13]
10!  3628800  [9] 1,2,4,16,64,60,63,1008,3600,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,1008,60480,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,240,15120,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,240,57600,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,3600,226800,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,3600,57600,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,3780,226800,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,3780,60480,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,960,3780,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,960,57600,3628800
10!  3628800  [9] 1,2,4,16,64,60,63,960,60480,3628800
10!  3628800  [9] 1,2,4,8,64,60,63,240,15120,3628800
10!  3628800  [9] 1,2,4,8,64,60,63,240,57600,3628800

[Nataly-Mak]

Забавно:

решения

8!  40320  [8] 1,2,4,6,36,32,35,1120,40320
8!  40320  [8] 1,2,4,6,36,32,35,1152,40320
8!  40320  [8] 1,2,4,6,36,32,35,1260,40320

очень похожи на решения

8!  40320  [8] 1,2,3,6,36,35,32,1120,40320
8!  40320  [8] 1,2,3,6,36,35,32,1152,40320
8!  40320  [8] 1,2,3,6,36,35,32,1260,40320

[Toucan]

Напоминаю участникам темы: формулы надо набирать в $\TeX$

[mertz]

new results for 11 steps (13! and 14!) 13 has 445 solutions, 14 has 65 solutions. 70 minutes and 357.5 billion nodes.

[ben_burrows]

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

new results for 11 steps (13! and 14!) 13 has 445 solutions, 14 has 65 solutions. </font><font>70 minutes and 357.5 billion nodes.

Do these counts impose any constraints on the output formula? E.g., must be monotonic, additions only for small numbers ... or do they include all possible solutions?

[mertz]

The goal is to do a complete search without any duplication. Solutions starting with 1,2,3,4 are the same as 1,2,4,3. Look at all the possible solutions with 5 numbers. The number of unique solutions is 59. It took me three versions to get it right. Monotonic doesn't work. There are many times a single decrease is needed. Multiple decreases are not too common but they do figure into the new results for 8! and 10! I posted above. Out of the 59 unique 5 base solutions, only about half produce a solution 6! to 14! Up to 14! I did a complete search. Past that I will have to start imposing constraints.

[dimkadimon]

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

Может облегчит задачу? A=37! То есть задача получается такой:

Очень быстро определить является ли число B делителем 37!

Можно найти множество всех делителей 37!. Их не так много всего 40 милионов. Потом можно за О(1) проверить если число B член этого множества.

[Pavlovsky]

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

1, 2, 4, 6: 64%
1, 2, 4, 16: 21%
1, 2, 3, 9: 8%
1, 2, 3, 5: 5%
1, 2, 4, 5: 2%

Статистика очень сильно зависит от особенностей переборного алгоритма. Если в процессе перебора найдено лучшее решение чем было, то на этом прекращается поиск решений найденной длины и перебор переключается на поиск более коротких решений. Какое решение попадет в список луших решений, зависит от порядка перебора. Например у меня перебор идет в обратном лексикографическом порядке. Поэтому мои лучшие решения как правило начинаются с 1,2,4,16 и даже 1,2,4,16,256.
Если у dimkadimon перебор организован в естественном возрастающем лексикографическом порядке, тогда представленная им статистика будет интерпретироваться совсем по другому. Начало 1,2,4,16 явно лучше других. Ведь для того чтобы такому началу попасть в список луших решений, не должно существовать решений с той же длиной с другими началами. Ведь 1,2,4,16 последнее в лексикографическом порядке.

Цитата:

1, 2, 4, 16: 21%

Говорит о том что в 20% случаев все рекордные решения начинаются с 1,2,4,16.

Цитата:

1, 2, 4, 6: 64%

А вот это ничего не значит. Ведь могут существовать рекордные решения начинающиеся и на 1,2,4,16.

[dimkadimon]

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

Если у dimkadimon перебор организован в естественном возрастающем лексикографическом порядке, тогда представленная им статистика будет интерпретироваться совсем по другому

У меня не полный перебор и поэтому я не использую никакой порядок. Если у нас решение 1, 2, 4, 6, ..., А то за один шаг можно получить А+1, А+2, А+4, А+6 (и минус тоже). За два шага можно получить А+3, А+5, А+7, А+8, А+10, А+12. Получается что за два шага или меньше можно получить все A+k, где k<=12, кроме k=9 или 11. Это полезное свойство.

Если решение 1, 2, 4, 16, ... А то за один шаг получаем А+1, А+2, А+4, А+16. За два шага получаем А+3, А+5, А+6, A+8, А+12, А+14, А+15, А+17, А+18, А+20. Для k<=12 гораздо больше пробелов (4 вместо 2). Зато некоторые числа с k>12 можно получить быстрее. Трудно сказать какое начало лучше или хуже - всё зависит от конкретного N!. Уверен только что начало 1, 2, 3, 4 плохое.

[Pavlovsky]

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

Уверен только что начало 1, 2, 3, 4 плохое.

Поэтому я и выбрал обратный лексикографический порядок. Чтобы глупости типа 1,2,3,4,5,6,7,... перебирать в последнюю очредь.