2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 53, 54, 55, 56, 57, 58, 59 ... 88  След.
 
 Re: Factorials
Сообщение21.04.2013, 05:33 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
282 7.13 Robert Gerbicz Halasztelek, Hungary 20 Jan 2013 14:05

За один день участия 7.13 баллов. Это гениально :D

Но... есть намного лучше, например:

Цитата:
120 18.39 Jarek Wroblewski Wroclaw, Poland 20 Jan 2013 16:47

И это тоже за один день!

-- Вс апр 21, 2013 06:40:49 --

dimkadimon в сообщении #713440 писал(а):
Ну, кто будет первым Россиянином который нашел 1000!

Ха, найти любую последовательность не проблема :-)
Например, начинаем так:

Код:
1,2,3,6,4,24,5,120,720,7,5040,8,40320,9,362880...

Годится? :wink:
Или начинаем от найденной минимальной последовательности для 37! Чем не вариант?

Но ведь надо, как я понимаю, найти последовательность минимальной длины.

Кстати, решение нашей команды для 37! (22 шага):

Код:
1,2,3,9,81,72,70,140,221,5040,362880,80196480,79833600,30940,30868,25900,420,
12964560,12964479,335780006100,6402373705728000,
40990389067797283140009984000000, 13763753091226345046315979581580902400000000

Тоже найдено по "супер-пупер" алгоритму.

$37! = 25900 \cdot 12964479 \cdot (18!)^2$

Это результат программы mertz для второго этапа - поиска числа 12964479:

Код:
found 4 solutions for 12964479 in 18 steps
1,2,3,9,81,72,70,140,221,5040,362880,80196480,79833600,30940,30868,25900,420,12964560,12964479
1,2,3,9,81,72,70,140,221,5040,362880,80196480,79833600,30940,30868,25900,4321520,12964560,12964479
1,2,3,9,81,72,70,140,221,5040,362880,80196480,79833600,30940,30868,25900,92604,12964560,12964479
1,2,3,9,81,72,70,140,221,5040,362880,80196480,79833600,420,30940,25900,30868,12964560,12964479

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

-- Вс апр 21, 2013 07:22:28 --

Теперь расскажу, как мы с whitefox нашли оптимальное решение для 25!
Это было очень красиво :roll:

Начинала я искать решение для 22! на основе этого разложения, найденного whitefox:

$22! = 247 \cdot (247 \cdot 185+1) \cdot 9979200^2$

Но решение для 22! не было найдено (по тому методу, который заложен в этом разложении).
Сообщаю об этом whitefox. Он отвечает, что тогда можно попробовать домножение на число $247 \cdot (247 \cdot 185+1)=11286912$.
Замечательная идея! Мне сразу это в голову не пришло.
Пробую... Однако для 22! всё равно не получается.
Тогда я домножаю число 11286912 на 23, $23 \cdot 24$,
$23 \cdot 24 \cdot 25$ и ищу решения для 23!, 24!, 25!.
Для 23! и 24! не получилось, а для 25! есть.
Разложение, по которому решение было найдено:

$25! = 155759385600 \cdot 9979200^2$

Решение:
Код:
1,2,4,6,24,28,576,600,594,16800,9979200,16796,552,282172800,155759385600,99584432640000,15511210043330985984000000

Есть два варианта, программа выдала три решения.
А поскольку всё это искалось мной по программе mertz, получается, что данное решение - результат работы всех членов команды.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 08:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Раскладываем в Вольфраме:

$1000! = A \cdot (500!)^2$

Код:
A=270288240945436569515614693625975275496152008446548287007392875106625428705
52219389861248392450237016536260608502154610480220975005067991754989421969951
84754236654842637517333561624640797378873443645741611194976045710449857562878
80514600994219426752366915856603136862602484428109296905863799821216320

В числе А всего 300 десятичных знаков :D

А где у нас главный герой - Pavlovsky? Может, уехал отдыхать на выходные?
И вообще: почему народ не рассказывает о своих красивых алгоритмах?

dmd так ждал "разбор полётов" :-)

-- Вс апр 21, 2013 09:32:20 --

