Поворот блоков в квадрозавре

Message boards : Science : Поворот блоков в квадрозавре
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 1973 - Posted: 9 May 2021, 7:09:20 UTC
Last modified: 9 May 2021, 7:41:38 UTC

Квадрозавр или чемпион 12-го порядка



Вспомнила, как лихо мы с Белышевым поворачивали блоки в ДЛК 10-го порядка блочной структуры.
Наш замечательный эксперимент, ставший уже историей.
Мы получили в этом эксперименте прекрасные результаты!

Эх, где же вы, Алексей?
Теперь можно заняться поворотом блоков в ДЛК 12-го порядка.
Вы могли бы это виртуозно сделать, как всё, что вы делали.
Приходите, подключайтесь к нашим исследованиям.
У нас отличная команда, но вас очень и очень не хватает!

Ну вот, смотрим на квадрозавра.
Блоки видим. Надо их поворачивать.
Поставила эту задачу перед Harry White. В своё время он писал программу поворота блоков в ДЛК 10-го порядка по моей просьбе.
Сейчас с интересом занялся поворотом блоков в ДЛК 12-го порядка.
Тут, понятно, всё намного сложнее.
Схема та же самая, однако блоков слишком много.
36 блоков мы видим на иллюстрации, они раскрашены. Но это ещё не всё. Harry пишет, что в этом ДЛК 72 блока. Или ещё интеркалятами их называют :)
Представили, сколько будет вариантов при поворотах всех 72 блоков?!
Цитирую письмо Harry
There are 9,474,296,895 combinations of the blocks to turn.

Break into how many runs?
If you enter 1, it will try to make all 9,474,296,895 DLS in 1 program run, (and run out of memory!)
If you enter 10, you will need to run the program 10 times to make them all.
If you enter 50, you will need to run the program 50 times to make them all.

The mod number chooses which combinations to use.
At 10 runs, mod 0 will use combinations 10, 20, 30, ..., mod 1 will use 1, 11, 21, ..., and mod 9 will use 9, 19, 29, ...

I entered 10 for runs and 0 for mod number making 947,429,688 DLS.
That is still a big number and perhaps too big for the canonizer to process all at once anyway.

If you use 100 for runs, you should get 94,742,968 per run,
choosing a mod value of 0, 1, 2, ... or 99 for the different runs.
For 1000 runs, 9,474,296 DLS per run. Mod values 0, 1, 2, ..., or 999.
For 10000 runs 947,429 per run, and so on.

Здесь он рассказывает, как пользоваться программой поворота блоков.
Мне удалось получить минимальную порцию ДЛК - 947429 штук.
Первым делом я их канонизировала
Order? 12
Format, (1: first row or 2: \diagonal)? 2
File name? inp
.. writing DLS to file output12CF2_2.txt
number of DLS 947429 CFs 941044

elapsed time 0:21:17

Изоморфов не сильно много.
А дальше такой интерес: как богаты эти ДЛК Д-трансверсалями.
С подсчётом Д-трансверсалей туго, программа Harry долго очень считает.
Я попробовала посчитать программой Tomas Brada, эта программа довольно быстро прощёлкала 34 тысячи с хвостиком ДЛК.
Конечно, всю порцию не стала обсчитывать.
Пока проверенные ДЛК не достигают по Д-трансверсалям своего прародителя, прародитель содержит 28496 Д-трансверсалей.
Вот что получилось (показываю только количества Д-трансверсалей больше 13000, и не все, конечно)

