Factorials

[Pavlovsky]

Почему бы нет. Если Xaositect еще подкинет какую нибудь теорему.
Он ведь теперь главный консультант по математике в этой теме.

[Nataly-Mak]

Неутомимый mertz вчера прислал ещё один инструмент. Эта программа ищет решения для любого числа (не только факториалы) в пределах 10 шагов.

Здесь показан поиск решения для числа 217350. На картинке видно - найдено 862 решения, и это ещё не все, я прервала программу.



Отличный инстумент! Поиск выполняется очень быстро. Программа может искать решения и в 11 шагов, но это будет уже очень долго.

И факториалы, конечно, ищет, но тоже в пределах 10 шагов, а это значит - до 12!

[mertz]

When you get that many results, try a lower step count. Found 13 solutions with 9 steps.

Will there be more than one person with 25 points?

Are there any improvements left?

Will Al change the contest?

[Nataly-Mak]

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

When you get that many results, try a lower step count. Found 13 solutions with 9 steps.

А, поняла. Действительно, найдено 13 решений в 9 шагов:

found 13 solutions for 217350 in 9 steps
217350 = [9] 1,2,3,5,15,14,210,1050,1035,217350
217350 = [9] 1,2,3,5,15,14,210,207,1035,217350
217350 = [9] 1,2,3,5,15,14,210,207,1050,217350
217350 = [9] 1,2,3,5,15,14,210,207,43470,217350
217350 = [9] 1,2,3,5,15,18,270,810,805,217350
217350 = [9] 1,2,3,5,15,225,210,1050,1035,217350
217350 = [9] 1,2,3,5,15,225,210,207,1035,217350
217350 = [9] 1,2,3,5,15,225,210,207,1050,217350
217350 = [9] 1,2,3,5,15,225,210,207,43470,217350
217350 = [9] 1,2,3,5,15,30,33,450,483,217350
217350 = [9] 1,2,3,5,15,30,450,453,483,217350
217350 = [9] 1,2,3,5,15,30,450,480,483,217350
217350 = [9] 1,2,4,16,15,225,241,964,966,217350

25 баллов, скорее всего, ещё будет, но не много, 2-3 человека.
Tomas хорошо лидирует, у него есть рекорды. Догнать его сложно.

[ben_burrows]

I am surprised to hear so little talk of 13!. Is the 11-step solution not known?

[mertz]

13! (11) has 377 solutions.
14! (11) has 56 solutions.

My pruning is not perfect so there may be more.

13! is part of the contest so solutions will not be shown.

[dimkadimon]

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

Will there be more than one person with 25 points?

Are there any improvements left?

Will Al change the contest?

There could be more 25, but I doubt there will be many. I am sure there are still improvements left. It is very unlikely that Al will change the contest.

[Nataly-Mak]

Ура, наши идут вперёд!

Цитата:

11 23.69 Alex Chernov Penza, Russia 22 Feb 2013 19:25
12 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52

Так держать!

-- Сб фев 23, 2013 11:39:30 --

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

На 19! не зацикливаюсь.

А я зациклилась на 19! Ни черта не получается, 16 шагов - хоть застрелись.

Вчера вот такое разложение попробовала:

19! = 143*144^4*1978375

Программа mertz элементарно находит 4 решения для числа 1978375 в 10 шагов.
Казалось бы так мало осталось. Всего 3 различных сомножителя. И... всё равно только 16 шагов.

Ну тупа-а-а-я

Надо применить какой-то другой подход. Я уже два алгоритма применила для поиска этого решения, нужен новый!

(Оффтоп)

Форум ПЕН опять в коме
Вчера там дискуссия была интересная в теме "История развития кибернетики".

[Nataly-Mak]

Это поиск решений для N=12 в программе mertz:



Красиво! Поиск занял несколько минут.

Ed
ваши программы для конкурсов всегда были замечательны.
Я написала книгу о конкурсе Monochromatic Squares (правда, чуть-чуть недописала, но ещё надеюсь дописать)

"Monochromatic Squares или Математическая раскраска"
http://yadi.sk/d/7SS_VtvP2F_XE