Если все стесняются, я продолжу :?

Покажу найденное мной оптимальное решение для 30!
Тут сомневались, что такое решение существует в виде
$30! = A \cdot (15!)^2$

Вот это решение:

Код:
1,2,4,6,36,34,216,180,6120,6336,1140480,1146600,25344,25346,155117520,1307674368000,
1710012252724199424000000,265252859812191058636308480000000

$30! = 155117520 \cdot (15!)^2$

Поиск начинается от начальной последовательности, представляющей 15!, без последнего члена. Число 155117520 от этой последовательности составляется всего за 3 шага!
Были, конечно, проверены все последовательности для 15! (их 347 штук); программа mertz выдала для числа 155117520 только два решения.
Это второе решение:

Код:
1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,25344,25346,155117520,
1307674368000,1710012252724199424000000,265252859812191058636308480000000

Кстати, тут был такой интересный момент. Сначала задала поиск числа 155117520 за 4 шага, в надежде найти решение для 30! в 18 шагов.
Запустила программу и прилегла (программе примерно на 2 часа работы, ибо добавляются 4 шага). Прилегла, вздремнула, просыпаюсь, смотрю: программа нашла уже 472 решения! И всё ещё работает. Прерываю программу (68% отработала программа); рассуждаю: если так много решений за 4 шага, наверное, есть и решения за 3 шага. Запускаю этот вариант и... программа быстренько выдаёт 2 решения :roll:

Вот посмотрите, это первые решения за 4 шага для числа 155117520:

(Оффтоп)

Код:
found 472 solutions for 155117520 in 15 steps
155117520 = [15] 1,2,4,6,36,216,180,176,6336,1140480,1140264,1146600,6120,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,1140480,1146816,1146600,6120,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,10,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,1056,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,1080,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,1115136,1115134,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,1115136,1140482,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,12672,12673,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,12672,155105280,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,24480,155105280,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,25344,155105280,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,25344,25346,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,38776320,155105280,155117520
155117520 = [15] 1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,12240,77552640,155105280,155117520
...

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 16:47 
Заблокирован


20/10/12

85
Nataly: "For one day of participation 7.13 points. This is brilliant"

Not forget your score, what is perfect 0. Will you skip also this contest? As I remember you don't participate on those contests where I'm.

Al Zimmermann:
"Since there’s only one problem in this contest, it’s going to be pretty easy to figure out what the best raw score is. So I’ve made it even easier by inserting a dummy contestant into the standings list. This dummy’s contest score, times one thousand, equals the best raw score submitted."

What is curious, yesterday I thought that this user is a cheater, and listed his place as New York, New York. But today he removed to Adelaide, Australia.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 16:59 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Gerbicz, if you dont have anything to say then dont say it. Its a dummy contestant. Its not a real contestant. Al introduced it to show what the optimal score is. Do you even understand English?!?

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 18:05 
Заблокирован


20/10/12

85
dimkadimon, I understand it, but don't know why was it important to change the place of this dummy user.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 18:13 
Заблокирован


21/04/13

78
Вроде все приведенные решения для больших n вписываются в две формулы: n!=a*c^2 и n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y. Отсюда и метод решения: генерируем для каждого n две таблицы - одну из двух столбцов, а вторую - из трех. Далее используем технику хеширования. Теперь по поводу техники работы с записями: я генерировал базу размером примерно 600 мегабайт, содержащую записи, каждая из которых включает 10 членов. При этом использовалась техника быстрой генерации неповторяющихся записей и такая очевидная эмпирика, как ограничение общего числа аддитивных операций в записи, и ограничение в их непрерывности следования. Ну и разное по мелочи. Для примера рассмотрим самый последний факториал 37! в финальной таблице конкурса. Приведем соответствующую запись к "божескому" виду.
4, 6, 36, 144, 216, 210, 220, 31680, 31464, 31824, 46656, 46620, 6652800, 310153536000, 211718707200, 6661517403340800, 6661729122048000, 44377224482864980286137958400000, 3763753091226345046315979581580902400000000

