Factorials

[Nataly-Mak]

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

Я нахожу 45 решений для 12 за 15 секунд. Все числа делители 12!

С этим ограничением, понятное дело, будет быстрее.
Сейчас сделаю это на моей машине.

-- Пт апр 19, 2013 15:14:14 --

Программа mertz нашла первые 38 решений за 14 секунд, потом появились 48 решений на 58-ой секунде. Больше решений не найдено, всего программа работала 2 мин. 22 сек.
Это с ограничением, что ищутся решения, состоящие только из делителей 12!
Вот эти 48 решений:

(Оффтоп)

found 48 solutions for 479001600 in 10 steps
1,2,4,6,12,144,150,154,21600,22176,479001600
1,2,4,6,12,144,150,154,21600,3110400,479001600
1,2,4,6,12,144,150,154,21600,3326400,479001600
1,2,4,6,12,144,150,154,22176,3193344,479001600
1,2,4,6,12,144,150,154,22176,3326400,479001600
1,2,4,6,12,144,150,154,23100,3326400,479001600
1,2,4,6,12,144,150,20736,154,23100,479001600
1,2,4,6,12,144,150,20736,154,3110400,479001600
1,2,4,6,12,144,150,20736,154,3193344,479001600
1,2,4,6,12,144,150,576,21600,22176,479001600
1,2,4,6,24,144,150,154,21600,22176,479001600
1,2,4,6,24,144,150,154,21600,3110400,479001600
1,2,4,6,24,144,150,154,21600,3326400,479001600
1,2,4,6,24,144,150,154,22176,3193344,479001600
1,2,4,6,24,144,150,154,22176,3326400,479001600
1,2,4,6,24,144,150,154,23100,3326400,479001600
1,2,4,6,24,144,150,20736,154,23100,479001600
1,2,4,6,24,144,150,20736,154,3110400,479001600
1,2,4,6,24,144,150,20736,154,3193344,479001600
1,2,4,6,24,144,150,576,21600,22176,479001600
1,2,4,6,24,30,576,720,21600,22176,479001600
1,2,4,6,24,30,576,900,21600,22176,479001600
1,2,4,6,24,30,576,900,924,518400,479001600
1,2,4,6,24,30,576,900,924,532224,479001600
1,2,4,6,24,30,576,900,924,831600,479001600
1,2,4,6,24,30,720,900,518400,924,479001600
1,2,4,6,24,30,720,900,924,665280,479001600
1,2,4,6,24,30,900,924,21600,19958400,479001600
1,2,4,6,24,30,900,924,21600,22176,479001600
1,2,4,6,24,30,900,924,21600,518400,479001600
1,2,4,6,24,30,900,924,22176,19958400,479001600
1,2,4,6,24,30,900,924,22176,532224,479001600
1,2,4,6,24,30,900,924,831600,19958400,479001600
1,2,4,6,24,36,576,600,21600,22176,479001600
1,2,4,6,24,576,600,3600,21600,22176,479001600
1,2,4,6,24,96,90,2304,2310,207360,479001600
1,2,4,6,24,96,90,2304,2310,207900,479001600
1,2,4,6,24,96,90,2304,2310,5322240,479001600
1,2,4,6,36,144,150,154,21600,22176,479001600
1,2,4,6,36,144,150,154,21600,3110400,479001600
1,2,4,6,36,144,150,154,21600,3326400,479001600
1,2,4,6,36,144,150,154,22176,3193344,479001600
1,2,4,6,36,144,150,154,22176,3326400,479001600
1,2,4,6,36,144,150,154,23100,3326400,479001600
1,2,4,6,36,144,150,20736,154,23100,479001600
1,2,4,6,36,144,150,20736,154,3110400,479001600
1,2,4,6,36,144,150,20736,154,3193344,479001600
1,2,4,6,36,144,150,576,21600,22176,479001600

