Al Zimmerman - Delacorte Numbers

[jcmeyrignac]

To thank you for the fast scoring system, I'll share a small trick:

there are several mathematical patterns to generate good grids without any computation.

[sevir]

jcmeyrignac в сообщении #937719 писал(а):

To thank you for the fast scoring system, I'll share a small trick:

there are several mathematical patterns to generate good grids without any computation.

Наверное, благодарность должна заключаться в конкретных формулах, а не в туманных намеках.

[Nataly-Mak]

jcmeyrignac в сообщении #937719 писал(а):

there are several mathematical patterns to generate good grids without any computation.

Вот это уже ИНТЕРЕСНО!

Сразу вспомнился конкурс по раскраскам. Там были замечательные математические модели, которые давали раскраски-шедевры. Позволю себе показать одну из них:



Кстати, эта великолепная раскраска помещена на титульном листе моей книги, написанной по материалам того конкурса:
Monochromatic Squares или Математическая раскраска
http://yadi.sk/d/SIXEr8l4CV9fY

Это было очень интересно - искать раскраски по математическим моделям. Моделей было много разных, были даже латинские квадраты, столь близкие мне.

В задаче о числах Делакорта тоже должны быть такие математические модели. Я об этом интуитивно догадывалась.
Посмотрите на это решение:



В решении стёрты числа нейтральной группы (белая цветовая зона).

Хорошо видно, что три цветовые зоны получаются связанные.
Не удалось мне тут удалить аппендикс в зелёной зоне.
Это, конечно, решение весьма далёкое от оптимального. Однако уже в нём вполне себе гармония
Теперь задача сводится к оптимальной расстановке чисел в каждой цветовой зоне. А это уже всё-таки не все перестановки, а перестановки чисел только внутри каждой цветовой зоны.

-- Сб ноя 29, 2014 13:20:08 --

sevir в сообщении #937725 писал(а):

Наверное, благодарность должна заключаться в конкретных формулах, а не в туманных намеках.

Может, вам ещё и ключ от квартиры, где деньги лежат?

[sevir]

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

sevir в сообщении #937725 писал(а):

Наверное, благодарность должна заключаться в конкретных формулах, а не в туманных намеках.

Может, вам ещё и ключ от квартиры, где деньги лежат?

Это Вы скажите whitefox'у, который выложил блестящий анализ задачи, а не отделался туманными намеками.

[Herbert Kociemba]

sevir в сообщении #937699 писал(а):

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

Herbert Kociemba в сообщении #934878 писал(а):

For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.

Strange I am getting quite good improvements with the new algorithm. In fact I reverted back to a simpler method, which I thought was rubbish. I guess before I was running it for 5 minutes and when it didn't give improvements I terminated it. But now with a 30-50 speed-up I get almost immediate improvements and it is encouraging me to continue using the method.

Herbert Kociemba хотел этим сказать, что очень хорошие результаты не помогают улучшить даже формулы whitefox'а. У меня подозрение, что он имеет доступ к кластеру, тем более, что он писал о возможности использования хорошего "железа".

I have no access to a cluster, I use a PC which is about 4 years old with a i7-CPU with 8 cores. What I wanted to say is that for 50x increase in speed the solution quality does almost not change for me. For example for N=27 and the maximum my score raised from 34385xxxx to 34386xxxx which is almost nothing - less than 0.0001 points.

[sevir]

Herbert Kociemba в сообщении #937763 писал(а):

I use a PC which is about 4 years old with a i7-CPU with 8 cores.

Ваш процессор поддерживает команды _rdrand?

[Nataly-Mak]

sevir в сообщении #937699 писал(а):

Herbert Kociemba хотел этим сказать, что очень хорошие результаты не помогают улучшить даже формулы whitefox'а. У меня подозрение, что он имеет доступ к кластеру, тем более, что он писал о возможности использования хорошего "железа".

Ба!! Так и хочется воскликнуть: "Маска! Я вас знаю!"

{у меня тоже подозрение }

Цитата:

Это не те конкурсы, в одном из которых поляк победил? Я ему письмо написал с обоснованием, что его результатов на обыкновенном компе невозможно достичь за разумное время (показал проколы в его описании алгоритма, которые с первого взгляда очень трудно заметить): вернее, можно, но с вероятностью, стремящейся к нулю. Он мне так и не ответил. Самое интересное, что все участники конкурсов Зиммермана яростно открещивались от применения кластеров в расчетах (это замечание к победителям относится). Как говорят, не пойман - не вор.

http://e-science.ru/comment/343690#comment-343690

[Herbert Kociemba]

sevir в сообщении #937795 писал(а):