x=31464
a=211718707200
y=6652800*46620=310153536000
x*a=6661517403340800
x*a+a=6661517403340800+211718707200=6661729122048000
(x*a)*(x*a+a)=44377224482864980286137958400000
n!=(x*a)*(x*a+a)*y=
44377224482864980286137958400000*310153536000=13763753091226345046315979581580902400000000
У меня решение задачи для 31! на 14 ядрах заняло примерно полчаса.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 18:25 
Заблокирован


20/10/12

85
Discovered a serious bug on azspcs.net: if you click on "Time-Weighted Standings (Beta)" then it doesn't show the dummy user with raw score=1000. OK, this is only beta, but Al should work more on this.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 19:41 
Аватара пользователя


21/02/10
1594
Екатеринбург
Чтобы никого не обидеть обойдусь без персоналий.

Поздравляю всех участников конкурса с его окончанием. Победителей конкурса. Тех кто стал лучшим в своей стране. Тех кто просто выступил в свою силу и убедился что не боги горшки обжигают. Естественно отдельно выделю Россиян. Активность Россиян была очень высокой. Конечно жаль, что никто не включился в борьбу за призовые места, но ведь это не последний конкурс.

Так же хочу поблагодарить тех, кто принял участие в обсуждении задачи в этой теме. Тема получилась очень интересной.

-- Вс апр 21, 2013 22:21:44 --

Алгоритмы, которые я использовал достаточно подробно описаны в этой теме. Поэтому опишу только некоторые особенности реализации.

Основной алгоритм условное название "Оливос":
Пусть есть начальная последовательность T. Как мы ее построили пока не важно. Используя числа из последовательности T, набираем произведение равное N!

Эта процедура оказалась супер эффективной! Работает очень быстро и позволяет строить решения близкие к оптимальным для очень больших N.

1) Если N! разложить на простые множители, то в нем будет много больших простых чисел входящих в разложение в первой степени. Разумно организовать перебор так. Сначала выбираем числа содержащие максимальное простое число, входящее в разложение N! Потом следующее по старшинству простое число и так далее вплоть до 2.

2) Используя теорему Оливоса, можно вычислить очень точные нижние оценки длины последовательности.

Цитата:
$L(\prod_{i=1}^{n}{{x_i}^{k_i}}) \ge n-1+max(L({x_i}^{k_i}))$, где L() минимальная длина последовательности.


Цитата:
Пусть мы хотим вычислить выражение: $x_1^{n_1}\dots x_k^{n_k}$. Пусть все $n_1,\dots,n_k$ различны. Привести общий случай к этому частному, элементарно. Тогда $L(x_1^{n_1}\dots x_k^{n_k}) \ge 2k-2$. Равенство достигается тогда, когда числа $n_1,\dots,n_k$ образуют аддитивную последовательность без использования дополнительных чисел.


3) Ну и наконец возможен следующий финт. Добавим в последовательность Т все числа которые можно получить операцией сложения или вычитания из чисел входящих изначально в последовательность T. Полученное множество чисел будем использовать в качестве разрешенных множителей, при разложении N! на множители. Естественно при подсчете длины последовательности должны помнить, что для построения добавленных чисел требуется дополнительная операция.

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 20:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
Технология поиска решений выглядит так:

1) Полным перебором были сформированы все последовательности длиной 8 операций (9 чисел). Таких последовательностей получилось около 6 миллионов. Далее для каждой последовательности и для каждого N была применена выше описанная процедура "Оливос". Это позволило набрать в конкурсе около 23,5 баллов. Процесс проверки всех последовательностей занял от нескольких часов для маленьких N, до трех дней для N=37.

2) Выборочно берем последовательность длины 8 операций, полным перебором увеличиваем ее на 3 шага. После чего к полученным последовательностям применяем процедуру "Оливос". Выбор перспективных последовательностей это чистая эвристика. Я использовал:
- случайный выбор;
- формирование списка начальных последовательностей для моих лучших решений и попытка построить решения для других N;
- а так же множество других шаманских способов.

3) Преобразование A(A+1)B^2=AB(AB+B), несмотря на всю примитивность, обладает термоядерной силой. Больше половины моих решений дотачивалось этим преобразованием!

 Профиль  
                  
 
 Re: Factorials
