2014 dxdy logo

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

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




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


22/03/08

7154
Саратов
Pavlovsky в сообщении #713866 писал(а):
Применяем преобразование 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 операций

Ну, тут, по-моему, главное было найти вот это хорошее разложение:

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

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

Кстати, я где-то писала об этой интересной находке:

$104006 = 322 \cdot (322+1)=322^2+322=323^2-323=2 \cdot 7 \cdot 17 \cdot 19 \cdot 23$

Не пошла чуточку дальше :-)

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


21/02/10
1594
Екатеринбург
dimkadimon
Я достаточно много времени уделил поиску преобразований, но увы ничего другого не нашел.

Перебор основным алгоритмом я организовал так: порог на длину последовательности задавал на единицу хуже рекордного. Причем алгоритм не останавливался на первом найденом решении, а продолжал работать пока не будут найдены все последовательности меньше или равные заданному порогу. Затем просматривал все найденные последовательности, на возможность применить преобразование.
Посмотрел свои решения.
Pavlovsky в сообщении #713740 писал(а):
половины моих решений дотачивалось этим преобразованием!

Тут я немного соврал. Практически все мои решения получены преобразованием A(A+1)B^2=(AB)(AB+B).

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 07:21 


16/08/05
1121
21! (база 1,2,4,6,24):

$(6 x (6 x + 6) (6 x + x))^2 (6 x + 6 + 4) ((6 x + 6) (6 x + x) - 6)$

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #713869 писал(а):
Ну, тут, по-моему, главное было найти вот это хорошее разложение:

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

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

Сейчас по приведённому разложению организовала поиск решения в программе mertz.

1 этап
ищу все решения для числа 12636 в 8 шагов. Найдено 279 решений.

2 этап
от найденных последовательностей ищу решения, в которых 9-ым шагом появляется число 322. Найдено 15 решений:

Код:
1,2,3,4,9,36,39,324,12636,322
1,2,3,6,18,21,324,39,12636,322
1,2,3,6,18,36,324,39,12636,322
1,2,3,6,36,39,108,324,12636,322
1,2,3,6,9,36,39,324,12636,322
1,2,3,9,12,108,324,117,12636,322
1,2,3,9,12,27,39,324,12636,322
1,2,3,9,12,36,39,324,12636,322
1,2,3,9,18,21,324,39,12636,322
1,2,3,9,18,36,324,39,12636,322
1,2,3,9,27,36,324,351,12636,322
1,2,3,9,27,36,39,324,12636,322
1,2,3,9,81,162,78,160,12636,322
1,2,3,9,81,162,78,161,12636,322
1,2,3,9,81,162,78,324,12636,322

3 этап
от найденных решений ищу решения для числа 4435200 в 11 шагов. Найдено только одно решение:

Код:
found 1 solutions for 4435200 in 11 steps
1,2,3,9,27,36,324,351,12636,322,4435236,4435200

Последним этапом выполняем 4 операции и получаем готовое решение:

Код:
1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

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


21/04/13

78
Nataly-Mak в сообщении #712587 писал(а):
dimkadimon
Сейчас уместно привести сообщение YuriiS на форуме ПЕН:
http://e-science.ru/forum/index.php?s=& ... t&p=393039

Цитата:
Если у кого есть желание и минута свободного времени, то развейте "страшные" слухи по поводу 19! на dxdy: это как раз самый благоприятный вариант из всех возможных для компьютерной реализации - у меня он проходит за неуловимые доли секунды. При расчете не учитывалась специфика 19!, а использовался общий подход.

YuriiS участник конкурса (см. Yurii Sigolaev).

У меня есть предположение, что здесь речь идёт о поиске только одного решения, а не всех 9 решений (а и всех-то, кажется, не 9 :?: ), но могу ошибаться. Хотя трудно поверить, что полный поиск для 19! может выполниться за "неуловимые доли секунды" :-)
Это всё-таки решения в 13 шагов!

Как я понимаю, Yurii Sigolaev сильно "загнул". Давайте рассмотрим одно из решений для 19!:
1, 2, 4, 16, 14, 18, 224, 220, 324, 104976, 23514624, 23514400, 5173217280, 19!
В свете описанного мною выше подхода имеем:
x=104976
a=224
y=220
x*a=23514624
x*a-a=23514400
(x*a)*(x*a-a)=5173217280
(x*a)*(x*a-a)*y=19!
Но (x), (a) и (y) находятся в первой десятке! Что это значит? А это значит то, что решение уже забито в моей базе данных (я писал, что последовательности в моей базе данных состоят из 10 чисел, а точнее, устроены еще более хитро: в виде буквы "T", о чем я писал во втором моем сообщении), т.е. уже никаких расчетов делать нет необходимости - необходим только поиск уже готового решения!!! А база занимает у меня порядка 600 мегабайт. Делим 600 на 14 (число доступных ядер на моих трех компах) и получаем порядка 40 мегабайт. Но такую порцию информации за неуловимые доли секунды с харда не считать. Так что Yurii Sigolaev - это барон Мюнхаузен в чистом виде. Еще не забываем, что требуется далеко не секунды для генерации таблиц, в которых и "зарыта собака" эффективного и однообразного решения конкурсной задачи. Хотя Yurii Sigolaev может пользовался более феноменальным алгоритмом, который я описал: это необходимо спросить у него. Весьма вероятно, что он имел в виду расчетное время: тогда он прав - нет даже и неуловимых долей секунды, о которых он писал. Теперь о трудностях с 28!: строчка (111838662144 1651104000) в сгенерированной мною таблице является 282-ой!!! Это и обусловило трудности нахожденя решения (не у меня - поиск решения моим методом длится несколько секунд на 14 ядрах).

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 08:11 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Gerbicz в сообщении #674406 писал(а):
This puzzle is good for small kids to play with numbers and operations.

