Al Zimmermann - Sums and Products

[Herbert Kociemba]

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}

[Pavlovsky]

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.

[dimkadimon]

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...

[Herbert Kociemba]

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.

[Pavlovsky]

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 до максимального числа распределены равномерно!

[dimkadimon]

Herbert congratulations on reaching your 30.0!



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

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

[Herbert Kociemba]

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.

[MaksSok.95]

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}
а это уже не линейка Голомба.

[Pavlovsky]

MaksSok.95 в сообщении #1081857 писал(а):

Из каких соображений выбиралось число 31

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

Глава 5.7

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

[MaksSok.95]

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}

[whitefox]

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

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

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

[Pavlovsky]

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

можно выполнять с произвольной линейкой Голомба

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

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

[whitefox]

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

[Pavlovsky]

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

что преобразования можно проводить по бесконечному числу модулей.

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

[Herbert Kociemba]

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.