num_dtrans: 14068
num_dtrans: 13620
num_dtrans: 13480
num_dtrans: 13680
. . .
num_dtrans: 13820
num_dtrans: 14104
num_dtrans: 14112
num_dtrans: 13928
num_dtrans: 13836
num_dtrans: 13692
num_dtrans: 14060
num_dtrans: 14060
num_dtrans: 14164
num_dtrans: 14020
num_dtrans: 13932
num_dtrans: 13964
num_dtrans: 14060
num_dtrans: 14440
num_dtrans: 14656
num_dtrans: 13412
num_dtrans: 14692
num_dtrans: 14008
num_dtrans: 13968
num_dtrans: 14344
. . .
num_dtrans: 13988
num_dtrans: 13452
num_dtrans: 14180
num_dtrans: 14284
num_dtrans: 13844
num_dtrans: 13996
num_dtrans: 13840
num_dtrans: 13548
num_dtrans: 14492
num_dtrans: 14008
num_dtrans: 14808
num_dtrans: 13876
num_dtrans: 14100
num_dtrans: 13988
num_dtrans: 13784
num_dtrans: 13928
num_dtrans: 13728
num_dtrans: 16168
num_dtrans: 14180
. . .
num_dtrans: 13976
num_dtrans: 13304
num_dtrans: 13756
num_dtrans: 13684
num_dtrans: 13548
num_dtrans: 14888
num_dtrans: 13784
num_dtrans: 13840
num_dtrans: 14456
num_dtrans: 13884
num_dtrans: 14276
num_dtrans: 13784
num_dtrans: 14128
num_dtrans: 14144
num_dtrans: 14448
num_dtrans: 14400
num_dtrans: 14332
num_dtrans: 13884
num_dtrans: 14268
. . .
num_dtrans: 13764
num_dtrans: 13884
num_dtrans: 13992
num_dtrans: 13748
num_dtrans: 14092
num_dtrans: 14384
. . .
num_dtrans: 14204
num_dtrans: 13180
num_dtrans: 13824
num_dtrans: 14312
num_dtrans: 13268
num_dtrans: 13692
num_dtrans: 13432
num_dtrans: 15636
num_dtrans: 14092
num_dtrans: 13744
num_dtrans: 13264
num_dtrans: 14552
num_dtrans: 13940
num_dtrans: 14132
num_dtrans: 14080
. . .
num_dtrans: 14168
num_dtrans: 13924
num_dtrans: 13988
num_dtrans: 13840
num_dtrans: 13160
num_dtrans: 14088
num_dtrans: 13160
num_dtrans: 14480
num_dtrans: 14488
num_dtrans: 13872
. . .
num_dtrans: 13320
num_dtrans: 13808
num_dtrans: 13760
num_dtrans: 13388
num_dtrans: 13688
num_dtrans: 13888
. . .
num_dtrans: 14220
num_dtrans: 14144
num_dtrans: 14144
num_dtrans: 14280
num_dtrans: 13384
num_dtrans: 13764
num_dtrans: 13660
num_dtrans: 13764
num_dtrans: 13548
. . .
num_dtrans: 14012
num_dtrans: 14148
num_dtrans: 13336
num_dtrans: 13640

Ну, даже если рекорда не будет, всё равно это замечательный генератор ДЛК с приличным количеством Д-трансверсалей.
BOINC-проекта для поиска БД КФ ОДЛК 12-го порядка у нас пока нет, но вдруг будет.
Вот и работа уже готова :)
Mynx сейчас обсчитывает примерно такие ДЛК (по количеству Д-трансверсалей).
У него их 23 штуки осталось.
ID: 1973 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 1974 - Posted: 9 May 2021, 7:17:07 UTC

Harry пишет, что никак не удаётся получить такую порцию ДЛК, которую канонизатор обсчитает.
Всё время компьютер зависает при канонизации.
Ну, вот минимальную порцию канонизатор берёт даже на моём компьютере.
ID: 1974 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 1975 - Posted: 9 May 2021, 19:12:02 UTC
Last modified: 9 May 2021, 19:24:54 UTC

Визуально определила текущий максимум Д-трансверсалей 16168 в ДЛК, полученных поворотом блоков в квадрозавре; текущий максимум принадлежит этому квадратику

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

Можно добавить его в топовые ДЛК 12-го порядка.
ID: 1975 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 1976 - Posted: 9 May 2021, 19:22:52 UTC
Last modified: 9 May 2021, 19:32:37 UTC

Для сравнения приведу текущий максимум по Д-трансверсалям и по ОДЛК от господина Ватутина, о котором он сообщил в дискуссии OEIS.
Из сообщения https://vk.com/wall162891802?w=wall162891802_1660
И еще один квадрат вдогонку:

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

у которого 15456 диагональных трансверсалей и 4167043 ОДЛК, что позволяет усилить текущее нижнее ограничение с a(12)>=3071828 до a(12)>=4167043 в ряду https://oeis.org/A287695.

