Factorials

[Herbert Kociemba]

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

No, I haven't finished. Moreover I could easily win the previous contest also in one day, but recognized that the range of N values is too small and lots of contestant will reach the perfect score. I'm a gentleman, and I have given you a chance to win the contest.

No, you are no gentleman. A gentleman does not behave like a megalomaniac.

[mertz]

-------------------------------
found 2 solutions for 51090942171709440000 in 14 steps
1,2,4,16,20,80,1600,1620,25920,25840,27440,44452800,44478720,1149330124800,51090942171709440000
1,2,4,16,20,80,1600,1620,25920,25840,27440,44452800,44478720,1977203644416000,51090942171709440000
-------------------------------
found 2 solutions for 1124000727777607680000 in 14 steps
1,2,4,6,24,144,864,840,5040,4200,9240,7983360,33530112000,33522128640,1124000727777607680000
1,2,4,6,24,36,864,840,5040,4200,9240,7983360,33530112000,33522128640,1124000727777607680000
-------------------------------

[dimkadimon]

526760993631400648723665 = 923^8-16 = 3^3*5*17*53*73*89*137*139*181*227*881*967
8871870642308873326043031 = 83^13-332 = 3*31*43*83*131*137*223*239*283*433*457*499
106890007738661124410157 = 83^12-4 = 3*31*43*131*137*223*239*283*433*457*499
9132681934384901718000 = 556^8-16 = 2^4*3*5^3*7*17*67*71*73*233*311*661*769
104572372169968517360 = 318^8-16 = 2^4*5*7*13*17*31*41*59*73*233*773*857
56393835945562339994280 = 1779^7-1779 = 2^3*3*5*7*19*67*89*127*151*277*313*593*601
7250918737971366638396712 = 1281^8-729 = 2^3*3^6*19*37*151*167*349*479*673*743*839
177238161792112501080 = 781^7-781 = 2^3*3^2*5*7*11*13*17*23*31*43*71*127*229*457
119232467787562583454 = 738^7-738 = 2*3^2*7*11*13*31*41*43*67*73*139*241*739
16381116696296135096040 = 1491^7-1491 = 2^3*3*5*7*13*37*71*97*149*211*373*619*811
31699739148714075320 = 1779^6-1 = 2^3*5*7*19*67*89*127*151*277*313*601
3055526712356604073224 = 1173^7-1173 = 2^3*3*7*13*17*23*31*37*61*293*409*587*727
169457240010780689926385 = 801^8-16 = 5*7*29^2*43^2*151*197*347*607*653*761
33275593513886483760 = 615^7-615 = 2^4*3*5*7*11*13*19*31*41*127*157*307*937
4584562529303064541464 = 1243^7-1243 = 2^3*3^4*7^2*11*19*23*67*113*157*193*311*421
226937467083370680 = 781^6-1 = 2^3*3^2*5*7*13*17*23*31*43*127*229*457
2826219734466559998840 = 1160^7-1160 = 2^3*3^4*5*7*13^3*19*29*43*61*73*613*877
1860326946952404840 = 1109^6-1 = 2^3*3^2*5*7^2*13*19*37*67*277*643*967
3844185754368006995985 = 499^8-16 = 3^2*5*17*53^2*73*89*97*151*193*257*379
1560496482665168880 = 188^8-16 = 2^4*3*5*13*41*43*53*137*269*337*431

[Nataly-Mak]

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

found 2 solutions for 1124000727777607680000 in 14 steps
1,2,4,6,24,144,864,840,5040,4200,9240,7983360,33530112000,33522128640,1124000727777607680000
1,2,4,6,24,36,864,840,5040,4200,9240,7983360,33530112000,33522128640,1124000727777607680000

Красивые решения!
Действительно:

$22! = 33522128640 \cdot 33530112000$

всего-то надо было найти это замечательное разложение
И далее множители этого разложения связаны между собой так:

$33530112000 = 33522128640 + 7983360$

где число 7983360 тоже делитель 22!
[решения искались с ограничением: все члены последовательности - делители 22!]