Сообщение21.04.2013, 21:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #713740 писал(а):
3) Преобразование A(A+1)B^2=AB(AB+B), несмотря на всю примитивность, обладает термоядерной силой. Больше половины моих решений дотачивалось этим преобразованием!

Пример оптимального решения, полученного с помощью этого преобразования, можете привести?

Я пыталась применить этот преобразование, но оптимальных решений мне не удалось найти. Решения плюс 1 от оптимального получаются легко.

Пример:

$22! = 4199 \cdot (4199 + 1) \cdot 7983360^2$

[разложение найдено whitefox]

Решение в 15 шагов на основе этого разложения:

Код:
1,2,4,8,10,40,42,100,4200,48,1920,4158,7983360,33530112000,33530107800,1124268269906073600000

Решение для 22! в 14 шагов для меня оказалось камнем преткновения. Я потратила на его поиск много сил и времени. Нашла разные варианты решений в 15 шагов, а в 14 шагов мне так и не удалось найти решение. Не удалось это и участникам команды.

Вот, например, решение в 15 шагов на основе разложения:

$22! = 8398 \cdot (8398+2) \cdot 3991680^2$

(все разложения подобного типа найдены whitefox)

Код:
1,2,4,16,20,21,420,8400,24,396,10080,3991680,15933509222400,8398,70543200,1124000727777607680000

А вот решение на основе разложения:

$22! =705432 \cdot (11!)^2$

Код:
1,2,4,6,10,40,42,400,16800,16796,705432,396,100800,39916800,1593350922240000,1124000727777607680000

Здесь интересный случай: по ходу процедуры найдены решения для 11! в 13 шагов:

Код:
found 3 solutions for 39916800 in 13 steps
1,2,4,6,10,40,42,400,16800,16796,705432,396,100800,39916800
1,2,4,6,10,40,42,400,16800,16796,705432,396,2376,39916800
1,2,4,6,10,40,42,400,16800,16796,705432,396,6652800,39916800

Поиск в этом примере начинался с числа 705432; были найдены все решения для этого числа в 10 шагов. Затем от найденных последовательностей искалось число 11!
Было найдено всего три решения (они показаны).

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 01:01 
Заблокирован


21/04/13

78
wanderers в сообщении #713672 писал(а):
Вроде все приведенные решения для больших n вписываются в две формулы: n!=a*c^2 и n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y. Отсюда и метод решения: генерируем для каждого n две таблицы - одну из двух столбцов, а вторую - из трех. Далее используем технику хеширования. Теперь по поводу техники работы с записями: я генерировал базу размером примерно 600 мегабайт, содержащую записи, каждая из которых включает 10 членов. При этом использовалась техника быстрой генерации неповторяющихся записей и такая очевидная эмпирика, как ограничение общего числа аддитивных операций в записи, и ограничение в их непрерывности следования. Ну и разное по мелочи. Для примера рассмотрим самый последний факториал 37! в финальной таблице конкурса. Приведем соответствующую запись к "божескому" виду.
4, 6, 36, 144, 216, 210, 220, 31680, 31464, 31824, 46656, 46620, 6652800, 310153536000, 211718707200, 6661517403340800, 6661729122048000, 44377224482864980286137958400000, 3763753091226345046315979581580902400000000

x=31464
a=211718707200
y=6652800*46620=310153536000
x*a=6661517403340800
x*a+a=6661517403340800+211718707200=6661729122048000
(x*a)*(x*a+a)=44377224482864980286137958400000
n!=(x*a)*(x*a+a)*y=
44377224482864980286137958400000*310153536000=13763753091226345046315979581580902400000000
У меня решение задачи для 31! на 14 ядрах заняло примерно полчаса.

