Factorials

[Pavlovsky]

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

[Nataly-Mak]

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

Но с другой стороны...

Я сказала только "с одной стороны", а именно: 147-ое место - это не показатель.

То, что он хвастун во вселенском масштабе, мне хорошо известно.

[whitefox]

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

А вот здесь вопрос спорный.
Дело в том, что Yurii Sigolaev вводил, как я понимаю, только оптимальные решения.
Я следила за его результатами во время конкурса, у него ни разу не было дробных значений результатов, только целые.

Коли так, отзываю свои слова о 147 месте.
Это, действительно, не имеет никакого значения.
А 17 оптимальных решений, действительно, хороший результат.

Последнюю строку моего предыдущего поста читать так:
"Легко быть гением постфактум".

[Nataly-Mak]

Любопытно:
Yurii Sigolaev нашёл оптимальные решения (судя по вводу их на конкурс)

23! - 3 апреля
24! - 3 апреля
26! - 6 апреля
28! - 10 апреля
29! - 10 апреля
30! - 9 апреля

Данные по решениям, которые были найдены в первые 48 часов, на сайте не приводятся (сюда вошло и решение для 25!).
Для 27! я не вижу у него решения; не нашёл? Может, забыл ввести? (как известно, все гении очень рассеянные люди ).
Для N>30 решений тоже нет. Это не успел: командировка помешала (как пояснил нам wanderers = Yurii Sigolaev).
Таким образом, его супер алгоритм заработал в полную силу только в апреле. Сложный алгоритм! Долго и сочинялась по нему программа

Для сравнения, Pavlovsky нашёл оптимальные решения:

23! - 26 марта
24! - 9 марта
26! - 20 марта
27! - 10 марта
29! - 14 апреля
32! - 7 апреля
34! - 11 апреля

-- Пт апр 26, 2013 07:34:18 --

А такой метод не пойдёт в поиске решения для 1000!

Пример для 51!

$51! = 25! \cdot 26! \cdot 247959266474052$
$247959266474052 = 2^2 \cdot 3^3 \cdot 7^2 \cdot 17 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47$

Начинаем от оптимального решения для 25!

1,2,4,6,24,28,576,600,594,16800,9979200,16796,552,282172800,155759385600,
99584432640000,25!,26,26!,25!*26!

Имеем 19 шагов. Осталось составить число 247959266474052 и выполнить умножение.

Сколько тут получится шагов

Нет, наверное, не получатся хорошие результаты на этом пути.

[Pavlovsky]

Запустил свою процедуру оптимизации последовательности для 1000! За ночь нашла улучшение на одну операцию.
Блин, не этого я ожидал. Полагал, что она будет сбрасывать сразу по несколько десятков операций. Да и рабоать будет быстрее. Посмотрим что будет дальше. Главное, что процедура работает!

[dimkadimon]

Timeline of how optimals were found

N | Date | First finder | Number of finders
27: 23 Jan 2013 01:29 Tomas Rokicki 20
23: 24 Jan 2013 00:35 Hermann Jurksch 27
24: 24 Jan 2013 00:35 Hermann Jurksch 37
28: 24 Jan 2013 00:37 Hermann Jurksch 15
29: 24 Jan 2013 09:33 Tomas Rokicki 30
32: 24 Jan 2013 21:06 Valentin Dobrota 19
30: 25 Jan 2013 10:59 Hermann Jurksch 16
26: 27 Jan 2013 00:10 Martin Piotte 21
35: 29 Jan 2013 16:24 Hermann Jurksch 12
37: 01 Feb 2013 21:23 Valentin Dobrota 14
34: 08 Feb 2013 22:30 Hermann Jurksch 10
33: 20 Feb 2013 06:31 Hermann Jurksch 6
31: 21 Feb 2013 04:05 Tomas Rokicki 9
36: 22 Feb 2013 03:36 Tomas Rokicki 6

[whitefox]

1    1.000    Robert Gerbicz    Halasztelek, Hungary    25 Apr 2013 20:42
12    .265    Raw Score = 1000    Adelaide, Australia    20 Apr 2013 16:00

Без комментариев.

-- 26 апр 2013, 07:55 --

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

Для N>30 решений тоже нет. Это не успел: командировка помешала (как пояснил нам wanderers = Yurii Sigolaev).

Выходит я угадал, и решения

sigolaevy писал(а):

My method allows to find the solution for 31!, 32!, 33! and 36! on 14 cores for
half an hour.

были найдены постфактум.
И, скорее всего, подгонкой под уже известные решения.

[Nataly-Mak]

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

1    1.000    Robert Gerbicz    Halasztelek, Hungary    25 Apr 2013 20:42
12    .265    Raw Score = 1000    Adelaide, Australia    20 Apr 2013 16:00

Без комментариев.

Угу...
Я это тоже видела; думаю, что и все участники темы видели, кто интересуется этим конкурсом.
Вы будете нас каждый день информировать об успехах Gerbicz?
А я буду информировать об успехах Pavlovsky.
Интересная тема получится

[whitefox]

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

Для 27! я не вижу у него решения; не нашёл?

Не нашёл. От N=13 до N=30, пропуская N=27, ровно 17 решений.

-- 26 апр 2013, 08:15 --

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

Вы будете нас каждый день информировать об успехах Gerbicz?
А я буду информировать об успехах Pavlovsky.
Интересная тема получится

Ладно, об успехах Gerbicz больше информировать не буду.
Но мне интересно -- будет ли преодолён рубеж в 250 шагов?
И если да, то как быстро?

[Pavlovsky]

Gerbicz спринтер, думаю дня через два задача ему надоест. Жаль, что Jarek Wroblewski похоже выбыл из борьбы за первое место.

Цитата:

I am most likely becoming a spectator.

Так что основная борьба развернется за третье место. За которое даже Bragging Rights не положено.

[dimkadimon]

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

Так что основная борьба развернется за третье место. За которое даже Bragging Rights не положено.

Я вручаю bragging rights на все места, чем выше место тем больше :)

[Pavlovsky]

Решил для построения решения 1000! воспользоваться программой Эда. И тут же напоролся на ограничение. Программа не строит последовательности длинее 22 операций.

[Nataly-Mak]

Так в основном конкурсе и не требовалось строить последовательности длиннее 22 шагов.
Эд ведь, наверное, не адаптировал свои программы для 1000!

[mertz]

No, I have not adapted it for 1000! I have doubled its speed again. I will release in a day or two. I also added the chain search suggested by Tom Rikicki. I can find solutions for 20! in about 30 minutes. 21! and 22! will have to use the 128-bit search but should run about 2 hours on my machine.

I think you need a different type of program for 1000! I do not understand the addition chains. Building it in pieces and getting the primes needed.

(Оффтоп)

The Gerbicz is doing well. He is like a blind man that can hear really well.

[Nataly-Mak]

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

I do not understand the addition chains.

Аддитивные цепочки - это просто.

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

Я рассуждаю на основе этого примера из Википедии.
Дана аддитивная последовательность:

v = (1,2,3,6,12,24,30,31)

Далее:

Цитата:

Addition chains can be used for addition-chain exponentiation:
so for example we only need 7 multiplications to calculate $5^{31}$:

5^2 = 5^1 × 5^1
5^3 = 5^2 × 5^1
5^6 = 5^3 × 5^3
5^12 = 5^6 × 5^6
5^24 = 5^12 × 5^12
5^30 = 5^24 × 5^6
5^31 = 5^30 × 5^1