2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 10:13 


25/08/12
89
dimkadimon в сообщении #1080827 писал(а):
Yep I thought this was the case, but couldn't find an easy way to generate them all. I tried using the sub-optimal rulers generated by the fortran programs, but it wasn't enough.



No, it is very simple. You only need one single solution to generate all others. Take for example {0,1,3,8,12,18}. With the operations rotate and multiply you get all other solutions. For p=5 of course all operations mod 31 in the projective case

1. rotateleft:

{0,1,3,8,12,18} -> rotate-> {1,3,8,12,18,0} -> subtract 1 -> {0,2,7,11,17,30}

2. multiply with any number coprime to the modulus, since gcd(2,31)=1 for example with 2:

{0,1,3,8,12,18} -> *2 -> {0,2,6,16,24,5} -> resort -> {0,2,5,6,16,24}

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 10:29 
Аватара пользователя


21/02/10
1594
Екатеринбург
Pavlovsky в сообщении #1080820 писал(а):
Yep I thought this was the case, but couldn't find an easy way to generate them all.


Для affine plane construction в статье A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS
http://eeme.ucd.ie/~kdrakaka/work/publi ... Rulers.pdf

Есть теорема 8, с ее помощью можно формировать много различных линеек. Наверно нечто подобное есть и для projective plane construction.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 10:37 
Аватара пользователя


01/06/12
755
Adelaide, Australia
Herbert Kociemba в сообщении #1080832 писал(а):
No, it is very simple. You only need one single solution to generate all others. Take for example {0,1,3,8,12,18}. With the operations rotate and multiply you get all other solutions. For p=5 of course all operations mod 31 in the projective case


Very nice! I wonder if the leaders tried doing this with all the sub-optimal rulers as well? Sub-optimal rulers + offset to get multiplications working may give you better results...

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 10:46 


25/08/12
89
dimkadimon в сообщении #1080838 писал(а):
Very nice! I wonder if the leaders tried doing this with all the sub-optimal rulers as well? Sub-optimal rulers + offset to get multiplications working may give you better results...


I do not know if I understand you correctly but if I already have found a solution of length S I of course try all rulers {0,.....,X} + offset with X<S and offset < S-X.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 15:21 
Аватара пользователя


21/02/10
1594
Екатеринбург
Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers
by Apostolos Dimitromanolakis
http://www.cs.utoronto.ca/~apostol/golomb/main.pdf
(не путать с предыдущей статьей)

Теорема 3.2 (Линдстрем) (вольный пересказ).

В линейке Голомба остатки от деления чисел в последовательности на $m \ge 2$ распределены равномерно!

Теорема 3.5

В линейке Голомба числа на интервале от 0 до максимального числа распределены равномерно!

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение13.12.2015, 01:20 
Аватара пользователя


01/06/12
755
Adelaide, Australia
Herbert congratulations on reaching your 30.0!



Ухожу заниматься новой важной задачей - помогать Деду Морозу разносить подарки детям :)

https://www.kaggle.com/c/santas-stolen-sleigh

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение13.12.2015, 02:26 


25/08/12
89
dimkadimon в сообщении #1081734 писал(а):
Herbert congratulations on reaching your 30.0!

Thank you! It took me really a long time to put all the pieces together. Now where the program is working I estimate it takes only a few hours to recompute the "best" solution for all 30 problems.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение13.12.2015, 15:59 


13/12/15

91
Herbert Kociemba в сообщении #1080832 писал(а):
dimkadimon в сообщении #1080827 писал(а):
Yep I thought this was the case, but couldn't find an easy way to generate them all. I tried using the sub-optimal rulers generated by the fortran programs, but it wasn't enough.



No, it is very simple. You only need one single solution to generate all others. Take for example {0,1,3,8,12,18}. With the operations rotate and multiply you get all other solutions. For p=5 of course all operations mod 31 in the projective case

1. rotateleft:

{0,1,3,8,12,18} -> rotate-> {1,3,8,12,18,0} -> subtract 1 -> {0,2,7,11,17,30}

