Factorials

[wanderers]

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

(Оффтоп)

-- Так вот, -- говорил им на это Король, -- когда появится Цветная
Капуста, вы на эту зеленую даже смотреть не захотите.
-- Господи, -- вздыхали кролики, услышав такое, -- неужели доживем до
этого?
-- Будьте спокойны, -- кивал Король, -- следим за опытами и
способствуем...

(С) Фазиль Искандер.

К тому, что я написал только что выше, мне добавить нечего, разве что дам Вам один дельный совет: не пыжтесь, а то лопните, да так, что и мокрого места не останется.

[Pavlovsky]

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

мой алгоритм будет опубликован в уважаемом издании, к которому таких, как Вы, и на пушечный выстрел не подпускают.

Скажите хоть название журнала.

[Nataly-Mak]

(Оффтоп)

По масштабам хвастовства и хамства wanderers очень сильно похож на "сашудворкина" (был такой в теме о конкурсе с перекладыванием карт).
Не удивлюсь, если это он и есть

dvorkin_sacha начинает:

dvorkin_sacha в сообщении #377878 писал(а):

А ведь $n=17$ интересно тем, что для него известен точный результат, который за разумное время в лоб на одном компе не посчитаешь (лет 20 уйдет для неплохого компа). У меня расчет в лоб для $n=13$ занял порядка одной минуты, а оптимизированный - доли секунды.

Клонов у dvorkin_sacha не есть числа. Неоднократно забаненный, он возрождается, как птица Феникс из пепла, и продолжает вовсю хамить на форуме.

cepesh в сообщении #417527 писал(а):

dvorkin_sacha

Вы забанены за двойную регистрацию, хамство и троллинг.

[whitefox]

(Оффтоп)

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

По масштабам хвастовства и хамства wanderers очень сильно похож на "сашудворкина"

Похоже, что это Ваш старый знакомый:

sigolaevy писал(а):

While here I read only the minor details. The task dares simply: for big n we
have two formulas n1=a*c^2 and n1 = (x*a) * (x*a +-a) *y. It is necessary to
generate two tables for the first and second case and to use hash coding.
The algorithm description in Russian see:
http://dxdy.ru/post713672.html#p713672

Забавно как он сам называет себя бароном Мюнхаузеном:

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

Так что Yurii Sigolaev - это барон Мюнхаузен в чистом виде.

[Nataly-Mak]

(Оффтоп)

Цитата:

sigolaevy писал(а):

Ого!
Любопытно весьма!
Так значит Yurii Sigolaev и есть wanderers.

Прочтите-ка наш диалог с Yurii Sigolaev на форуме ПЕН:

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

omega (это я):
"Так вы и сами можете там выложить."

YuriiS:
"Не могу: я на dS забанен."

Сомнений не остаётся: клоны продолжают плодиться

-- Вт апр 23, 2013 20:53:20 --

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

(Оффтоп)

Похоже, что это Ваш старый знакомый...

(Оффтоп)

О! Вы даже не представляете, насколько старый знакомый...
За 5 лет пребывания на этом форуме я помню как минимум 5 клонов этого персонажа.
О других форумах не буду говорить.
Мне хорошо известно подлинное имя этого персонажа.
Я почти всегда безошибочно узнаю его в многочисленных клонах. Иногда, правда, не сразу.
Например, в YuriiS не сразу узнала.
Есть много очень характерных признаков, по которым персонаж легко узнаваем.

[dimkadimon]

Друзья, ну зачем ругаться? Мы тут все занимаемся любимым делом - решаем интересную задачу. Предлагаю вернуться к оригинальной теме.

Кто нибудь пробовал искать решения с конца? У меня были идеи, но я их так и не закодил. Например можно начать с N! и рекурсивно разбивать числа на два фактора. Причем чем ближе факторы по размеру тем лучше:

6!=720=24*30
---
24=4*6
30=5*6
---
4=2*2
6=2*3
5=2+3
---
2=1+1
3=1+2

Получается вот такое решение: 1, 2, 3, 4, 5, 6, 24, 30, 720