Gerbicz в сообщении #713295 писал(а):
In spoj I would set these problems to the tutorial section, ideal for small kids, up to 12 years.


Гы-гы-гы :lol:
Это такая методика -- объявить "детской" задачу которую не можешь решить.
Эзоп писал(а):
Под лозами лиса, терзаясь голодом,
До виноградных гроздьев вспрыгнуть силилась,
Но не смогла, и уходя, промолвила:
«Еще незрел он: не люблю кислятины!»
Кто на словах порочит непосильное.
Свое здесь должен видеть поведение.

Та же басня в английском переводе:
Aesop писал(а):
Driven by hunger, a fox tried to reach some grapes hanging high on the vine but was unable to, although he leaped with all his strength. As he went away, the fox remarked, 'Oh, you aren't even ripe yet! I don't need any sour grapes.' People who speak disparagingly of things that they cannot attain would do well to apply this story to themselves.

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


22/03/08

7154
Саратов
Мне удалось воспользоваться другим преобразованием, предложенным Pavlovsky:

$A(AC-1)B^2=AB(ABC-B)$

Правда, решение получено не оптимальное, а 16 шагов, но у меня и 16 шагов очень долго не получалось.
Разложения под это преобразование нашёл whitefox, таких разложений очень много.

$24! =191600640^2 \cdot 323 \cdot (323 \cdot 162-1)$

Решение:

Код:
1,2,3,9,81,162,324,323,171,13851,13842,191600964,191600640,61887006720,10025695088640,10025503488000,620448401733239439360000

Pavlovsky
у вас есть оптимальные решения, полученные на основе приведённого преобразования?

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


21/02/10
1594
Екатеринбург
Преобразование можно использовать для получения оптимального решения для 24! :D
Начальная последовательность: 1,2,4,16,18,324,308,104976
Разложение: 24!=104976*104975*18*322*(308*320)^2
Преобразование: (104976*308*320)*(104976*308*320-308*320)*18*322
Решение:
1,2,4,16,18,324,308,104976, 320, 322, 98560,10346434560,10346336000, 107047688359772160000, 1926858390475898880000, 620448401733239439360000

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


21/04/13

78
Хочу отметить, что 24! вписывается в парадигму (y, x, a).

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #713881 писал(а):
Pavlovsky
у вас есть оптимальные решения, полученные на основе приведённого преобразования?


Преобразование $A(AC-1)B^2=AB(ABC-B)$ мне удалось применить лишь однажды для 23!

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


21/04/13

78
И 23! вписывается также в парадигму (y, x, a).

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


21/02/10
1594
Екатеринбург
wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются. :D

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


22/03/08

7154
Саратов
wanderers в сообщении #713888 писал(а):
И 23! вписывается также в парадигму (y, x, a).

Вот это

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

и есть та самая парадигма?

Цитата:
n!=(x*a)(x*a+a)*y

Она единственная для 23! или есть другие?

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


21/04/13

78
Pavlovsky в сообщении #713890 писал(а):
wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются. :D

Я об этом и не думаю: просто считаю, что приводимая мною информация как раз и поможет сократить ваше время для обдумывания.

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


01/06/12
1013
Adelaide, Australia
На сайте есть оптимальные решения в которых есть +/-1. Можно ли их улучшить преобразованиями? Например:

N=29:
1, 2, 4, 8, 64, 68, 544, 540, 539, 552, 34560, 35100, 18918900, 653837184000, 360918125568000, 360264288384000, 130025911672642675802112000000, 8841761993739701954543616000000

N=31:
1, 2, 3, 4, 12, 14, 168, 672, 675, 8100, 7425, 7424, 1247400, 1255500, 838252800, 1052426390400000, 1052427228652800, 7813219745518387200, 8222838654177922817725562880000000

N=35:
1, 2, 4, 6, 36, 35, 216, 220, 864, 880, 874, 899, 30240, 785726, 6652800, 6683040, 5227277932800, 44460928512000, 232409630482575939993600000, 10333147966386144929666651337523200000000

N=36:
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 265914909018965606400000, 371993326789901217467999448150835200000000

N=37:
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 50361071569256448000, 51759990223958016000, 2068866205391165380939751620608000000, 13763753091226345046315979581580902400000000
1, 2, 4, 6, 36, 35, 37, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000, 1398963115630080000, 1398918654701568000, 55915302848409875160533827584000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000

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

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



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

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


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

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