Пока я уходила на форум, у меня программа нашла решение для 37!
Удивительно! Продолжаю всё тот же алгоритм, что показан выше на примере для 36!
И получилось!
Теперь решение для 37! всего плюс 2 от оптимального. Это хорошо для нас

[mertz]

non-factor pruning for 12!, 48 solutions < 1 second. You are missing 3 of the solutions. Do you have a defect in your search or is there more pruning?

[dimkadimon]

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

non-factor pruning for 12!, 48 solutions < 1 second. You are missing 3 of the solutions. Do you have a defect in your search or is there more pruning?

That's very fast! I am not doing a full search so I am not going to find all the solutions.

[mertz]

There is more to optimize. I can see another 5 times improvement. Lists kept in ascending order would allow faster look ups if the insertion list is fast enough. SSE4.1 and AVX have many 256-bit integer instructions that would help. Code generators to build custom functions for each level of the recursion. So many things to try, so little time...

[Nataly-Mak]

Ну что, други, приуныли?

Конкурс заканчивается.
Десятка в этот раз для россиян оказалась недосягаемой.
В остальном всё замечательно

У меня ещё работают программы, ищут решение для 34!
Ищут и не находят
Так и не удалось мне поправить это безобразное решение "плюс 4" от оптимального.

mertz
у конкурса, как я понимаю, будет продолжение, которое организует dimkadimon.
Вы можете ещё попробовать все свои идеи по оптимизации программ.

Я пас Сыта этой задачей до "не могу".
Займусь своими любимыми квадратами Стенли. Возможно, напишу статью для сайта, материалов у меня в рабочем файле уже очень много накопилось. Пора бы это всё систематизировать и выложить на сайт.

Ещё раз приглашаю всех в тему о квадратах Стенли (она здесь на форуме - "Антимагические квадраты").

[Nataly-Mak]

Хорошо подтянулся вчера Gennady Gusev, оставив далеко позади фрау из Австрии (она всё время наступала ему на пятки ):

Цитата:

34 23.72 Gennady Gusev Rybinsk, Russia 19 Apr 2013 19:21
35 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
46 23.31 Alexandra Chrysothemis Salzburg, Austria 15 Apr 2013 19:38

Рядом с ним и Kalachev Gleb.

Кстати, в конкурсе с перекладыванием карт Kalachev Gleb в последний момент обошёл нашу команду. Запомнила этот момент

[Nataly-Mak]

И где все?

Интересно положение конкурсантов в альтернативной турнирной таблице:

Цитата:

1 24.85 Martin Piotte Montreal, Quebec, Canada 17 Mar 2013 19:36
2 24.83 Tomas Rokicki Palo Alto, California, United States 22 Feb 2013 03:36
3 24.58 Hermann Jurksch Recklinghausen, Germany 14 Mar 2013 23:03
4 24.31 Walter Trump Nuremberg, Germany 27 Mar 2013 21:27
5 24.30 Valentin Dobrota Constanta, Romania 7 Feb 2013 11:05
6 24.19 Lucien Pech Zürich, Switzerland 19 Apr 2013 23:25
7 24.17 Herbert Kociemba Darmstadt, Germany 30 Mar 2013 09:09
8 24.00 John Morris Simi Valley, California, United States 3 Apr 2013 23:47
9 23.90 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39
10 23.85 Siva Dirisala Foster City, California, United States 17 Apr 2013 08:57
11 23.80 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
12 23.59 Alex Chernov Penza, Russia 27 Feb 2013 10:40
13 23.44 Valery Pavlovsky Ekaterinburg, Russia 15 Apr 2013 03:37

25 баллов нет ни у кого. На первом месте канадец.
Трое наших подпирают топ-10.
Положение Pavlovsky почти не отличается от официальной таблицы.
А вот Vovka17 в альтернативной таблице аж на 61-ом месте.

Не нахожу ничего хорошего в этой таблице.

[Nataly-Mak]

Ура! Конкурс закончился!

