Al Zimmerman - Delacorte Numbers

[Pavlovsky]

Цитата:

Everyone,
I know that many of you are anxious to see AZsPCs back on the air. So here's a report on where things stand at the moment. There is good news and there is bad and, on the whole, I think they pretty much cancel each other out.
I was able to start the process of setting up an account with an external hosting service sooner than I had expected. That's the good news. The bad news is that the hosting service I chose (one which has been in business for a couple of decades) is apparently dysfunctional. I didn't think it would take upwards of a week to transfer a couple of domain names from one registrar to another, or that repeated manual tweaking of the process would be necessary, but that's what's happening.
I'm optimistic that, once the domain names have been transferred, the remaining steps (opening a hosting account and uploading the software and database) will proceed apace. But, then again, I once thought you could transfer a domain name in 72 hours.

Al
---In [e-mail], <alzimmerma@...> wrote :

[dmd]

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

dmd в сообщении #935938 писал(а):

Формула для $\Delta D$ заработала

Ну и как? Работает быстро?

Таки да! Формула whitefox для $\Delta D$ даёт увеличение скорости в 30-50 раз.

[sevir]

dmd в сообщении #936769 писал(а):

Формула whitefox для $\Delta D$ даёт увеличение скорости в 30-50 раз.

По сравнению с каким алгоритмом?

[whitefox]

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

Это утверждение можно немного обобщить.
Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, такие что $\left\lfloor\frac{N^2}{p_1}\right\rfloor=\left\lfloor\frac{N^2}{p_2}\right\rfloor$ Тогда в максимальном решении, $D_{p_1} \le D_{p_2}$. Где $D_{p_1} (D_{p_2})$ сумма квадратов расстояний между числами кратными $p_1 (p_2)$

Возможно, можно ещё обобщить.
Гипотеза: Пусть $|M_a|=|M_b|$ и пусть $\varphi(a)<\varphi(b)$, тогда условие $D_a\leqslant D_b$ является необходимым для максимума, а условие $D_a\geqslant D_b$ является необходимым для минимума.

$|M_k|$, как обычно, означает мощность множества $M_k$.

[dmd]

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

По сравнению с каким алгоритмом?

с моим для полного $D$

[sevir]

dmd в сообщении #936886 писал(а):

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

По сравнению с каким алгоритмом?

с моим для полного $D$

И сколько операций требовалось на ваш алгоритм?

-- 27.11.2014, 17:37 --

Pavlovsky,
А обсуждался вопрос переноса сроков конкурса?

[Pavlovsky]

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

Гипотеза: Пусть $|M_a|=|M_b|$ и пусть $\varphi(a)<\varphi(b)$, тогда условие $D_a\leqslant D_b$ является необходимым для максимума, а условие $D_a\geqslant D_b$ является необходимым для минимума.

Параметры моего максимального решения для N=6. Оно чуток не дотягивает до рекорда. Первое число k, второе $D_k$, третье число $\varphi(k)$.
$|M_k|=4$
8 151 * 4 = 604
9 152 * 6 = 912
$|M_k|=3$
10 80 * 4 = 320
11 46 * 10 = 460
12 92 * 4 = 368
$|M_k|=2$
13 13 * 12 = 156
14 34 * 6 = 204
15 41 * 8 = 328
16 34 * 8 = 272
17 18 * 16 = 288
18 50 * 6 = 300

Как видите гипотеза требует существенных доработок.

-- Чт ноя 27, 2014 20:53:03 --

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

А обсуждался вопрос переноса сроков конкурса?

Насколько я разбираюсь в английском языке - нет.
Впрочем есть люди, которые считают что три месяца это очень много. Я множеству этих людей не принадлежу.

[dmd]

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

И сколько операций требовалось на ваш алгоритм?

У меня получалось около 7500 парных перестановок в секунду на одном ядре. У лидеров оно измеряется в миллионах в секунду.

[Nataly-Mak]

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

Впрочем есть люди, которые считают что три месяца это очень много.

Это вы не на меня намекаете?
В точку!
Особенно для такого конкурса, как числа Делакорта. Для него хватило бы с лихвой одного месяца