7!=5040=70*72
70=7*10
72=8*9
...

Получается 1,2,3,4,7,8,9,10,70,72,5040.

-- 24.04.2013, 10:02 --

Кто нибудь начал решать 1000!? Я выкладываю свои решения для N=100 и N=200. Оптимальное решение они не дадут но должны помочь:

(Оффтоп)

N=100
53: 0+0, 1+1, 2*2, 0+3, 4*4, 4*5, 6-3, 1+7, 6*8, 4+9, 9*10, 7*11, 3+6, 10-13, 12*14, 14*15, 7+8, 16*17, 13*18, 10+17, 20*20, 19*21, 21*22, 7-4, 23*24, 24-0, 25*26, 7+26, 27*28, 7+28, 29*30, 28*31, 0+30, 32*33, 33*34, 33*35, 20*36, 24-3, 38*38, 37*39, 39*40, 13+17, 41*42, 38-2, 3*44, 45*45, 43*46, 46*47, 13+30, 48*49, 45*50, 0+1, 51*52

N=200
95: 0+0, 1+1, 2*2, 0+3, 4*4, 4*5, 6-3, 1+7, 6*8, 4+9, 9*10, 7*11, 3+6, 10-13, 12*14, 14*15, 7+8, 16*17, 13*18, 10+17, 20*20, 19*21, 21*22, 7-4, 23*24, 24-0, 25*26, 7+26, 27*28, 7+28, 29*30, 28*31, 0+30, 32*33, 33*34, 33*35, 20*36, 24-3, 38*38, 37*39, 39*40, 13+17, 41*42, 38-2, 3*44, 45*45, 43*46, 46*47, 13+30, 48*49, 45*50, 0+1, 51*52, 50*51, 45-8, 54*55, 44+49, 57-6, 56*58, 0+42, 59*60, 28-5, 61*62, 57*63, 7+57, 64*65, 42+65, 66*67, 38-3, 65-69, 68*70, 13-2, 71*72, 13+52, 2*74, 0+75, 73*76, 75-17, 77*78, 74*79, 72-38, 52*81, 82-3, 80*83, 81*84, 81-1, 52*86, 74+87, 85*88, 1*86, 90-4, 87+91, 89*92, 91*93, 86*94

[Nataly-Mak]

Я много раз пользовалась таким простым приёмом, как домножение.
При этом переход делала не только от (N-1)! к N!, но и от от (N-m)! к N!, m>1.

Покажу один пример - получение решения для 37! от оптимального решения для 30!
Это оптимальное решение для 30! в 17 шагов:

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

Домножать здесь нужно на число

$31 \cdot 32 \cdot 33 \cdot 34 \cdot 35 \cdot 36 \cdot 37=51889178880$

Даже не надеялась, что можно выполнить домножение на такое большое число, но попробовала и... получилось.
В качестве начальной последовательности берётся решение для 30! без двух последних членов:

1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,25344,25346,155117520,
1307674368000

От этой последовательности ищется число 51889178880. Это удаётся сделать за 5 шагов.

1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,25344,25346,155117520,
1307674368000,217,6512,1328040,8648196480,51889178880

Добавляем к последовательности два последних члена из решения для 30! и выполняем последнее умножение. Готовое решение для 37! в 23 шага:

1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,25344,25346,155117520,
1307674368000,217,6512,1328040,8648196480,51889178880,1710012252724199424000000,
265252859812191058636308480000000,
13763753091226345046315979581580902400000000

Конечно, решение не ахти (плюс 3 от оптимального), но всё равно хорошо. Это решение я получила как только нашла оптимальное решение для 30!
Уже перед самым концом конкурса (19 апреля) мне удалось улучшить его на 1 шаг:

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

Ну, а домножение на меньшие числа (m=2, m=3, m=4...) выполнялось гораздо проще, если вообще было возможно.
Когда были найдены оптимальные решения для N=25,26,30, попробовала все варианты домножений, чтобы найти решения для бОльших N.

[whitefox]

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