Из каких соображений выбиралось число 31?
Например, для операций по модулю 7 мы получим:
{0,3,5} -> rotate-> {3,5,0} -> subtract 3 -> {0,2,4}
а это уже не линейка Голомба.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение14.12.2015, 07:50 
Аватара пользователя


21/02/10
1594
Екатеринбург
MaksSok.95 в сообщении #1081857 писал(а):
Из каких соображений выбиралось число 31


http://www.cs.utoronto.ca/~apostol/golomb/main.pdf

Глава 5.7

31 выбрано так, чтобы все суммы в последовательности {0,1,3,8,12,18}, взятые по модулю 31 оставались различными.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение14.12.2015, 14:37 


13/12/15

91
Pavlovsky в сообщении #1082023 писал(а):
http://www.cs.utoronto.ca/~apostol/golomb/main.pdf

Глава 5.7

31 выбрано так, чтобы все суммы в последовательности {0,1,3,8,12,18}, взятые по модулю 31 оставались различными.


Спасибо: как я понял, это еще не гарантирует успех.Возьмем для наглядности более простой случай.
Программа conpp выдает решение {0,1,3} (для работы под виндами я заменил isort на qsort и durand на dlarnv). Решением для второго конкурса будет {1,4,6} и его мы получим с помощью умножений на 5, взятых по модулю 12: {0,1,3} -> mul 5-> {0,5,3} -> resort -> {0,3,5}

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение14.12.2015, 15:04 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Pavlovsky в сообщении #1082023 писал(а):
31 выбрано так, чтобы все суммы в последовательности {0,1,3,8,12,18}, взятые по модулю 31 оставались различными.

Вообще, преобразования Herbert Kociemba можно выполнять с произвольной линейкой Голомба. В частности, в качестве модуля годится все целые числа большие $2(a_n-a_1),$ но, как показывает приведённый выше пример, для некоторых линеек допустимы и меньшие модули.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение15.12.2015, 09:37 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1082071 писал(а):
можно выполнять с произвольной линейкой Голомба


Для N=101 взял самое лучшее решение известное на сегодняшний момент. Выполнил все возможные преобразования. Но по моим расчетам рекорд в конкурсе чуток лучше полученного мной результата. Значит нужно что то еще.

http://www.cs.utoronto.ca/~apostol/golomb/main.pdf
Интересно теорема 8, которую можно встроить в алгоритм affine plane construction, даст те же линейки, что и преобразования с готовой линейкой?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение15.12.2015, 16:02 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Pavlovsky в сообщении #1082275 писал(а):
Выполнил все возможные преобразования.

Позвольте усомниться, хотя бы потому, что преобразования можно проводить по бесконечному числу модулей.
whitefox в сообщении #1082071 писал(а):
в качестве модуля годится все целые числа большие $2(a_n-a_1).$

Pavlovsky в сообщении #1082275 писал(а):
Значит нужно что то еще.

Hint от Herbert Kociemba не пробовали?
Herbert Kociemba в сообщении #1080806 писал(а):
for example for N=1009 also p=1013 and p=1019 should be examined

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение15.12.2015, 16:14 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #1082354 писал(а):
что преобразования можно проводить по бесконечному числу модулей.


Делал только по минимально возможному модулю. Эксперименты с большими числами в качестве модуля, дали ощущение бесполезности этого занятия. Полученные решения получаются сильно хуже исходного. Шансы получить лучшее решение - минимальны.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение16.12.2015, 02:07 


25/08/12
89
Pavlovsky в сообщении #1082275 писал(а):
Для N=101 взял самое лучшее решение известное на сегодняшний момент. Выполнил все возможные преобразования. Но по моим расчетам рекорд в конкурсе чуток лучше полученного мной результата. Значит нужно что то еще.

Then there seems to be an error in your program logic. I can confirm that you get the best solution for N=101 directly from the projective plane construction with p=101.

whitefox в сообщении #1082071 писал(а):
в качестве модуля годится все целые числа большие $2(a_n-a_1),$

I do not believe that it is useful to take such large moduluses.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.

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



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

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


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

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