Начну с вот этого сообщения:

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

А у меня идеи кончились. Похоже что для следующего прогреса надо оптимизировать код (не знаю как) и гонять компьютер сутками чтобы увеличить бал хотя бы на 0.001. Это мне не хочется делать и поэтому задача надоела. Оставляю её пока не появятся хорошие идеи...

Очень интересная задача что-то весьма быстро надоела.
Мои задачи по пандиагональным квадратам не надоели мне за несколько лет!
Сравнивайте, сравнивайте! Был уже проведён один конкурс по пандиагональным квадратам из простых чисел (кстати, провёл его Al Zimmermann). Сейчас идёт второй конкурс - по пандиагональным квадратам из последовательных простых чисел
http://primesmagicgames.altervista.org/wp/competitions/
Я дала на этот конкурс три месяца, потому что задачи конкурса очень сложные. Я это прекрасно знаю, ибо сама вот уже два месяца бьюсь над решением этих конкурсных задач (n=7, n=8).
На конкурсе пока не выложили ни одного решения!

Далее: в первые же дни конкурса я спросила в дискуссионной группе, как это все так быстро умудрились решить задачу почти по максимуму. Ответил один участник: у него алгоритм имитация отжига работал примерно два часа. Класс!
То есть берём самый простой алгоритм, пишем программу и на кластере (ну, на худой конец на 40 ядрах) за 2 часа получаем решения на 24,99+
Что дальше делать? Гонять сутками машину в поисках ещё 0.001?
Ах да - теоретизировать. Как быстрее вычислить изменение числа Делакорта при парной, тройной и т.д. перестановках. А на... черта всё это нужно? Я, к примеру, вообще ничего не вычисляла, всё за меня делала программа приёма решений.

Ну, кто любит теоретизировать, флаг им в руки. Я не люблю. Я практик. Вот построить пандиагональный квадрат 8-го порядка из последовательных простых чисел я очень хочу. И для этого мной придуман уже не один алгоритм и не одна эвристика. Небольшой прорыв есть (вряд ли кто-нибудь следит за моими сообщениями на форуме, где проходит конкурс; а зря).

(Оффтоп)

Бесконечно рада, что сначала сайт "упал", что привело к вынужденной остановке моих занятий, так как я все решения улучшала в визуализаторе.
Думала, что это будет просто перерыв. И ещё больше рада, что этот перерыв будет не временным.
А причина в том, что Ал забанил меня в его дискуссионной группе.
Не появились два мои последние сообщения. Я недоумевала - почему не появились. А сегодня вошла в дискуссионную группу и... Yahoo сообщает мне, что два мои сообщения не были утверждены.
Ага! Ну, теперь стало понятно. Не пропустил Ал.
А сообщения-то были вполне нейтральные, никакого негатива не содержали.
Вот первое:

Цитата:

Al
I must say that the visualizer made wonderful.
I love the transformation of solutions to the canonical form, when I see well what numbers should must be moved.
Thank you very much!

А во втором я предлагала выложить визуализатор для оффлайн использования.
И в чём тут криминал?
Весьма раздосадованная, пишу Алу письмо с просьбой объяснить, как это понимать?
Ответ был таким:

Цитата:

All messages must be approved by me. Sometimes I choose not to approve a message if I feel it does not make a positive contribution to the AZsPCs experience.

Вот так!
Ну и начхать я хотела на его конкурс О чём ему и сообщила.

Ах да, а причина блокирования сообщений, вероятно, в предыдущей моей критике конкурса.
Ну, что думала, то и сказала. Лицемерить не обучена.

Всем удачи! В теории и в практике

Я вполне довольна своим результатом: 19 баллов с хвостиком при ручной работе, без всяких программ. Потенциал ещё остался, но теперь уже, слава Богу, больше не буду играть с визуализатором.

-- Чт ноя 27, 2014 21:54:46 --

(Оффтоп)

Кстати,
Pavlovsky
вы назвали решение Макса для $n=4$ (наименьший пандиагональный квадрат из последовательных простых чисел) великим результатом.
Да. Согласна.