Решения не вписываются ни в одну из парадигм wanderers, ибо здесь такая парадигма:

$22! = A(A+C)$

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

Вроде все приведенные решения для больших n вписываются в две формулы: n!=a*c^2 и n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y.

Как видим, далеко не все.

У кого есть другие оригинальные решения, которые не вписываются во все приведённые здесь парадигмы?

[Nataly-Mak]

Упаковку полинома для решения 22! сочинила.
Использовала второе решение mertz (в котором есть число 36).
Поскольку несколько громоздко получилось, пришлось ввести дополнительные обозначения.
Итак, начинаем от последовательности:

1,2,4,6

$x=6$

$y=4x \cdot 6x - 4x$
$z=4x \cdot 6x \cdot (yx+(yx-y))$

$f(x)=z(yx-y) \cdot (z(yx-y)-z)$

Не ошиблась?
Для проверки:

$y=840$
$z=7983360$
$f(6)=22!$

Требуется найти полином f(x).
Запуталась в скобках, слишком громоздко

Кто развернёт упаковку?

Примечание: поскольку в последовательности первым получено число 33530112000, формулу лучше записать в виде:

$22! = A(A-C)$

Впрочем, сути это не меняет.

[Nataly-Mak]

Стало любопытно, сколько есть решений для числа 7983360 в 11 шагов.

Запускаю программу mertz с ограничением, что ищутся только решения с чётными числами.
Через 3 мин. 40 сек. программа отработала 4% и нашла 4957 решений
Прерываю программу, просматриваю эти решения. Ведь нам надо, чтобы в последовательности обязательно присутствовало число 4200.
Увы, ни в одном из полученных решений этого числа нет.

Интересно, сколько же будет решений для числа 7983360 в 11 шагов, в которых будет присутствовать число 4200?
Неужели таких решений и будет всего два --- те, что найдены mertz
Круто! Из многих тысяч решений только два годные. Вот они - алмазы!

Опа!
А ведь парадигма-то вот она

$22! = 7983360^2 \cdot 4200 \cdot (4200-1)$

Смотрела, смотрела на число 7983360 --- до боли знакомое число
И разложение это whitefox нашёл!
И я его мучила! Но вот решения для числа $7983360$ в 11 шагов найти не смогла. Во-первых, это очень долго (если вообще без ограничений), а во-вторых, решений будет несколько тысяч и проверить их потом на достраивание трудно (у меня программа уже при 8000 решений виснет, хотя mertz писал, что программа должна проверять 10000 решений).

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

А я пыталась плясать от числа 4200. И почему у меня это не получилось? Не помню...
Сейчас попробую это снова проделать.

Вот они - разложения, найденные whitefox:

10! = 63 * (63 + 1) * 30^2
11! = 175 * (175 + 1) * 36^2
14! = 351 * (351 + 1) * 840^2
17! = 935 * (935 + 1) * 20160^2
18! = 220 * (220 + 1) * 362880^2
22! = 4199 * (4199 + 1) * 7983360^2
26! = 322 * (322 + 1) * 62270208000^2
27! = 19550 * (19550 + 1) * 5337446400^2

Да, обидно, были рядом с решением

Смотрю файлы, вот есть решение для числа 4200 в 7 шагов, оно единственное:

1,2,4,6,10,60,70,4200

Далее есть решения для этого числа в 8 шагов - много.
Достроить эти решения до числа 7983360 не удалось.
А вот решений для числа 4200 в 9 шагов у меня нет.
Видимо, я это пыталась искать, но решений таких оказалось очень много, не стала доводить это до конца.
А решения в 9 шагов как раз до числа 7983360 достраиваются!

Ну, очень довольна, что теперь вижу, почему мои мучения не увенчались успехом
А я очень много мучила 22!

-- Ср май 01, 2013 10:10:36 --

Я и от числа 4199 пыталась плясать.
Вот решения для этого числа в 8 шагов:

1,2,4,16,15,19,225,221,4199
1,2,4,16,15,19,240,221,4199
1,2,4,16,17,13,19,221,4199
1,2,4,16,17,13,19,247,4199
1,2,4,16,17,13,19,323,4199
1,2,4,6,10,60,70,4200,4199

В 7 шагов решений, неверное, не существует; нет такого файла у меня.
Далее решения для числа 4199 в 9 шагов, много.
Всё это не удалось достроить до числа 7983360 за нужное количество шагов.

[Nataly-Mak]

Товарищи, потерпите ещё немножко

Да, запускаю поиск решений для числа 4200 в 9 шагов.
Их более 10000 (прервала программу при 76%, найдено 10315 решений).
Поэтому я тогда этот вариант и не проверила.

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

Кстати, интересно, это начало массива решений:

1,2,4,16,12,10,14,30,140,4200
1,2,4,16,12,10,14,30,300,4200
1,2,4,16,12,10,14,30,420,4200
1,2,4,16,12,10,15,28,150,4200
1,2,4,16,12,10,15,28,280,4200
1,2,4,16,12,10,15,28,420,4200
1,2,4,16,12,10,15,60,70,4200
....

А что тут делает число 15, если ищутся только последовательности, состоящие из чётных чисел?
Это вопрос к mertz.

Теперь беру эти 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

Итак: не сообразила искать решения только с чётными числами. Плохо работает соображалка

mertz
сколько будет решений для числа 4200 в 9 шагов при условии, что ищем последовательности, состоящие только из чётных чисел (не считая число 1)?

-- Ср май 01, 2013 11:30:50 --

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

Далее решения для числа 4199 в 9 шагов, много.
Всё это не удалось достроить до числа 7983360 за нужное количество шагов.

Повторила сейчас поиск по числу 4199.
Решений в 9 шагов 1059.
До числа 7983360 эти решения за 2 шага не достраиваются.
А вот за 3 шага - пожалуйста

found 12 solutions for 7983360 in 12 steps
1,2,3,9,7,16,17,256,247,4199,1792,4455,7983360
1,2,3,9,7,16,17,256,247,4199,4455,1140480,7983360
1,2,3,9,7,16,17,256,247,4199,4455,31185,7983360
1,2,3,9,7,16,256,247,3952,4199,1792,4455,7983360
1,2,3,9,7,16,256,247,3952,4199,4455,1140480,7983360
1,2,3,9,7,16,256,247,3952,4199,4455,31185,7983360
1,2,3,9,7,16,256,263,4208,4199,1792,4455,7983360
1,2,3,9,7,16,256,263,4208,4199,4455,1140480,7983360
1,2,3,9,7,16,256,263,4208,4199,4455,31185,7983360
1,2,4,6,7,16,256,262,4192,4199,1792,4455,7983360
1,2,4,6,7,16,256,262,4192,4199,4455,1140480,7983360
1,2,4,6,7,16,256,262,4192,4199,4455,31185,7983360 

То есть решение для 22! в 15 шагов получается с ходу.

[Nataly-Mak]

Обалденная цитата из письма whitefox

Цитата:

Например, для 22! существует единственное разложение такого вида 22! = 7983360^2 * 4199 * 4200
Нужно всего лишь найти решение для 4200 (или 4199) длиной 7-9 шагов и продолжить его до решения 7983360 длиной в 11 шагов.

Всё это я и проделала, но не до конца - с решениями для числа 4200 в 9 шагов не получилось: очень их много, не смогла найти все и проверить
[а применить замечательную эвристику Pavlovsky о чётных числах не догадалась].

Получаю двойку, мне очень стыдно

[dimkadimon]

Nataly-Mak

Вот вам ещё:

26! = 20051006976000 * (20051006976000 + 62270208000)
27! = 104347077120000 * (104347077120000 + 5337446400)
28! = 552129177600000 * (552129177600000 + 75554519040)
29! = 2973473193600000 * (2973473193600000 + 73705282560)
30! = 16268126711316480 * (16268126711316480 + 36938064683520)

[Nataly-Mak]