Как видим, ДЛК, порождаемые квадрозавром при повороте блоков, очень даже солидные получаются по Д-трансверсалям.
Главное, этих ДЛК очень много. Все их обсчитать на Д-трансверсали нереально на одном ПК. Может быть, и побольше найденного максимума ещё будет. Вдруг даже и прародителя "детки" превзойдут :) Кто их знает.
Harry White пытается хоть какую-то порцию обсчитать на Д-трансверсали и... никак.
А тем более - обсчитать все эти ДЛК на ОДЛК. Это можно только на 1000 машинах делать.
Квадратики 10-го порядка мы с Белышевым в своё время обсчитали, но там всё же поменьше было произведено ДЛК при повороте блоков.
ID: 1976 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 1994 - Posted: 13 May 2021, 13:30:55 UTC
Last modified: 13 May 2021, 18:27:05 UTC

Попробовала обсчитать всю порцию из 941044 КФ ОДЛК, полученных поворотом блоков в квадрозавре, на Д-трансверсали программой Harry White GetTransversals.
Программа работала больше 4-х часов, а потом аварийно прекратила работу.
Написала об этом Harry.
Он ответил, что программу исправил и сейчас тестирует её на присланной мной порции квадратов.

Я тоже немного протестировала.
Взяла ДЛК 12-го порядка из статьи А. Чернова

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

и повернула в нём блоки.
В этом ДЛК программа нашла всего 12 блоков (или интеркалятов), быстренько их повернула и выдала 4095 ДЛК; из них 1071 уникальных, большой отсев изоморфов.
Посчитала в этих ДЛК Д-трансверсали новой программой. Программа с этой порцией, конечно, справилась быстро.
"Детки" не превзошли прародителя, максимальное количество Д-трансвесалей в них 5788, в этом квадратике

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

В прародителе содержится 8760 Д-трансверсалей.

Интересно попробовать "деток" в методе Пелегрино-Ланселотти. Будут ли они давать ортогональные пары 36-го порядка?
Квадратики "лёгкие" получились, обсчитываться на ОДЛК должны быстро.
ID: 1994 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 22 Oct 17
Posts: 2499
Credit: 0
RAC: 0
Message 2017 - Posted: 14 May 2021, 12:05:35 UTC
Last modified: 14 May 2021, 12:11:56 UTC

Хорошая новость!
Harry White обсчитал минимальную порцию ДЛК, полученную от квадрозавра поворотом блоков, на Д-трансверсали.
Он прислал консоль, сейчас программа выводит на консоль прогресс (по 1024 ДЛК).
Покажу частично

order? 12
Type of transversals, 1 all or 2 diagonal? 2
File name? inp
1024
2048
3072
4096
5120
6144
7168
8192
9216
10240
. . . . .
927744
928768
929792
930816
931840
932864
933888
934912
935936
936960
937984
939008
940032
.. writing counts to file 12Transversals.txt
square 938997 max transversals 18808

elapsed time 23:39:40

Вычисления выполнялись почти сутки. Круто!
Максимальное количество Д-трансверсалей 18808 имеет 938997-й ДЛК, в самом хвосте :)
Не превзошли "детки" прародителя. Однако квадратик с 18808 Д-трансверсалями весьма солидный, надо его включить в мой набор топовых ДЛК.

Harry сделал также Топ-10 по Д-трансверсалям из этой порции ДЛК, как я его просила

      CF        trans
    ------      -----
    938997      18808
    938609      16592
    939707      16184
     19475      16168
       185      16168
    809765      16128
     14185      15992
      1266      15952
    840292      15880
    934547      15720

Более того, он выписал соответствующие ДЛК.
Тут есть два ДЛК с 16168 Д-трансверсалями, они не изоморфные (здесь порция различных КФ и изоморфных ДЛК не может быть).

Покажу и квадратики, которые Harry выписал.

№185
 0 10  4  5  2  3  9  8  7  6 11  1