Ничто не мешает вам найти второй великий результат - наименьший пандиагональный квадрат 5-го порядка из последовательных простых чисел
(пока нет ни одного такого квадрата)

И ещё: тема-то "Дьявольские магические квадраты из простых чисел" всё просматривается и просматривается. Кто же её смотрит-то так активно?
Да, актуальная тема, и долго ещё будет актуальна, ибо нерешённые проблемы остались.
Я могла бы многое в эту тему добавить из своих последних исследований, но... не буду. Читайте мои сообщения на сайте S. Tognon.

[sevir]

Pavlovsky

(Оффтоп)

Не обращайте внимания: помните басню про лису и виноград - это тот самый случай.

[Nataly-Mak]

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

Pavlovsky
Не обращайте внимания: помните басню про лису и виноград - это тот самый случай.

Хм...
Вы - лиса...
Вот здесь
http://primesmagicgames.altervista.org/wp/competitions/
виноград.
Не откушаете ли?
Ну, хоть один квадратик любой

Кстати, а причём здесь Pavlovsky? Это не он задачу для конкурса AZ придумал.
Задача тупая совсем не потому, что я не умею писать программу для алгоритма отжига.
Виноград зелен не потому, что я не могу его достать. Он просто ЗЕЛЕН, сам по себе.
Так что, и басня тут совсем ни при чём.

[Yadryara]

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

Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, такие что $\left\lfloor\frac{N^2}{p_1}\right\rfloor=\left\lfloor\frac{N^2}{p_2}\right\rfloor$ Тогда в максимальном решении, $D_{p_1} \le D_{p_2}$. Где $D_{p_1} (D_{p_2})$ сумма квадратов расстояний между числами кратными $p_1 (p_2)$

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

$|M_k|=2$
13 13 * 12 = 156
[...]
17 18 * 16 = 288

Правильно ли я понимаю, что приведён единственный пример с такой парой простых? Есть ли ещё примеры?

[dimkadimon]

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

Начну с вот этого сообщения:
dimkadimon в сообщении #923999

писал(а):
А у меня идеи кончились. Похоже что для следующего прогреса надо оптимизировать код (не знаю как) и гонять компьютер сутками чтобы увеличить бал хотя бы на 0.001. Это мне не хочется делать и поэтому задача надоела. Оставляю её пока не появятся хорошие идеи...
Очень интересная задача что-то весьма быстро надоела.
Мои задачи по пандиагональным квадратам не надоели мне за несколько лет!

Это было давно. С тех пор я сделал прогрес и снова взялся за задачу. Потом она мне опять надоела и я переключился на другие задачи. А потом whitefox показал свою гениальную формулу и я снова взялся за задачу.

Теперь я стал решать вашу задачу (чтобы вы не чусвтвовали что она никому не интересна). Задача интересная, но очень сложная. Может только несколько человек найдут решения, а может даже никто. Пока что я нашел 7х7 с 4 ошибками и S=797, простые от 7 до 239:

(Оффтоп)

131 151 79 109 73 223 31
227 61 83 157 229 17 23
71 103 233 19 -1* 181 191
67 101 47 229* 59 197 97
37 137 179 127 11 107 199
53 131* 163 7 233* 43 167
211 113 13 149 193 29 89

[Pavlovsky]

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

Правильно ли я понимаю, что приведён единственный пример с такой парой простых? Есть ли ещё примеры?

С ростом N таких примеров становится очень много.
Например
для N=7
$|M_k|=2$ p=17,19,23
для N=8
$|M_k|=2$ p=23,29,31
$|M_k|=3$ p=17,19
для N=9
$|M_k|=2$ p=29,31,37
$|M_k|=4$ p=17,19

[sevir]

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

Хорошо, вот мои лучшие результаты для N<=10, надеюсь они другим помогут:
...
N=10, MAX=593249

А Вы не могли бы привести некоторые решения для $N > 10$: я заметил особенность своего алгоритма - чем больше $N$, тем меньше отличается мое решение, полученное практически мгновенно от вашего. Например, для $N = 10$ мне машина сразу выдала решение $592831$. Но $592831 / 593249 = 0,9993$. Это я к тому, что стоит ли мне дальше "огород городить".