Цитата: evatutin от 12.05.2020, 18:49

Упражнение для глазастых: найдите среди квадратов два повторяющихся... Если без шуток и я нигде не ошибся, то повторяющихся квадратов быть не должно. Вверху посредине в жирной рамке — каноническая форма (CF) одного из ДЛК порядка 4. Тонкой линией обведен соответствующий ей главный класс из 2 нормализованных по первой строке ДЛК (вверху посредине). Каждый из представителей главного класса нормализованных ДЛК образует подкласс из одного нормализованного и оставшихся 4! - 1 = 24 - 1 = 23 денормализованных ДЛК (штриховые прямоугольники слева и справа). Итого, канонической форме соответствует класс изоморфизма из 48 ДЛК общего вида.

Картинка является поясняющей для групп числовых рядов вида:
1 — число главных классов [каких-то квадратов] порядка N;
2 — число нормализованных [каких-то квадратов] порядка N;
3 — число [каких-то квадратов] порядка N.

Цитата: kotenok2000 от 18.05.2020, 02:24

Не могу подключиться к   gerasim.boinc.ru

Цитата: evatutin от 28.05.2020, 14:54

Среди известных нам комбинаторных структур есть структуры типа 1:N, в которых есть центральный квадрат звезды, а есть N ее лучей — квадратов, ортогональных центральному. А нельзя ли подойти к целенаправленному поиску таких структур через CMS?

Гипотеза: Существует CMS, переводящая центральная квадрат сам в себя (по сути — автоморфизм специального вида), а i-й луч — в (i+1)-й (как обычно, с точностью до нормализации).