11  1  7  6  9  8  2  3  4  5  0 10
 4  5  2  8  0  1 11 10  9  3  7  6
 7  6  9  3 11 10  0  1  2  8  4  5
 2  3 11  1  4  6  7  5  0 10  9  8
 9  8  0 10  7  5  4  6 11  1  2  3
 8  9  1 11  5  7  6  4 10  0  3  2
 3  2 10  0  6  4  5  7  1 11  8  9
 5  7  3  9  1  0 10 11  8  2  6  4
 6  4  8  2 10 11  1  0  3  9  5  7
 1 11  6  7  3  2  8  9  5  4 10  0
10  0  5  4  8  9  3  2  6  7  1 11

№1266
 0 10  4  5  2  3  9  8  7  6 11  1
11  1  7  6  9  8  2  3  4  5  0 10
 4  5  2  8  0  1 11 10  9  3  7  6
 7  6  9  3 11 10  0  1  2  8  4  5
 9  3 11  1  4  6  7  5  0 10  2  8
 2  8  0 10  7  5  4  6 11  1  9  3
 3  9  1 11  5  7  6  4 10  0  8  2
 8  2 10  0  6  4  5  7  1 11  3  9
 5  4  3  9 10  0  1 11  8  2  6  7
 6  7  8  2  1 11 10  0  3  9  5  4
 1 11  6  7  3  2  8  9  5  4 10  0
10  0  5  4  8  9  3  2  6  7  1 11

№14185
 0 10  4  5  2  3  9  8  7  6 11  1
11  1  7  6  9  8  2  3  4  5  0 10
 4  5  2  8  0 10 11  1  9  3  7  6
 7  6  9  3 11  1  0 10  2  8  4  5
 9  8  0  1  4  6  7  5 11 10  2  3
 2  3 11 10  7  5  4  6  0  1  9  8
 3  2  1  0  5  7  6  4 10 11  8  9
 8  9 10 11  6  4  5  7  1  0  3  2
 5  4  3  9 10  0  1 11  8  2  6  7
 6  7  8  2  1 11 10  0  3  9  5  4
 1 11  5  7  8  9  3  2  6  4 10  0
10  0  6  4  3  2  8  9  5  7  1 11

№19475
 0 10  4  5  2  3  9  8  7  6 11  1
11  1  7  6  9  8  2  3  4  5  0 10
 4  5  2  8  1  0 10 11  9  3  7  6
 7  6  9  3 10 11  1  0  2  8  4  5
 8  2 11  1  4  6  7  5  0 10  3  9
 3  9  0 10  7  5  4  6 11  1  8  2
 9  3 10 11  5  7  6  4  1  0  2  8
 2  8  1  0  6  4  5  7 10 11  9  3
 6  7  3  9  0  1 11 10  8  2  5  4
 5  4  8  2 11 10  0  1  3  9  6  7
 1 11  6  7  3  2  8  9  5  4 10  0
10  0  5  4  8  9  3  2  6  7  1 11

№809765
 0 10  4  5  2  8  9  3  7  6 11  1
11  1  7  6  9  3  2  8  4  5  0 10
 5  7  2  8  0 10 11  1  9  3  6  4
 6  4  9  3 11  1  0 10  2  8  5  7
 9  8  1 11  4  6  7  5 10  0  2  3
 2  3 10  0  7  5  4  6  1 11  9  8
 3  9  0 10  5  7  6  4 11  1  8  2
 8  2 11  1  6  4  5  7  0 10  3  9
 4  6  3  9  1  0 10 11  8  2  7  5
 7  5  8  2 10 11  1  0  3  9  4  6
 1 11  5  7  3  9  8  2  6  4 10  0
10  0  6  4  8  2  3  9  5  7  1 11

№840292
 0 10  4  6  2  8  3  9  5  7 11  1
11  1  5  7  3  9  2  8  6  4  0 10
 4  6  2  8  0 10  1 11  9  3  7  5
 5  7  9  3  1 11 10  0  2  8  6  4
 8  2  0 10  4  6  7  5  1 11  3  9
 3  9 11  1  7  5  4  6 10  0  2  8
 9  3  1 11  5  7  6  4  0 10  8  2
 2  8 10  0  6  4  5  7 11  1  9  3
 7  5  3  9 11  1  0 10  8  2  4  6
 6  4  8  2 10  0 11  1  3  9  5  7
 1 11  7  5  9  3  8  2  4  6 10  0