Поздравляю всех!
Первым, конечно, поздравляю Pavlovsky

Цитата:

12 24.63 Valery Pavlovsky Ekaterinburg, Russia 15 Apr 2013 03:37

12-ое место всё-таки завоевано и зубы целы

В топ-10 наших, увы, нет
Во второй десятке только один Pavlovsky.

Ну, и в третьей десятке наших трое:

Цитата:

22 24.10 Vladimir Chirkov Bobruisk, Russia 8 Apr 2013 11:22
27 23.86 Viktor Polesov Moskow, Russia 20 Apr 2013 08:25
30 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40

Здесь и моя команда

(Оффтоп)

Чтобы не расстраивать Gerbicz, я решила выступать под псевдонимом. Надеюсь, что это не запрещено правилами конкурса. Ну, на всякий случай скрывала свой псевдоним
Ну, и думаю, что уже все поняли, что вторым участником моей команды был mertz.
Как уже говорила, команда у меня была замечательная. Программа mertz достойна всяческих похвал. Это очень мощный, многофункциональный инструмент. Удобно то, что все функционалы находятся в одной программе. В общем, мне очень и очень понравилась эта программа. Без неё я, конечно, не нашла бы многие из своих решений.

Vovka17, вас поздравляю со вторым местом среди россиян.
Вы к концу конкурса что-то немного утратили активность.

[Vovka17]

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

...
А вот Vovka17 в альтернативной таблице аж на 61-ом месте.

Просто я тугодум . Поэтому мне и понравились эти конкурсы, что никуда не надо спешить. Живи себе спокойно, переваривай задачку, а через несколько недель, начинай кодить...
Не могу сказать, что доволен своим достигнутым результатом, хотя как и в прежних конкурсах научился многому новому - это главное для меня. (Вот, например, уже совсем не боюсь многопоточного программирования ). Но задача как-то свелась больше к самому программированию (а я в этом слаб), чем к поиску красивых идей.
Когда Дмитрий выложил здесь свои мысли насчет 100! я догадывался, что для конкурса он прибережет что-нибудь "повеселее". Думал, неужели будет 1000!
Точно!
Не буду зарекаться, но пока у меня нет никакого желания участвовать в продолжении (как и большинство конкурсантов "сыт факториалами"). Кроме того, мои программы не приспособлены для таких "маниакальных" чисел. Это всё надо начинать с чистого листа.

[Nataly-Mak]

Эх, жаль, что я не участвую в форуме конкурса.
Обязательно высказала бы пожелание, чтобы в следующих конкурсах запретили вот такое безобразие

Цитата:

371 .92 Juan Miguel Ballesteros Frankfurt am Main, Hessen, Germany 21 Jan 2013 08:50
…………..
417 .48 Daniele Corallo Durmersheim, Baden-Wuerttemberg, Germany 23 Mar 2013 12:03

Нет, ну это же просто смешно! Что за участие --- нет даже одного балла!
Просто отметились (можно было взять известное решение для 20! из указанной здесь статьи и ввести его; вот, мол, и я участвовал в конкурсе). Только таблицу сделали безобразно длинной.
Я бы даже ввела наименьшее значение результата, разрешённое для ввода, 3 балла; остальным делать нечего на конкурсе

-- Сб апр 20, 2013 21:19:23 --

Vovka17 в сообщении #713252 писал(а):

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

Да-да, у меня аналогичная ситуация.

Цитата:

Когда Дмитрий выложил здесь свои мысли насчет 100! я догадывался, что для конкурса он прибережет что-нибудь "повеселее". Думал, неужели будет 1000!
Точно!

Ну, задача эта на любителей, о-ч-ч-ч-е-н-ь больших любителей

[dmd]

Число 1000! имеет 2568 десятичных знаков

? sizedigit(1000!)
%1 = 2568

Не такое уж большое это число, в отличие например от последнего известного простого Мерсенна