Для симметричных линий-2 верность гипотезы очевидна, а соответствующая CMS будет описывать симметрию центрального квадрата (обобщенные симметрии могут быть также описаны через CMS, что на мой взгляд очевидно). Для не симметричных линий-2 — не очевидно. Для структур типа 1:3, 1:4 и всех остальных подобных — тоже не очевидно. А раз так, будем проверять в проекте, в основной подпроект которого добавлена новая версия расчетного модуля 3.1.9 и WU'шки эксперимента exp722, в котором как раз и будет производиться поиск таких CMS.
Теперь немного потенциально неприятной информации для некоторых участников проекта... Выполненный недавно поиск CMS для циклов-4 был осуществлен без грида на моей машине примерно за 2 недели, что было очень долго и неудобно. Сейчас сделана попытка перенести его и аналогичные ему в проект. Проблема в том, что время поиска CMS может составлять от нескольких секунд, до нескольких десятков часов. Чекпоинтов нет, т.к. прервать громоздкий рекуррентный алгоритм и потом возобновить не так уж и просто (это в принципе можно, но заниматься этим ради нескольких сотен WU'шек наверное особого смысла не имеет, по крайней мере на данном, разведочном, этапе). Поэтому, если компьютер выключается, лучше наверное их сразу отменить, они посчитаются машинами, работающими в режиме 24/7. Прошу простить и понять... Кворум — 1, дедлайн — 2 недели. Проверяем гипотезу...

Цитата: evatutin от 28.05.2020, 14:58

Цитата: kotenok2000 от 18.05.2020, 02:24

Не могу подключиться к   gerasim.boinc.ru

В чем причина?

Цитата: evatutin от 28.05.2020, 20:00

Продемонстрируем сформулированное ранее утверждение про тривиальность наличия CMS для симметричных линий-3. Для примера возьмем горизонтально-симметричный квадрат B

B = 0123456789120436597820358146974697182035978654312034780912566941728503785063941253192708648562907341 (центр линии-3 и, по совместительству, центральный квадрат звезды 1:2)

и ортогональные ему концы линии-3 (они же лучи звезды 1:2)

A = 0123456789385729041647983615209286503174651072489356428190378304975261246918730510756329487931048652,
C = 0123456789385907241697483610255286943170601572984326908175348374205961496218035715076342987431598602.

CMS, отражающая лучи звезды друг в друга по кругу, приведена ниже (ее можно не искать полным перебором, а получить напрямую отталкиваясь от определения горизонтальной симметрии):

9 8 7 6 5 4 3 2 1 0
19 18 17 16 15 14 13 12 11 10
29 28 27 26 25 24 23 22 21 20
39 38 37 36 35 34 33 32 31 30
49 48 47 46 45 44 43 42 41 40
59 58 57 56 55 54 53 52 51 50
69 68 67 66 65 64 63 62 61 60
79 78 77 76 75 74 73 72 71 70
89 88 87 86 85 84 83 82 81 80
99 98 97 96 95 94 93 92 91 90

Ее структура циклов {2:50}. Как и следовало ожидать, приведенной выше CMS лучи отражаются друг в друга по кругу (A->C, C->A) с точностью до нормализации.

A' = CMS(A) = 9876543210614092758302516389744713056829398427015673091824651625794038503781964284923657012568401397,
Normalize(A') = 0123456789385907241697483610255286943170601572984326908175348374205961496218035715076342987431598602 = C.

Аналогично:

C' = CMS(C) = 9876543210614270958352016384790713496825348927510643571809621695024738753081269489243670512068951347,
Normalize(C') = 0123456789385729041647983615209286503174651072489356428190378304975261246918730510756329487931048652 = A.

Ну и в заключение, применение CMS к центральному квадрату звезды дает его же с точностью до нормализации:

B' = CMS(B) = 9876543210879563402179641853025302817964021345687965219087433058271496214936058746807291351437092658,
Normalize(B') = 0123456789120436597820358146974697182035978654312034780912566941728503785063941253192708648562907341 = B.

Для других обобщенных симметрий CMS будут другими, но общий принцип отражения лучей звезды по кругу будет неизменным.

Цитата: evatutin от 29.05.2020, 00:22

Поиск обобщенных симметрий через ESODLS CMS

Через ESODLS CMS (скорее всего) можно искать обобщенные симметрии. По крайней мере в текущем парастрофическом срезе (и срезе от транспонирования) и хочется надеяться, что все. Принцип поиска очень прост и эффективен: берется исследуемый квадрат A, к нему применяется одна из ESODLS CMS (номер X для определенности), в результате чего получается квадрат A', который затем нормализуется. Если в результате пары данных преобразований получается исходный квадрат A, будем говорить, что выбранная ESODLS CMS автоморфно отражает квадрат сам в себя (опять таки с точностью до нормализации). Или, другими словами, если

A = Normalize(ESODLS_CMS_X(A)),

то с высокой долей уверенности выбранная ESODLS CMS номер X соответствует одной из обобщенных симметрий, которые мы ранее с подачи whitefox'а описывали кодами в виде тройки (A,B,C) или пары (A,B) целых чисел (например, (4,31)-симметрия, в окрестности которой в свое время было найдено множество интересных редких комбинаторных структур).

Операции применения CMS к ДЛК и последующей нормализации являются достаточно простыми и быстрыми, на проверку одного квадрата на соответствие всем 15360 ESODLS CMS схемам порядка 10 у меня на Core i7 4770 уходит ~40 мс времени работы CPU в один поток (без особой оптимизации и распараллеливания, хотя тут при необходимости есть над чем поработать).

Пример 1:

0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 3 5 8 1 4 6 9 7
4 6 9 7 1 8 2 0 3 5
9 7 8 6 5 4 3 1 2 0
3 4 7 8 0 9 1 2 5 6
6 9 4 1 7 2 8 5 0 3
7 8 5 0 6 3 9 4 1 2
5 3 1 9 2 7 0 8 6 4
8 5 6 2 9 0 7 3 4 1

Горизонтальная симметрия, ей соответствует автоморфная ESODLS CMS 2 (и тривиальная ESODLS CMS 0, которая, как и (1,1)-симметрия, присуща всем квадратам без исключения).

Пример 2:

0 1 2 3 4 5 6 7 8 9
1 2 0 6 7 3 4 9 5 8
2 0 5 4 9 7 3 8 1 6
5 3 8 7 6 9 1 0 4 2
3 5 9 1 8 0 7 6 2 4
8 6 1 9 3 4 2 5 7 0
6 8 3 2 5 1 9 4 0 7
7 4 6 0 1 2 8 3 9 5
9 7 4 5 2 8 0 1 6 3
4 9 7 8 0 6 5 2 3 1

Вертикальная симметрия, автоморфная ESODLS CMS 14882

Пример 3:

0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 7 9 5 6 3
7 5 4 2 9 1 8 3 0 6
2 7 8 1 0 3 5 6 9 4
8 6 3 9 5 0 7 4 2 1
9 4 5 8 2 6 1 0 3 7
5 0 9 7 6 4 3 8 1 2
6 3 1 5 7 8 2 9 4 0
3 8 6 0 1 9 4 2 7 5
4 9 7 6 3 2 0 1 5 8

Какая-то обобщенная симметрия (ввиду того, что образуемая структура типа 1:10 включает в своем составе 6 КФ, а не 11), автоморфная ESODLS CMS 398.

PS. Скорее всего из любой автоморфной ESODLS CMS можно вытащить перестановки Px и Py для обобщенной симметрии... И наоборот: по паре заданных перестановок Px и Py можно построить CMS. Скорее всего данный способ описания обобщенных симметрий является эквивалентным использованному ранее, но в этом еще надо будет убедиться...

PPS. Возможно найдутся и другие CMS с интересными свойствами, не являющиеся ESODLS, но также автоморфно отражающие ДЛК. Точнее, они существуют и много для любого ДЛК без исключения, но вот будет ли от них какая-то польза... Открытый вопрос.

[upd]

Таким образом (через ESODLS CMS) можно извлекать не все обобщенные симметрии, а только описываемые M-перестановками. Извлекаемые таким образом симметрии уменьшают мощность главного класса ДЛК. Некоторые обобщенные симметрии (например, (27,27)) таким образом извлечь не получится и мощность главного класса они не уменьшают. Через ESOLS CMS можно извлечь все, правда самих ESOLS CMS будет весьма много и данный способ извлечения вряд ли будет эффективным...

Цитата: evatutin от 31.05.2020, 22:36

Косметические изменения в расчете: версия расчетника изменена на 3.2.0, а WU'шек — на exp723. По первым результатам, полученным в ходе расчетов, устраняю мелкие ляпы...

Цитата: evatutin от 01.06.2020, 14:03

Результаты поиска КФ ОДЛК в проекте Gerasim@Home за месяц:

ONCE (A):1 - 1752756, where:
1 CFs - 33160
2 CFs - 1719596 (+255122)

LINE3 (B):1 - 66053, where:
2 CFs - 18735
3 CFs - 47318 (+1168)

LINE3 (B):2 - 42394, 41:1, where:
2 CFs - 18735
3 CFs - 23659 (+584)

LINE4 (C):1 - 118, where:
2 CFs - 4
4 CFs - 114 (+2)

LINE4 (C):2 - 118, where:
2 CFs - 4
4 CFs - 114 (+2)

LINE5 (D):1 - 17, where:
3 CFs - 17

LINE5 (D):2 - 34, where:
3 CFs - 34

LOOP4 (E):2 - 2240, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 636

1TO3 (F):1 - 348, where:
4 CFs - 348 (+9)

1TO3 (F):3 - 116, where:
4 CFs - 116 (+3)

1TO4 (G):1 - 1290, where:
3 CFs - 882
5 CFs - 408 (+4)

1TO4 (G):4 - 543, where:
3 CFs - 441
5 CFs - 102 (+1)

1TO5 (k):1 - 10, where:
6 CFs - 10

1TO5 (k):5 - 2, where:
6 CFs - 2

1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18

1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3

1TO7 (h):1 - 7, where:
8 CFs - 7

1TO7 (h):7 - 1, where:
8 CFs - 1

1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16

1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2

RHOMBUS3 (J):2 - 9, where:
5 CFs - 9

RHOMBUS3 (J):3 - 6, where:
5 CFs - 6

RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16

RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8

FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6

FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9

FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3

TREE1 (V):1 - 2, where:
4 CFs - 2

TREE1 (V):2 - 1, where:
4 CFs - 1

TREE1 (V):3 - 1, where:
4 CFs - 1

CROSS (X):1 - 16, where:
6 CFs - 16

CROSS (X):2 - 4, where:
6 CFs - 4

CROSS (X):4 - 4, where:
6 CFs - 4

DAEDALUS10 (i):1 - 6, where:
12 CFs - 6

DAEDALUS10 (i):2 - 4, where:
12 CFs - 4

DAEDALUS10 (i):4 - 1, where:
12 CFs - 1

DAEDALUS10 (i):10 - 1, where:
12 CFs - 1

FLYER (j):1 - 2, where:
8 CFs - 2

FLYER (j):2 - 3, where:
8 CFs - 3

FLYER (j):4 - 3, where:
8 CFs - 3

VENUS (l):1 - 1, where:
5 CFs - 1

VENUS (l):2 - 3, where:
5 CFs - 3

VENUS (l):4 - 1, where:
5 CFs - 1

DAEDALUS8 (m):1 - 2, where:
6 CFs - 2

DAEDALUS8 (m):2 - 2, where:
6 CFs - 2

DAEDALUS8 (m):4 - 1, where:
6 CFs - 1

DAEDALUS8 (m):8 - 1, where:
6 CFs - 1

RHOMBUS5 (n):2 - 4, where:
5 CFs - 4

RHOMBUS5 (n):5 - 1, where:
5 CFs - 1

1TO10 (o):1 - 5, where:
6 CFs - 5

1TO10 (o):10 - 1, where:
6 CFs - 1

ROBOT (p):1 - 4, where:
5 CFs - 4

ROBOT (p):2 - 4, where:
5 CFs - 4

ROBOT (p):4 - 2, where:
5 CFs - 2

STINGRAY (q):1 - 1, where:
5 CFs - 1

STINGRAY (q):2 - 3, where:
5 CFs - 3

STINGRAY (q):3 - 1, where:
5 CFs - 1

Эксперимент по исследованию свойств окрестностей обобщенных симметрий: пройдено 457 (+29) окрестностей из 903 (50,6%, +3,2%).

Цитата: evatutin от 01.06.2020, 20:05

При поиске CMS, отражающей лучи звезды 1:N друг в друга, можно учесть, что искомая CMS должна автоморфно отражать центральный квадрат сам в себя (для симметричной двушки данное свойство было недавно проиллюстрировано, см. https://vk.com/wall162891802_1187). Эта особенность является дополнительным ограничением на поиск, а значит потенциально может снизить необходимые вычислительные затраты. Учет данного ограничения был реализован в коде (теперь по сути ищется два согласованных по CMS цикла: один из них имеет период 1, другой — N, в данном эксперименте N=3). Для трешки

0123456789120478963556982134709876502314458236709139408712562431695807875903416260179285437365140928

учет данной особенности сокращает время поиска CMS (точнее, доказательство ее несуществования с 27617 до 5 с, т.е. более чем в 5000 раз!). Ввиду найденной особенности эксперимент exp723 досрочно прерван и заменен экспериментом exp724 с новой версией расчетного модуля 3.2.1. По первым наблюдениям время счета WU'шки сокращается с десятков часов до нескольких секунд — минут. Считаем...