2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 66, 67, 68, 69, 70, 71, 72 ... 88  След.
 
 Re: Factorials
Сообщение25.04.2013, 13:44 
Аватара пользователя


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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #715364 писал(а):
Но с другой стороны...

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

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

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


19/12/10
1546
Nataly-Mak в сообщении #715355 писал(а):
А вот здесь вопрос спорный.
Дело в том, что Yurii Sigolaev вводил, как я понимаю, только оптимальные решения.
Я следила за его результатами во время конкурса, у него ни разу не было дробных значений результатов, только целые.
Коли так, отзываю свои слова о 147 месте.
Это, действительно, не имеет никакого значения.
А 17 оптимальных решений, действительно, хороший результат.

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

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


22/03/08

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

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

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

Для сравнения, 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 и выполнить умножение.

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

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

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


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

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


01/06/12
1016
Adelaide, Australia
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

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


19/12/10
1546
Код:
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.
были найдены постфактум.
И, скорее всего, подгонкой под уже известные решения.

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


22/03/08

7154
Саратов
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? :D
А я буду информировать об успехах Pavlovsky.
Интересная тема получится :D

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


19/12/10
1546
Nataly-Mak в сообщении #715603 писал(а):
Для 27! я не вижу у него решения; не нашёл?

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

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

Nataly-Mak в сообщении #715620 писал(а):
Вы будете нас каждый день информировать об успехах Gerbicz? :D
А я буду информировать об успехах Pavlovsky.
Интересная тема получится :D

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

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


21/02/10
1594
Екатеринбург
Gerbicz спринтер, думаю дня через два задача ему надоест. Жаль, что Jarek Wroblewski похоже выбыл из борьбы за первое место.
Цитата:
I am most likely becoming a spectator.


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

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #715634 писал(а):
Так что основная борьба развернется за третье место. За которое даже Bragging Rights не положено.

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

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


21/02/10
1594
Екатеринбург
Решил для построения решения 1000! воспользоваться программой Эда. И тут же напоролся на ограничение. Программа не строит последовательности длинее 22 операций.

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


22/03/08

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

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 14:38 


02/11/12
141
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.

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


22/03/08

7154
Саратов
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


 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 66, 67, 68, 69, 70, 71, 72 ... 88  След.

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



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

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


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

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