dimkadimon
интересные разложения.
А упаковку мою для 22! можете развернуть?
ну, то есть превратить её в полином
$f(x) = a_nx^n + a_{n-1}x^{n-1}+... $

Запускаю снова поиск решений для числа 7983360 в 11 шагов с ограничением: только чётные числа.
Программа работает 8 мин. 20 сек., отработала 7%, найдено 10659 решений. Прерываю программу. Проверяю все эти решения в Ворде, ни в одном нет числа 4200.
Вот так дела!

[whitefox]

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

26! = 20051006976000 * (20051006976000 + 62270208000)
27! = 104347077120000 * (104347077120000 + 5337446400)
28! = 552129177600000 * (552129177600000 + 75554519040)
29! = 2973473193600000 * (2973473193600000 + 73705282560)
30! = 16268126711316480 * (16268126711316480 + 36938064683520)

И из этих разложений можно получить оптимальные решения?

Например, для 28! было найдено, по существу, единственное оптимальное решение из разложения $28!=1651104000^2\cdot326876\cdot342144$

[Nataly-Mak]

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

И из этих разложений можно получить оптимальные решения?

whitefox
не зря мы поиграли в одной команде
Вы читаете мои мысли на расстоянии: я хотела задать такой же вопрос.

-- Ср май 01, 2013 14:57:58 --

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

27! = 104347077120000 * (104347077120000 + 5337446400)

Это --- не ещё, это уже есть у whitefox

[см. его разложения, я их показала чуть выше]

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

Решение на основе этого разложения я тоже пыталась получить. Тщетно!

[mertz]

Found 2 arrays that were only 3000. Compiler should have caught it. Updated program. New limit is 50000. Use same links as before to download.

[Nataly-Mak]

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

Found 2 arrays that were only 3000.

Как я понимаю, решений для числа 4200 в 9 шагов (только с чётными числами) нашлось всего 3000. Правильно понимаю?

Спасибо за новую версию программы.

mertz
ничего не изменилось в новой версии программы.
О каких двух массивах вы писали, я совсем не понимаю
Ищу в новой версии программы решения для числа 4200 в 9 шагов только с чётными числами.
Решений, как и прежде, программа выдала 4332, и в этих решениях есть нечётные числа:

1,2,4,16,12,10,14,30,140,4200
1,2,4,16,12,10,14,30,300,4200
1,2,4,16,12,10,14,30,420,4200
1,2,4,16,12,10,15,28,150,4200
1,2,4,16,12,10,15,28,280,4200
1,2,4,16,12,10,15,28,420,4200
1,2,4,16,12,10,15,60,70,4200
....

-- Ср май 01, 2013 15:38:16 --

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

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

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

Нашла два числа с новым рекордом количества решений в 10 шагов, это числа 19550 и 19551.

А почему 10 шагов? Ведь для этих чисел есть решения в 8 шагов:
1, 2, 3, 5, 25, 28, 784, 782, 19550
1, 2, 4, 8, 7, 49, 57, 343, 19551

Я знаю
Мне для формулы нужны решения и в 8, и в 9, и в 10 шагов.
Нашла для 19550: в 8 шагов - 1 решение, в 9 шагов - 245 решений; для числа 19551: 4 решения в 8 шагов и 538 решений в 9 шагов.
Всё это проверила; нужны ещё решения в 10 шагов. А вот с этими решениями проблема - очень уж их много.

Вот здесь писала, как работала с этой самой парадигмой для 27!
Ничего не получилось у меня.
Решения для числа 19550 в 10 шагов зашкаливают, их очень много.

А можно ли вообще из этой дьявольской парадигмы
$27! = 19550 \cdot (19550 + 1) \cdot 5337446400^2$
выжать оптимальное решение

[whitefox]

mertz
Какая функция у кнопки Run в первом окне?
Чем Normal Search отличается от Chain Search?

Вот чего мне сейчас реально не хватило при поиске решения для 326876, так это обрезки Non-Factor по 28!, а не по целевому числу.