Кто нибудь пробовал искать решения с конца? У меня были идеи, но я их так и не закодил. Например можно начать с N! и рекурсивно разбивать числа на два фактора

А алгоритм №1 Nataly-Mak и его модификации разве не относятся к этой категории?
Там ведь тоже в начале N! разбивается на множители $\mathrm N! =\mathrm A\cdot\mathrm B\cdot\mathrm B$
Но дальнейшая рекурсия не выполняется, так как один из множителей, обычно, принадлежит имеющейся базе данных, а второй получается коротким достраиванием.
Если же ни один из множителей базе данных не принадлежит, либо достраивание слишком длинное, то тогда и выполняется рекурсия.

[Nataly-Mak]

(Оффтоп)

О wanderers смотрите здесь
post714805.html#p714805

[wanderers]

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

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

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

Вообще говоря, при решении задачи более "длинных", чем unsigned __int64 переменных не требуется. Но при генерации таблиц по приведенным формулам для больших n это не так. Для этого я использовал long double с учетверенной точностью собстсвенной разработки (замечу, что для этого компилятор мелкомягких не годится), т.к. фортрановский компилятор интела хоть и поддерживает учетверенную точность, но с их подходом к реализации этой самой учетверенной точности можно эти таблицы сто лет строить. На первый взгляд, например, 37! не засунуть в переменную моей реализации, но это не так: ведь все степени двойки "прячутся" в показатели степени!!! В моей реализации учетверенной точности под мантиссу отводится 126 бит, которые в целочисленном случае все и используются, тогда как у интела под мантиссу отводится всего 112 бит и при этом моя реализация "пашет" раз в 15 быстрей!

[Nataly-Mak]

(Оффтоп)

Фантастика!
wanderers забанен, но пишет сообщения

[wanderers]

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

whitefox, в настоящем споре я вас не очень понимаю. Вроде wanderers уже описал свой алгоритм: использовать формулы n!=a*c^2 и n!=(x*a)(x*a-a)*y. Я не очень разобрался в генерации базы данных но видимо алгоритм достаточно быстрый если он смог найти N=31 за пол часа на 14 ядрах. Или я что то не так понял?

Дима, киньте Ваше мыло мне в личку: как только мое железо освободится, перешлю Вам то, что обещал.

[Nataly-Mak]

(Оффтоп)

Гениям не страшен бан. Они элементарно саморазбаниваются

dimkadimon
искренне не советую вам связываться с прохиндеем.
Если вы мне не верите, посмотрите тему, ссылку на которую дала чуть выше.
Я в той теме участия не принимала.
Посмотрите, сколько у него клонов!
Приличные люди не клонируются, а участвуют в форуме под одним и тем же ником.

[whitefox]

(Оффтоп)

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

Гениям не страшен бан. Они элементарно саморазбаниваются

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

Дима, киньте Ваше мыло мне

Но вот без мыла в бане ну никак

-- 24 апр 2013, 09:40 --

И снова Gerbicz

10    .274    Raw Score = 1000    Adelaide, Australia

Дойдёт ли он до 250 шагов?

[Pavlovsky]

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

Кто нибудь пробовал искать решения с конца?

Сначала я пытался реализовать этот подход. Первые мои результаты были получены именно этим подходом.

1) Разложение на множители. Чтобы избавиться от дублей, в разложении A=B*C, число B обявлялось неделимым. То есть в дальнейшем с ним нельзя делать операцию разложения на множители.
2) Операции вычитания и сложения. При операции вычитания возникает опасность зацикливния. То есть сначала мы определяем A=B-C. А когда настает черед числа B мы его можем представить B=A+C. Прямая проверка этой ситуации получается слишком затратной. К тому же вариантов разложения A=B+C слишком много. Поэтому операции сложения и вычитания в чистом виде я запретил. А использовал разложение A=B*C+D;A=B*C-D. Где D<<B,C.
3) Для болших N использовал начальное разложение. N!=AB^2, где B максимальное возможное. Для очень больших N использовал это разложение дважды.

Такой подход позволил получить результаты на уровне 0,8 балла.