Атакуем последовательность A200000

[Zealint]

Тема исключительно для любителей пробивать труднорешаемые задачи в свободное время.

Предыстория

Давно обещал взяться за последовательность A200000. Пытался как-то перевести название задачи: то ли подсчёт орнаментов, то ли извилин. В конце концов оставил просто «подсчёт гамильтоновых меандров на решётке P_n \times P_n», не найдя устоявшегося перевода слова «meander».

Однако возникла проблема: меандры на квадратной решётке нужно считать таким образом, что получаемые друг из друга поворотом и отражением меандры считаются одинаковыми. Участник alexBlack предложил вариант подсчёта, но мне такой вариант отчего-то не нравится. Интуиция подсказывает, что есть более просто вариант.

А если считать симметричные меандры различными?

Есть похожая задача, в которой симметрия и повороты дают различные меандры, она оказалась гораздо проще (A200749). Были предложены результаты до n=15. «На коленках» за пару часов удалось наклепать программу, считающую до n=16. Вот ответы:

01 :: 1
02 :: 1
03 :: 0
04 :: 11
05 :: 320
06 :: 71648
07 :: 55717584
08 :: 213773992667
09 :: 3437213982024260
10 :: 249555807519163873078
11 :: 78627163663841340597702692
12 :: 109477494899001088619906813170744
13 :: 666376868834051436218404625691790011056
14 :: 17813932068751803215543399261217225231408150272
15 :: 2084618062581510894785237376608868017658716989948775752
16 :: 1069049587048126292657245511018395164729584995637677006604201633

Первые 15 чисел совпали с теми, что были у alexBlack, можно добавить 16-е в энциклопедию, но я пока попробую пробить дальше. Нужно просто переписать предварительную программу по всей строгости моего любимого жанра «труднорешаемых задач». Думаю, n=17 будет для меня точным потолком.

Вопрос

Можно ли как-то «красиво» учесть симметрию в классическом алгоритме динамического программирования по профилю? Красиво - это, конечно, звучит субъективно. Под красивостью здесь будем понимать то, что решение для A200000 окажется не более сложным, чем для A200749.

Дополнение

Коль скоро для решения применяется метод матрицы переноса (Transfer Matrix Method), для решеток P_m \times P_n при фиксированных m мы быстро получаем линейные рекуррентные соотношения с постоянными коэффициентами. Так, для m=3 имеем число меандров (A078008):

$$ a_1=0,\,a_2=1,\,a_3=0,\qquad a_n=a_{n-1}+2a_{n-2},\quad n\geq 4. $$

Для m=4 порядок уже равен 6 (нет в OEIS):

$$ a_1=0, \,a_2=1, \,a_3=2, \,a_4=11, \,a_5=42, \,a_6=199, $$

$$a_n=3a_{n-1}+9 a_{n-2}-10 a_{n-3}-7 a_{n-4}+7 a_{n-5}-a_{n-6},\quad n\geq 7.$$

Порядки прочих соотношений приведены ниже.

m=5 \, \rightarrow \, 12
m=6 \, \rightarrow \, 31
m=7 \, \rightarrow \, 69
m=8 \, \rightarrow \, 178
m=9 \, \rightarrow \, 433

Это не предел, могу вывести и другие соотношения, пока их порядок не начнёт превышать пару десятков тысяч, то есть до m=12 ещё будет реально посчитать.

Кому-нибудь ещё интересно прободаться с задачей?
Мне интересно, как можно красиво учесть симметрию (как в случае A200000).
Если есть красивые идеи, предлагаю поделиться.

Если кто-то знает приложения этой задачи в физике, дайте, пожалуйста, знать.

[Zealint]

Для A200749 вчера днём запустил программу для $n=17$. Сегодня утром получил ответ, но нужна независимая проверка. Пока не проверю, могу показать первые и последние цифры.

Ответ для $n=17$: $239\;\cdots\;872,$ (73 цифры).

Может быть сумею даже для 18 пробить. Но одному становится скучно.

Как красиво учесть симметрию пока не придумал.

[maxal]

Zealint в сообщении #677494 писал(а):

Для A200749 вчера днём запустил программу для $n=17$. Сегодня утром получил ответ, но нужна независимая проверка. Пока не проверю, могу показать первые и последние цифры.

Когда проверите, оформите свои результаты в виде b-файла типа текущего https://oeis.org/A200749/b200749.txt и залейте в A200749. Заранее спасибо.

[alexBlack]

Попробовал еще один вариант.
Считаем профилем кольцо (0,0)-(0,k)-(k,k)-(k,0)-(0,0). Идем от внешнего кольца к центру решетки. Была надежда, что удастся посчитать хотя бы симметричные пути, а несимметричные просто вычислить из A200749, но все равно дальше $n=10$ не удалось продвинуться. Чтож, хотя бы $n=9$ теперь известно.

      x1    x2         x4                   x8              A200000               A200749         
                                                       =x1+x2+x4+x8    =x1+2*x2+4*x4+8*x8
 ---- -- ----- ---------- -------------------- -------------------- ---------------------
  n=1 1      0          0                    0                    1                     1  
    2 1      0          0                    0                    1                     1  
    3 0      0          0                    0                    0                     0  
    4 1      1          2                    0                    4                    11               
    5 0      0          4                   38                   42                   320  
    6 0     12        170                 8868                 9050                 71648  
    7 0      0       1322              6964037              6965359              55717584  
    8 1    299     206305          26721645856          26721852461          213773992667  
    9 0      0    9074685      429651743215690      429651752290375      3437213982024260  
   10 2  33544 3858758949 31194475937966096274 31194475941824888769 249555807519163873078  

[cepesh]

Тема перемещена из форума «Computer Science» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

[maxal]

Пока суд да дело, последовательность A200000 была вычислена аж до 17 членов, причем последние 7 из них вычислил некто Du в этом году (его программа представлена в описании последовательности). Самому разбираться в этой программе времени нет, но если вдруг кто разберётся -- было бы интересно узнать, если ли там какие-то неочевидные идеи.