Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
А в ближайшее время в проекте планируется ли создание хоть одного счётного приложения под Linux?
Получил вот такое письмо: "Здравствуйте, было бы неплохо, если бы вы выпустили SSL-сертификат для gerasim.boinc.ru (IP 31.31.198.181), а то ошибки достали, да и не хотелось бы, чтобы кто-то угнал аккаунт."
В современных условиях, возможно, в сертификате есть смысл.
НО это стоит некоторых средств и это надо как-то устанавливать. Я пару раз сталкивался, и не сразу получалось.
Какие есть мысли на этот счет?
Сайт gerasim.boinc.ru (IP 31.31.198.181) не открывается сейчас. Накануне челленджа - это печально.
SSL-сертификат нужен обязательно. Стоит не дорого, порядка 1 000 руб. (куда перевести копеечку?).
В инете полно подробных инструкций по установке. Нужен доступ с админскими (root'овыми) правами к веб-серверу. Обычно админы серверов/сайтов делают это "с закрытыми глазами".
Здравствуйте. Копеечка конечно хорошо, но можено и бесплатнее...
https://letsencrypt.org/ru/getting-started
P.S. Готов оказать максимальное техническое содействие, если потребуеться....
В OEIS добавлены 2 новых числовых ряда, связанных с X-образными заполнениями диагоналей ДЛК:
* https://oeis.org/draft/A337302
* https://oeis.org/draft/A337303
Цитата: evatutin от 11.07.2020, 13:27О числе классов эквивалентности перестановок из N элементов с одинаковой структурой мультимножества длин циклов
Напомню, что через структуры мультимножеств длин циклов описываются обобщенные симметрии (автоморфизмы) в ДЛК. Рассмотрим, как происходит их построение на примере перестановки
P = [9 3 8 4 7 2 5 1 6 0].
Циклы получаются следующим образом:
P[0]=9, P[9]=0 — цикл длины 2;
P[1]=3, P[3]=4, P[4]=7, P[7]=1 — цикл длины 4;
P[2]=8, P[8]=6, P[6]=5, P[5]=2 — цикл длины 4.Соответствующее перестановке P мультимножество длины циклов L(P) = {2,4,4}.
Для размерности N=10, как было показано whitefox'ом, существует 42 различных мультимножества: {1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,2}, ..., {10}. А для других размерностей? Можно организовать небольшой вычислительный эксперимент и определить, что и было проделано для размерностей N<=12, результаты приведены ниже.
N=1
---
1: {1}N=2
---
1: {1,1}
2: {2}N=3
---
1: {1,1,1}
2: {1,2}
3: {3}N=4
---
1: {1,1,1,1}
2: {1,1,2}
3: {1,3}
4: {2,2}
5: {4}N=5
---
1: {1,1,1,1,1}
2: {1,1,1,2}
3: {1,1,3}
4: {1,2,2}
5: {1,4}
6: {2,3}
7: {5}N=6
---
1: {1,1,1,1,1,1}
2: {1,1,1,1,2}
3: {1,1,1,3}
4: {1,1,2,2}
5: {1,1,4}
6: {1,2,3}
7: {1,5}
8: {2,2,2}
9: {2,4}
10: {3,3}
11: {6}N=7
---
1: {1,1,1,1,1,1,1}
2: {1,1,1,1,1,2}
3: {1,1,1,1,3}
4: {1,1,1,2,2}
5: {1,1,1,4}
6: {1,1,2,3}
7: {1,1,5}
8: {1,2,2,2}
9: {1,2,4}
10: {1,3,3}
11: {1,6}
12: {2,2,3}
13: {2,5}
14: {3,4}
15: {7}N=8
---
1: {1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,2}
3: {1,1,1,1,1,3}
4: {1,1,1,1,2,2}
5: {1,1,1,1,4}
6: {1,1,1,2,3}
7: {1,1,1,5}
8: {1,1,2,2,2}
9: {1,1,2,4}
10: {1,1,3,3}
11: {1,1,6}
12: {1,2,2,3}
13: {1,2,5}
14: {1,3,4}
15: {1,7}
16: {2,2,2,2}
17: {2,2,4}
18: {2,3,3}
19: {2,6}
20: {3,5}
21: {4,4}
22: {8}N=9
---
1: {1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,3}
4: {1,1,1,1,1,2,2}
5: {1,1,1,1,1,4}
6: {1,1,1,1,2,3}
7: {1,1,1,1,5}
8: {1,1,1,2,2,2}
9: {1,1,1,2,4}
10: {1,1,1,3,3}
11: {1,1,1,6}
12: {1,1,2,2,3}
13: {1,1,2,5}
14: {1,1,3,4}
15: {1,1,7}
16: {1,2,2,2,2}
17: {1,2,2,4}
18: {1,2,3,3}
19: {1,2,6}
20: {1,3,5}
21: {1,4,4}
22: {1,8}
23: {2,2,2,3}
24: {2,2,5}
25: {2,3,4}
26: {2,7}
27: {3,3,3}
28: {3,6}
29: {4,5}
30: {9}N=10
---
1: {1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,4}
6: {1,1,1,1,1,2,3}
7: {1,1,1,1,1,5}
8: {1,1,1,1,2,2,2}
9: {1,1,1,1,2,4}
10: {1,1,1,1,3,3}
11: {1,1,1,1,6}
12: {1,1,1,2,2,3}
13: {1,1,1,2,5}
14: {1,1,1,3,4}
15: {1,1,1,7}
16: {1,1,2,2,2,2}
17: {1,1,2,2,4}
18: {1,1,2,3,3}
19: {1,1,2,6}
20: {1,1,3,5}
21: {1,1,4,4}
22: {1,1,8}
23: {1,2,2,2,3}
24: {1,2,2,5}
25: {1,2,3,4}
26: {1,2,7}
27: {1,3,3,3}
28: {1,3,6}
29: {1,4,5}
30: {1,9}
31: {2,2,2,2,2}
32: {2,2,2,4}
33: {2,2,3,3}
34: {2,2,6}
35: {2,3,5}
36: {2,4,4}
37: {2,8}
38: {3,3,4}
39: {3,7}
40: {4,6}
41: {5,5}
42: {10}N=11
---
1: {1,1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,1,4}
6: {1,1,1,1,1,1,2,3}
7: {1,1,1,1,1,1,5}
8: {1,1,1,1,1,2,2,2}
9: {1,1,1,1,1,2,4}
10: {1,1,1,1,1,3,3}
11: {1,1,1,1,1,6}
12: {1,1,1,1,2,2,3}
13: {1,1,1,1,2,5}
14: {1,1,1,1,3,4}
15: {1,1,1,1,7}
16: {1,1,1,2,2,2,2}
17: {1,1,1,2,2,4}
18: {1,1,1,2,3,3}
19: {1,1,1,2,6}
20: {1,1,1,3,5}
21: {1,1,1,4,4}
22: {1,1,1,8}
23: {1,1,2,2,2,3}
24: {1,1,2,2,5}
25: {1,1,2,3,4}
26: {1,1,2,7}
27: {1,1,3,3,3}
28: {1,1,3,6}
29: {1,1,4,5}
30: {1,1,9}
31: {1,2,2,2,2,2}
32: {1,2,2,2,4}
33: {1,2,2,3,3}
34: {1,2,2,6}
35: {1,2,3,5}
36: {1,2,4,4}
37: {1,2,8}
38: {1,3,3,4}
39: {1,3,7}
40: {1,4,6}
41: {1,5,5}
42: {1,10}
43: {2,2,2,2,3}
44: {2,2,2,5}
45: {2,2,3,4}
46: {2,2,7}
47: {2,3,3,3}
48: {2,3,6}
49: {2,4,5}
50: {2,9}
51: {3,3,5}
52: {3,4,4}
53: {3,8}
54: {4,7}
55: {5,6}
56: {11}N=12
---
1: {1,1,1,1,1,1,1,1,1,1,1,1}
2: {1,1,1,1,1,1,1,1,1,1,2}
3: {1,1,1,1,1,1,1,1,1,3}
4: {1,1,1,1,1,1,1,1,2,2}
5: {1,1,1,1,1,1,1,1,4}
6: {1,1,1,1,1,1,1,2,3}
7: {1,1,1,1,1,1,1,5}
8: {1,1,1,1,1,1,2,2,2}
9: {1,1,1,1,1,1,2,4}
10: {1,1,1,1,1,1,3,3}
11: {1,1,1,1,1,1,6}
12: {1,1,1,1,1,2,2,3}
13: {1,1,1,1,1,2,5}
14: {1,1,1,1,1,3,4}
15: {1,1,1,1,1,7}
16: {1,1,1,1,2,2,2,2}
17: {1,1,1,1,2,2,4}
18: {1,1,1,1,2,3,3}
19: {1,1,1,1,2,6}
20: {1,1,1,1,3,5}
21: {1,1,1,1,4,4}
22: {1,1,1,1,8}
23: {1,1,1,2,2,2,3}
24: {1,1,1,2,2,5}
25: {1,1,1,2,3,4}
26: {1,1,1,2,7}
27: {1,1,1,3,3,3}
28: {1,1,1,3,6}
29: {1,1,1,4,5}
30: {1,1,1,9}
31: {1,1,2,2,2,2,2}
32: {1,1,2,2,2,4}
33: {1,1,2,2,3,3}
34: {1,1,2,2,6}
35: {1,1,2,3,5}
36: {1,1,2,4,4}
37: {1,1,2,8}
38: {1,1,3,3,4}
39: {1,1,3,7}
40: {1,1,4,6}
41: {1,1,5,5}
42: {1,1,10}
43: {1,2,2,2,2,3}
44: {1,2,2,2,5}
45: {1,2,2,3,4}
46: {1,2,2,7}
47: {1,2,3,3,3}
48: {1,2,3,6}
49: {1,2,4,5}
50: {1,2,9}
51: {1,3,3,5}
52: {1,3,4,4}
53: {1,3,8}
54: {1,4,7}
55: {1,5,6}
56: {1,11}
57: {2,2,2,2,2,2}
58: {2,2,2,2,4}
59: {2,2,2,3,3}
60: {2,2,2,6}
61: {2,2,3,5}
62: {2,2,4,4}
63: {2,2,8}
64: {2,3,3,4}
65: {2,3,7}
66: {2,4,6}
67: {2,5,5}
68: {2,10}
69: {3,3,3,3}
70: {3,3,6}
71: {3,4,5}
72: {3,9}
73: {4,4,4}
74: {4,8}
75: {5,7}
76: {6,6}
77: {12}Число различных по структуре мультимножества длины циклов классов эквивалентности перестановок из N элементов образует следующий числовой ряд:
1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77
Он уже представлен в OEIS (см. https://oeis.org/A000041) и представляет собой т.н. разбиения числа (см. https://ru.wikipedia.org/wiki/Разбиение_числа) — число способов представления целого положительного числа N в виде суммы целых положительных слагаемых b(1) + b(2) + b(3) + ... + b(m) = N, причем b(i) <= b(i+1).
Вот так в математике все связано: от латинских квадратов к перестановкам, от них — к циклам в их составе, а от мультимножеств длин циклов — к разбиениям числа на слагаемые!
Оказывается это то же самое, что и the number of conjugacy classes in the symmetric group S_n (and the number of irreducible representations of S_n). Будем знать, спасибо Joerg Arndt за уточнение! :)
Результаты поиска КФ ОДЛК в проекте Gerasim@Home за месяц:
ONCE (A):1 - 1677972, where:
1 CFs - 33160
2 CFs - 1644812
LINE3 (B):1 - 73831, where:
2 CFs - 18735
3 CFs - 55096 (+2620)
LINE3 (B):2 - 46283, 36:1, where:
2 CFs - 18735
3 CFs - 27548 (+1310)
LINE4 (C):1 - 126, where:
2 CFs - 4
4 CFs - 122 (+2)
LINE4 (C):2 - 126, where:
2 CFs - 4
4 CFs - 122 (+2)
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2252, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 648 (+8)
1TO3 (F):1 - 375, where:
4 CFs - 375 (+6)
1TO3 (F):3 - 125, where:
4 CFs - 125 (+2)
1TO4 (G):1 - 1298, where:
3 CFs - 882
5 CFs - 416 (+4)
1TO4 (G):4 - 545, where:
3 CFs - 441
5 CFs - 104 (+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
Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофический срез 1 [Px Py Pv]: пройдено 583 (+42) окрестностей из 903 (64,6%, +4,7%);
* парастрофический срез 3 [Py Px Pv]: пройдено 45 (+13) окрестности из 1764 (2,5%, +0,7%).
Эксперимент по подсчету главных классов ДЛК порядка 9 — завершен, данные ожидают постобработки с моим участием.
О числе главных классов ДЛК и числе нормализованных ДЛК порядка 9. Независимое подтверждение найденных ранее значений
В результате выполнения эксперимента exp774 по подсчету главных классов ДЛК порядка 9 через классы эквивалентности X-образных заполнений и ESODLS-схемы (см. https://vk.com/wall162891802_1296) было получено 633 300 WU'шек, каждая из которых содержит 2 целых числа (для определенности A и B): A — число КФ, соответствующих выбранному X-образному заполнению линейки + начальное ячеек ДЛК; B — число дозаполнений до ДЛК (число СНДЛК, соответствующих выбранному X-образному заполнения линейки + начальное ячеек ДЛК). Например, для самой первой WU'шки wu_e774_line1_0.wu с начальным заполнением
0 2 3 5 6 4 7 8 1
. 1 4 2 . . 5 0 .
. . 2 . . . 3 . .
. . . 3 . 2 . . .
. . . . 4 . . . .
. . . 6 . 5 . . .
. . 5 . . . 6 . .
. 8 . . . . . 7 .
7 . . . . . . . 8
было получено, что A = 1536075 и B = 12783424.
Суммируя полученные значения по линейкам, получаем число КФ в линейке = sum(A[i]) и число СНДЛК в линейке = sum(B[i]) (соответственно 4-й и 5-й столбцы таблицы).
Далее, суммируя значения по 4-му столбцу (число КФ по линейкам), получаем общее число КФ или, что то же самое — общее число главных классов ДЛК порядка 9, равное 3292326155394. Цифра совпадает с членом a(9) последовательности https://oeis.org/A287764, найденным ранее whitefox'ом через Юнион Джек заполнения. Выполненный расчет (через X-образные заполнения) является независимым подтверждением правильности полученной ранее величины.
Для каждой линейки можно найти число соответствующих ей нормализованных ДЛК, умножив число СНДЛК на кратность линейки, что дает 7-й (последний) столбец таблицы. Суммируя значения по 7-му столбцу, можно получить общее число нормализованных ДЛК порядка 9 (член a(9) ряда https://oeis.org/A274171), равное 5056994653507584, что в точности совпадает с ранее найденными значениями (данная проверка является уже четвертой: первые две были выполнены полным перебором в проекте Gerasim@Home (http://gerasim.boinc.ru) и независимо на вычислительном кластере "Академик В.М. Матросов" в СО РАН в Иркутске Олегом Заикиным и Степаном Кочемазовым, третья — whitefox'ом через Юнион Джек заполнения попутно с подсчетом числа главных классов).
На выполнение расчетов в общей сложности ушло около месяца вычислительного времени проекта Gerasim@Home (включая досчет хвостов + 2 параллельно работающих подпроекта по анализу окрестностей обобщенных симметрий ДЛК в первом и третьем парастрофических срезах, реальная производительность всех подпроектов проекта — 7,4 TFLOP/s по данным boincstats.com).
PS. Если складывать число нормализованных ДЛК по линейкам в Excel'е, общее значение получается равным 5056994653507580 (на конце 0, а должна быть 4). Это не ошибка в расчетах, это у Excel'я не хватает точности для хранения всех значащих цифр. Если сумму найти вручную или с использованием int64-значений, получится верное значение 5056994653507584 :).
[upd]
Число нормализованных ДЛК порядка 9 считали еще и в RakeSearch попутно с поиском строчно-перестановочных ОДЛК (см. https://rake.boincfast.ru/rakesearch/forum_thread.php?id=187). Данный прошлогодний анонс коллег и братьев по оружию я упустил, грешен, каюсь :). Таким образом, выполненный подсчет числа нормализованных ДЛК порядка 9 является не 4-м, а 5-м независимым подтверждением найденной величины. Спасибо hoarfrost'у за уточнение!