? sizedigit(2^57885161-1)
%2 = 17425170

[Nataly-Mak]

Последним функционалом в программе mertz был поиск решения от любой заданной начальной последовательности. Это супер-функция!
Ну, и тут очень хорошо стал работать "супер-пупер" алгоритм, о котором я писала чуть выше.
Сегодня, уже под занавес, нашла решение для 35! по этому алгоритму.
Сначала долго мучила 34!, ничего не нашла; решила попробовать для 35!
И тут удача улыбнулась
Вот это решение:

1,2,4,6,12,144,140,156,20160,120960,18869760,18849600,155,21700,311,171,22011,
3763881,355687428096000,126513546505547170185216000000,81676217700,
10333147966386144929666651337523200000000

Решение основано на раложении:

$35! = 81676217700 \cdot (17!)^2$
$81676217700=3763881 \cdot 21700$

Сначала ищется число 21700, а затем число 3763881; потом эти числа перемножаются и решение готово.
Поиск начинается от последовательностей, представляющих 17!, без последнего члена.
Это результат второго этапа, выданный программой mertz:

found 3 solutions for 3763881 in 17 steps
1,2,4,6,12,144,140,156,20160,120960,18869760,18849600,155,21700,311,171,22011,3763881
1,2,4,6,12,144,140,156,20160,3144960,18869760,18849600,155,21700,311,171,22011,3763881
1,2,4,6,12,144,140,156,936,20160,18869760,18849600,155,21700,311,171,22011,3763881

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

Для полноты картины показываю и результат первого этапа - поиск числа 21700:

found 6 solutions for 21700 in 13 steps
1,2,4,6,12,144,140,156,20160,120960,18869760,18849600,155,21700
1,2,4,6,12,144,140,156,20160,120960,18869760,18849600,21840,21700
1,2,4,6,12,144,140,156,20160,3144960,18869760,18849600,155,21700
1,2,4,6,12,144,140,156,20160,3144960,18869760,18849600,21840,21700
1,2,4,6,12,144,140,156,936,20160,18869760,18849600,155,21700
1,2,4,6,12,144,140,156,936,20160,18869760,18849600,21840,21700

Эти последовательности являются начальными для второго этапа - поиска числа 3763881.

[Gerbicz]

The contest is over!

Rank Score Contestant Last Improvement
1 1.000 Helge Keller Karlsruhe, Germany 20 Apr 2013 16:13
2 1.000 Jarek Wroblewski Wroclaw, Poland 20 Apr 2013 16:30
3 1.000 Robert Gerbicz Halasztelek, Hungary 20 Apr 2013 16:52

In spoj I would set these problems to the tutorial section, ideal for small kids, up to 12 years. Kamenetsky would you throw away some dirty T-shirts like Al ?

I would set up much harder number theory or algebraic topological problem, but in this case who would compete? Nataly with her own Basic code?

-- 20.04.2013, 22:11 --

dmd:
Number 1000! has 2568 decimals

My wild guess is that you have designed this problem for Nataly. The UBasic (that version I have on my computer) can handle factorials up to n=1014.

[dimkadimon]

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

The contest is over!

Rank Score Contestant Last Improvement
1 1.000 Helge Keller Karlsruhe, Germany 20 Apr 2013 16:13
2 1.000 Jarek Wroblewski Wroclaw, Poland 20 Apr 2013 16:30
3 1.000 Robert Gerbicz Halasztelek, Hungary 20 Apr 2013 16:52

In spoj I would set these problems to the tutorial section, ideal for small kids, up to 12 years. Kamenetsky would you throw away some dirty T-shirts like Al ?

The contest still has 5 weeks to go and its not over. If you want to setup your own contest feel free approach Al. The prize is $25AU which you can use to buy yourself a dirty t-shirt. If you have nothing constructive to say than don't say anything.

[dimkadimon]

Ну, кто будет первым Россиянином который нашел 1000!