Думаю, что скорее всего победители и пользоваались подобной техникой, но пока на yahoo они пишут о несущественных, хотя и важных технических деталях: ясно, что действительный набор решений намного богаче и разнообразней - для этого достаточно ознакомиться с решениями для 13!, 14!, 15!, 16! и 17!. Правда, Tomas Rokicki туманно намекает на некие таблицы. Интересно также посмотреть на завулированность многих решений, которые на самом деле сводятся к двум примитивным формулам. Хотел бы уточнить метод хранения записей в моей базе данных: они хранятся в виде буквы "T". Например, для n = 3, сначала идут 1 и 2, а потом "шляпка" в виде 3-ки и 4-ки. Иначе бы база разрослась до многогигабайтных размеров. Но здесь самое главное важен не метод хранения (многогигабайтность можно и пережить), а то, что такая форма представления записей позволяет использовать эффективный метод генерации неповторяющихся записей.

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 05:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Немного о полиномах...

Это полином Pavlovsky для 26!:

f(x)=$32x^{16}+544x^{15}+4088x^{14}+17648x^{13}+47428x^{12}+79616x^{11}+76890x^{10}+28956x^9-13095x^8-12022x^7+640x^6+800x^5$
$f(36)=26!$

По упаковке данного полинома, предложенной dmd, мне удалось получить решение в 17 шагов:

Код:
1,2,4,6,36,38,72,2736,2772,103968,104004,104000,99792,10378368000,
107710522343424000000,104006,3744216,403291461126605635584000000

Потом whitefox нашёл оптимальную упаковку полинома:

$f(x)=x(x+2)(1+2x(x+2))((x+2x(x+2))(x(x+2)(1+2x(x+2))-6x))^2$

по которой получено решение в 15 шагов:

Код:
1,2,4,6,36,38,1368,2736,2737,3744216,2772,216,3744000,10378368000,
107710522343424000000,403291461126605635584000000

Пример весьма показательный: один и тот же полином, но по-разному упакован, что дало экономию двух шагов.

[А сам автор полинома сначала имел упаковку, дающую решение в 16 шагов.]

Я тут приводила полином для найденного мной оптимального решения N=21. Решение это найдено по алгоритму №1, то есть на основе разложения:

$21! = 3879876 \cdot (10!)^2$

Решение:

Код:
1,2,4,6,24,144,150,168,25200,3628800,154,25194,3879876,13168189440000,
51090942171709440000

По готовому решению составляю полином (это делается очень просто):

$f(x)=262144 x^{18}+1114112 x^{17}+1785856 x^{16}+1208320 x^{15}+96256 x^{14}-308224 x^{13}-150016 x^{12}-17920 x^{11}+2560 x^{10}+512 x^9$
$f(6)=21!$

А вот найти оптимальную упаковку данного полинома, на мой взгляд, совсем не просто. Упаковка должна вычисляться всего за 11 операций (шагов).
dmd мой взгляд назвал субъективным, однако не предложил оптимальную упаковку этого полинома. Предложенные им упаковки за 11 операций вычислить невозможно.
Это оптимальная упаковка:

$f(x)=(4 x^2 (4 x^2+ x)(4 x^2+4 x))^2 \cdot (4 x^2+ x+(x-2))((4 x^2+ x)(4 x^2+4 x)- x)$

Я тоже вряд ли смогла бы оптимально упаковать полином. Упаковку я получила по готовому решению - это сделать гораздо проще.

Эти два полинома (для 26! и 21!) очень красивы по своим оптимальным упаковкам.
Есть ли у кого-нибудь подобные полиномы для других N?

-- Пн апр 22, 2013 06:55:23 --

У меня есть ещё полином для 13!

$f(x)=x^8+6x^7+17x^6+32x^5+39x^4+28x^3+12x^2$
$f(16)=13!$

Полином составлен по решению mertz:

Код:
1,2,4,16,14,18,288,274,78912,21621888,21621600,6227020800

Оптимальная упаковка данного полинома:

$f(x)=x(x+2)(x(x+2)(x(x+2)-(x-2))^2-x(x+2))$

Интересно, что для этого полинома Вольфрам предложил тоже оптимальную упаковку:

$x^2(x+2)^2((x^2+x+2)^2-1)$

По этой упаковке получилось такое решение:

Код:
1,2,4,16,256,18,324,82944,274,75076,75075,6227020800