10  0  6  4  8  2  9  3  7  5  1 11

№934547
 0 10  4  6  2  8  3  9  7  5 11  1
11  1  7  5  3  9  2  8  4  6  0 10
 4  6  2  8  1 11 10  0  9  3  7  5
 7  5  9  3 10  0  1 11  2  8  4  6
 3  9 10  0  4  6  7  5  1 11  2  8
 2  8  1 11  7  5  4  6 10  0  9  3
 8  2 11  1  5  7  6  4  0 10  3  9
 9  3  0 10  6  4  5  7 11  1  8  2
 5  7  3  9  0 10 11  1  8  2  6  4
 6  4  8  2 11  1  0 10  3  9  5  7
 1 11  5  7  9  3  8  2  6  4 10  0
10  0  6  4  8  2  9  3  5  7  1 11

№938609
 0 10  4  6  2  8  3  9  7  5 11  1
11  1  7  5  3  9  8  2  4  6  0 10
 5  7  2  8  1 11 10  0  9  3  4  6
 6  4  9  3 10  0  1 11  2  8  5  7
 3  9  1 11  4  6  7  5  0 10  8  2
 8  2  0 10  7  5  4  6 11  1  3  9
 2  8 10  0  5  7  6  4  1 11  9  3
 9  3 11  1  6  4  5  7 10  0  2  8
 4  6  3  9  0 10 11  1  8  2  7  5
 7  5  8  2 11  1  0 10  3  9  6  4
 1 11  5  7  9  3  2  8  6  4 10  0
10  0  6  4  8  2  9  3  5  7  1 11

№938997
 0 10  4  6  2  8  3  9  7  5 11  1
11  1  7  5  3  9  8  2  4  6  0 10
 6  4  2  8  0 10 11  1  9  3  5  7
 5  7  9  3 11  1  0 10  2  8  6  4
 2  8  0 10  4  6  7  5 11  1  9  3
 9  3 11  1  7  5  4  6  0 10  2  8
 3  9  1 11  5  7  6  4 10  0  8  2
 8  2 10  0  6  4  5  7  1 11  3  9
 7  5  3  9  1 11 10  0  8  2  4  6
 4  6  8  2 10  0  1 11  3  9  7  5
 1 11  5  7  9  3  2  8  6  4 10  0
10  0  6  4  8  2  9  3  5  7  1 11

№939707
 0 10  4  6  2  8  3  9  7  5 11  1
11  1  7  5  3  9  8  2  4  6  0 10
 7  5  2  8  1 11  0 10  9  3  4  6
 4  6  9  3 10  0 11  1  2  8  7  5
 3  9 11  1  4  6  7  5  0 10  8  2
 8  2  0 10  7  5  4  6 11  1  3  9
 2  8 10  0  5  7  6  4  1 11  9  3
 9  3  1 11  6  4  5  7 10  0  2  8
 6  4  3  9  0 10  1 11  8  2  5  7
 5  7  8  2 11  1 10  0  3  9  6  4
 1 11  5  7  9  3  2  8  6  4 10  0
10  0  6  4  8  2  9  3  5  7  1 11

Квадраты выписаны в порядке возрастания номеров.
Собственно, все эти ДЛК надо включить в топовые, они все с приличным количеством Д-трансверсалей.

Напомню: минимальная порция, которую я получила по программе Harry поворота блоков в квадрозавре, содержит 10000-ю часть всех ДЛК.
Все ДЛК получить на одном ПК нереально, а тем более обсчитать их на Д-трансверсали. Уж не говорю о том, чтобы обсчитать их на ОДЛК.
Не исключено, что среди всех ДЛК есть и ДЛК с бОльшим количеством Д-трансверсалей, чем найденный в минимальной порции максимум.
Как я уже говорила, программа поворота блоков - замечательный генератор ДЛК с приличным количеством Д-трансверсалей.
Отличный генератор заданий для будущего BOINC-проекта!
ID: 2017 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : Science : Поворот блоков в квадрозавре


©2021 Progger & Stefano Tognon (ice00)