Ваша программа позволила сделать отличные иллюстрации. Это очень красивые иллюстрации!

[Pavlovsky]

Анализ последних моих решений показывает, что достаточно короткое решение дают следующие разложения факториала на множители:
1) N!=A*B^2.
2) Далее можно разложить B=C*D^2. То есть N!=A*C^2*D^4.

[Nataly-Mak]

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

Анализ последних моих решений показывает, что достаточно короткое решение дают следующие разложения факториала на множители:
1) N!=A*B^2.
2) Далее можно разложить B=C*D^2. То есть N!=A*C^2*D^4.

Попробовала.

1. 19! = 35^2*144^4*230945
увы, только 16 шагов
число 230945 за 9 шагов не представляется, только за 10.

2. 20! = 224^2*180^4*46189
легко даёт решение в 15 шагов

3. 21!=224^2*180^4*969969
пока не нашла решение; ищется представление числа 969969; уже найдено 117 решений в 10 шагов.

[Pavlovsky]

Разложения N!=A*B^2 и N!=A*C^2*D^4 должны быть хорошими. Обосновать это утверждение можно двумя соображениями:
1) В N! можно выделить достаточно большой сомножитель вдиа A^2 и даже A^4.
2) Разложение A*B^2 требует двух умножений, N!=A*C^2*D^4 требует четырех умножений. Что очень мало.

-- Вс фев 24, 2013 16:05:59 --

Разложения N!=A*B^2 и N!=A*C^2*D^4 не подходят для 19! По различным намекам участников нашедших решение 13 для N=19. Можно сделать выводы:
1) В конце последовательности не более двух умножений.
2) Если в конце последовательности 2 умножения, то в разложении 19!=A*B*C, A,B,C различны.

[Nataly-Mak]

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

3. 21!=224^2*180^4*969969
пока не нашла решение; ищется представление числа 969969; уже найдено 117 решений в 10 шагов.

Программа mertz нашла 164 представления числа 969969 в 10 шагов.
На основе одного из представлений легко получается решение для 21! в 16 шагов.
Однако, всё это у меня уже есть, пока никаких улучшений.

19! - 16
20! - 15
21! - 16

[dmd]

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

2) Если в конце последовательности 2 умножения, то в разложении 19!=A*B*C, A,B,C различны.

Пусть $x,y,z$ - числа из последовательности выстраивающей $A$, и $x',y',z'$ - другие три числа из той же последовательности, возможно совпадающие с числами из первой тройки. Тогда очевидно, что $B=xy \pm z$ и $C=x'y' \pm z'$. На достройку последовательности получается $6$ шагов, соответственно последовательность $A$ должна быть как минимум длиной $7$ для рекорда $13$. Но может быть и $8$ если $x||y=1$, и $9$ если $(x||y=1)\&\&(x'||y'=1)$. При этом последовательность $A$ тоже должна заканчиваться не умножением. Например для $A=2816$ такова $1,2,4,16,12,256,3072,2816$. До кучи еще надо рассмотреть и $B=x \pm y \pm z$ и $C=x' \pm y' \pm z'$.

(Оффтоп)

Примерно по этой схеме сейчас и пытаюсь искать рекорды. Начинал тоже с исследования квадратных делителей факториала, т.к. их достаточно мало получалось в общем числе делителей. Но быстро понял, что делители-квадраты исчерпывают себя уже при $N>17$ (впрочем - не уверен в этом, просто для моих эвристик это оказалось так). Я пока не научился собирать все последовательности для заданного небольшого числа хотя бы на 5-7 шагов, и не факт что научусь. Строю последовательность банально методом случайного тыка. У меня нет рекорда даже для $N=16$. Но и случайный тык позволил сгенерить нерекорды для всех $N$ и набрать около 20 очков.

[Nataly-Mak]

dmd в сообщении #687679 писал(а):

Пусть $x,y,z$ - числа из последовательности выстраивающей $A$, и $x',y',z'$ - другие три числа из той же последовательности, возможно совпадающие с числами из первой тройки. Тогда очевидно, что $B=xy \pm z$ и $C=x'y' \pm z'$.

Это верно для любого разложения 19!=A*B*C (A,B,C - различны)?