Herbert Kociemba в сообщении #937763 писал(а):

I use a PC which is about 4 years old with a i7-CPU with 8 cores.

Ваш процессор поддерживает команды _rdrand?

I really do not know, I never heard about such a feature. And I already bought the machine in December 2008, so it is almost 6 years old, not 4 years.

[jcmeyrignac]

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

No, the pattern are different.
Focus on circles. Edit: there are 5 circles, than can be subdivided.

-- 29.11.2014, 17:15 --

Herbert Kociemba в сообщении #937763 писал(а):

I have no access to a cluster, I use a PC which is about 4 years old with a i7-CPU with 8 cores. What I wanted to say is that for 50x increase in speed the solution quality does almost not change for me. For example for N=27 and the maximum my score raised from 34385xxxx to 34386xxxx which is almost nothing - less than 0.0001 points.

You have a faster computer than mine !
With my quad-core, I improved all our small max grids significantly. This is where you can save a lot of points.

[sevir]

Herbert Kociemba в сообщении #937817 писал(а):

sevir в сообщении #937795 писал(а):

Herbert Kociemba в сообщении #937763 писал(а):

I use a PC which is about 4 years old with a i7-CPU with 8 cores.

Ваш процессор поддерживает команды _rdrand?

I really do not know, I never heard about such a feature. And I already bought the machine in December 2008, so it is almost 6 years old, not 4 years.

Эти команды используются интеловским транслятором в случае поддержки процессором генерации случайных чисел: позволяют получать быстро качественные последовательности случайных чисел вплоть до int64.

[Nataly-Mak]

jcmeyrignac в сообщении #937841 писал(а):

No, the pattern are different.
Focus on circles. Edit: there are 5 circles, than can be subdivided.

На кругах? Ничего не знаю о кругах
Ну, могу предположить 3 круга: жёлтый, белый, зелёный. Только это мало похоже на круги.

[Yadryara]

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

Посмотрите на это решение:



В решении стёрты числа нейтральной группы (белая цветовая зона).

Хорошо видно, что три цветовые зоны получаются связанные.

Есть очень важная, но не отмеченная зона в составе салатовой.

Есть гипотеза, что 28 простых чисел (1; 149 — 283) для достижения максимума должны стоять максимально плотно в самом центре.

[Nataly-Mak]

Yadryara в сообщении #937870 писал(а):

Есть очень важная, но не отмеченная зона в составе салатовой.

Есть гипотеза, что 28 простых чисел (1; 149 — 283) для достижения максимума должны стоять максимально плотно в самом центре.

Четвёртый круг?
А где пятый?

[Scryer]

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

(Quoting someone else:)

Цитата:

Это не те конкурсы, в одном из которых поляк победил? Я ему письмо написал с обоснованием, что его результатов на обыкновенном компе невозможно достичь за разумное время (показал проколы в его описании алгоритма, которые с первого взгляда очень трудно заметить): вернее, можно, но с вероятностью, стремящейся к нулю. Он мне так и не ответил. Самое интересное, что все участники конкурсов Зиммермана яростно открещивались от применения кластеров в расчетах (это замечание к победителям относится). Как говорят, не пойман - не вор.

http://e-science.ru/comment/343690#comment-343690

I have not seen anyone complain about others running multiple cores or large clusters of computers, and there is nothing in the rules against it. There has been open discussion of using CUDA and OpenCL, though so far I have seen no claim that someone has gotten better performance using them. This Delacorte problem may benefit from a CUDA approach because of the lower than usual amount of data that needs to be transferred. A survey was posted to the Yahoo website that asked how many cores were being used, and the last time I checked one participant reported using a large number, which would be in the GPU range.

I claim the "яростно открещивались" part is wrong. I for one do not "vehemently repudiate" using multiple cores, and I know of no participant who does. Solutions are where you find them.

[Pavlovsky]

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

Четвёртый круг?
А где пятый?

Все эти круги очень точно описываются весовой функцией

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

Будем называть весом числа k:
$\sum\limits_{i \ne k}{(gcd(i,k)-1)}$

Кстати если весовую функцию немного изменить, то получится

$$\Phi(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

из второго пакета формул от whitefox

То есть весовая функция не эвристическая абстракция, а имеет конкретное применение.

Весовая функция для N=4
До модификации

(Оффтоп)

12 23
6 17
8 17
16 17
15 16
10 15
4 13
14 13
3 8
5 8
9 8
2 7
7 6
11 0
13 0

После модификации

(Оффтоп)

12 30
8 24
16 24
6 22
15 22
10 20
14 20
4 16
5 12
7 12
3 10
9 10
2 8
11 0
13 0