-- Пн апр 22, 2013 07:16:01 --

Опубликованы решения конкурсантов.
Забавно - решение для 19! с отрицательными числами:

Код:
1, 2, 4, 16, -14, -224, -220, 18, 324, 104976, -23514624, 23514400, -5173168000, 121645100408832000

Всего конкурсанты нашли 13 решений для 19!

Это 9 решений, найденных mertz:

Код:
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,104976,23514624,23514400,5173168000,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,104976,23514624,23514400,5173217280,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,104976,23514624,23514400,552932274585600,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,72576,23514624,23514400,5173168000,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,72576,23514624,23514400,5173217280,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,16,14,18,224,220,324,72576,23514624,23514400,552932274585600,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,6,24,576,600,2400,2394,2970,7128000,7128576,17064432000,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,6,24,576,600,2400,2394,2970,7128000,7128576,17065810944,121645100408832000
19! = 121645100408832000 = [13] 1,2,4,6,24,576,600,2400,2394,2970,7128000,7128576,50812489728000,121645100408832000

Первое решение полностью совпадает с приведённым решением конкурсанта, если все числа взять без знака минус.

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 06:29 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ой, наврала :? Это там в графе указано количество шагов (13), а я подумала, что количество решений.
Вот все решения, найденные конкурсантыми, их 10 щтук:

Код:
1, 2, 4, 6, 24, 576, 600, 2400, 2394, 2970, 7128000, 7128576, 17064432000, 121645100408832000
1, 2, 4, 6, 24, 576, 600, 2400, 2394, 2970, 7128000, 7128576, 17065810944, 121645100408832000
1, 2, 4, 6, 24, 576, 600, 2400, 2394, 2970, 7128000, 7128576, 50812489728000, 121645100408832000
1, 2, 4, 16, -14, -224, -220, 18, 324, 104976, -23514624, 23514400, -5173168000, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 72576, 23514624, 23514400, 5173217280, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 72576, 23514624, 23514400, 552932274585600, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 104976, 23514624, 23514400, 5173217280, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 104976, 23514624, 23514400, 552932274585600, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 104976, 23514624, 23514400, 5173168000, 121645100408832000
1, 2, 4, 16, 14, 18, 224, 220, 324, 72576, 23514624, 23514400, 5173168000, 121645100408832000

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

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 06:31 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #713756 писал(а):
Пример оптимального решения, полученного с помощью этого преобразования, можете привести?


Начальная последовательность 1,2,3,9,27,36,324,351,123201
Разложение 23! на множители, найденное перебором: 322*323*351*123200^2*36^3
1,2,3,9,27,36,324,351, 123201,322,323, 123200, 4435200, 19670999040000, 708155965440000, 248562743869440000, 80285766269829120000, 25852016738884976640000
Итого 17 операций

Применяем преобразование A*(A*A-1)^2*B^3=(AB)*(A*(AB)-B)^2
322*323*(351*36)*(351*(351*36)-36)^2
1,2,3,9,27,36,324,351,322,323, 12636, 4435236, 4435200, 19670999040000, 6353732689920000, 2045901926154240000, 25852016738884976640000
Итого 16 операций

Применяем преобразование A(A+1)B^2=(AB)(AB+B)
322*(322+1)*12636* 4435200^2
(322*4435200)*(322*4435200+4435200)*12636
1,2,3,9,27,36,324,351,322,12636,4435236,4435200, 1428134400, 1432569600, 2045901926154240000, 25852016738884976640000
Итого 15 операций

Преобразование A(A+1)B^2=(AB)(AB+B) было "открыто" при решении задачи для 19!
Начальная последовательность: 1,2,4,16,14,224,220,18,324,104976
Разложение: 19!=104975*220*104976*224^2
Преобразование:
(104976*224-224)*220*(224*104976)
1,2,4,16,14,224,220,18,324,104976,23514624,23514400,552932274585600,121645100408832000

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 06:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky, получается что все ваши преобразования основаны на том что в решении есть +/-1. А что если такого нет, какие тогда преобразования можно применить?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 53, 54, 55, 56, 57, 58, 59 ... 88  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group