Частичная сумма латинского квадрата

[0101]

Здравствуйте!
Задан латинский квадрат в виде матрицы $M[ n,n]
$ M[i,j]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$
Подскажите, пожалуйста,
известны ли какие-нибудь алгоритмы вычисления суммы элементов
частичного прямоугольника произвольного размера, включающего в себя
элемент $M[0,0]$.
Что касается попыток решения -
задачу можно свести к подсчету количества единичных значений булевых функций,
определяющих двоичные разряды $M[i,j]$,
но получается сложно очень,
нужны дополнительные свойства чтобы понизить сложность,
может быть решение уже кем-то найдено

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены ТеХом, отсутствуют попытки решения.

Наберите формулы ТеХом, как написано здесь, приведите попытки решения, после чего сообщите в теме Сообщение в карантине исправлено и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: возвращено

[0101]

Палиндромы подобные нижеприведенному могут послужить решению поставленной задачи.
Чего-то у меня на экране не видны 4 последних столбца.
Латинский квадрат -это таблица Кэли, а что можно сказать по поводу идентификации этого палиндрома?


$\left(\begin{array}{ccccccccccccccccccccccccccc} 0&1&2&2&3&4&4&5&6&4&5&6&6&7&8&8&9&10&8&9&10&10&11&12&12&13&14\\ 1&3&5&5&5&5&9&7&5&5&5&5&7&7&7&9&9&9&9&7&5&9&9&9&9&11&13\\ 2&5&8&8&7&6&14&9&4&6&5&4&8&7&6&10&9&8&10&5&0&8&7&6&6&9&12\\ 2&5&8&4&5&6&6&5&4&6&7&8&6&7&8&6&7&8&10&9&8&8&9&10&6&9&12\\ 3&5&7&5&5&5&7&5&3&7&7&7&7&7&7&7&7&7&11&9&7&9&9&9&7&9&11\\ 4&5&6&6&5&4&8&5&2&8&7&6&8&7&6&8&7&6&12&9&6&10&9&8&8&9&10\\ 4&9&14&6&7&8&8&5&2&8&9&10&6&7&8&4&5&6&12&9&6&6&7&8&0&5&10\\ 5&7&9&5&5&5&5&3&1&9&9&9&7&7&7&5&5&5&13&11&9&9&9&9&5&7&9\\ 6&5&4&4&3&2&2&1&0&10&9&8&8&7&6&6&5&4&14&13&12&12&11&10&10&9&8\\ 4&5&6&6&7&8&8&9&10&4&5&6&6&7&8&8&9&10&4&5&6&6&7&8&8&9&10\\ 5&5&5&7&7&7&9&9&9&5&5&5&7&7&7&9&9&9&5&5&5&7&7&7&9&9&9\\ 6&5&4&8&7&6&10&9&8&6&5&4&8&7&6&10&9&8&6&5&4&8&7&6&10&9&8\\ 6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8\\ 7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7\\ 8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6\\ 8&9&10&6&7&8&4&5&6&8&9&10&6&7&8&4&5&6&8&9&10&6&7&8&4&5&6\\ 9&9&9&7&7&7&5&5&5&9&9&9&7&7&7&5&5&5&9&9&9&7&7&7&5&5&5\\ 10&9&8&8&7&6&6&5&4&10&9&8&8&7&6&6&5&4&10&9&8&8&7&6&6&5&4\\ 8&9&10&10&11&12&12&13&14&4&5&6&6&7&8&8&9&10&0&1&2&2&3&4&4&5&6\\ 9&7&5&9&9&9&9&11&13&5&5&5&7&7&7&9&9&9&1&3&5&5&5&5&9&7&5\\ 10&5&0&8&7&6&6&9&12&6&5&4&8&7&6&10&9&8&2&5&8&8&7&6&14&9&4\\ 10&9&8&8&9&10&6&9&12&6&7&8&6&7&8&6&7&8&2&5&8&4&5&6&6&5&4\\ 11&9&7&9&9&9&7&9&11&7&7&7&7&7&7&7&7&7&3&5&7&5&5&5&7&5&3\\ 12&9&6&10&9&8&8&9&10&8&7&6&8&7&6&8&7&6&4&5&6&6&5&4&8&5&2\\ 12&9&6&6&7&8&0&5&10&8&9&10&6&7&8&4&5&6&4&9&14&6&7&8&8&5&2\\ 13&11&9&9&9&9&5&7&9&9&9&9&7&7&7&5&5&5&5&7&9&5&5&5&5&3&1\\ 14&13&12&12&11&10&10&9&8&10&9&8&8&7&6&6&5&4&6&5&4&4&3&2&2&1&0 \end{array}\right)$

[0101]

Для начала можно рассмотреть закономерности получения частичной суммы для строки вышеупомянутого латинского квадрата - одномерной последовательности $A[n]$,
для которой
$ A[i]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$

[0101]

Задан латинский квадрат в виде матрицы $M[ n,n]
$ M[i,j]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$
При необходимости можно показать пример.

Нужно получить сумму элементов частичного прямоугольника из упомянутого латинского квадрата произвольного размера, включающего в себя элемент $M[0,0]$.
Один из способов
1. Предполагаем, что произвольный элемент латинского квадрата $M[X,Y]$ представлен в двоичном виде.
2. Представляем формулу каждого разряда $M[X,Y]$ в виде арифметического полинома.
3. Произвольный разряд $X_i$ числа $X$(для $Y$ то же самое) заменяем таким образом,
что $ X_i=\frac{x_i+1}{2}$. Чтобы аргумент $X_i$ принимал значения
$0,1$, аргумент $x_i$ должен принимать значения $-1,1$.
4.Полученные полиномы нужно представить в каноническом виде - учесть,
что $x_i^2=1$, и раскрыть все скобки.
Теперь множество принимаемых произвольным аргументом $x_i$ и $y_i$
можно расширить до $[-1,0,1]$.

Вот пример функции $P[x,y]$(некоего палиндрома) получаемой в итоге для $k=3$ сообщение #658250
Как ее использовать для получения суммы элементов частичного прямоугольника из упомянутого латинского квадрата при необходимости напишу, это по сути не сложный алгоритм.
Проблема в том, насколько отличаются минимальные размеры формулы для $P[x,y]$(и как их вообще искать) от минимальных размеров формулы для $M[X,Y]$

[Xaositect]

Хмм.
$\frac{(2i + 1)(2j +1) \mathop{\mathrm{mod}} 2^{k+1} - 1}{2} = \frac{(4ij + 2i + 2j + 1) \mathop{\mathrm{mod}} 2^{k+1} - 1}{2} = \frac{(4ij + 2i + 2j) \mathop{\mathrm{mod}} 2^{k+1}}{2} = (2ij + i + j) \mathop{\mathrm{mod}} 2^{k}.$
Просуммировать это не проблема.

[0101]

Это формула для элемента.
Нужно получить сумму элементов частичного прямоугольника(не по модулю) из упомянутого латинского квадрата произвольного размера, включающего в себя элемент $M[0,0]$, т.е. некоторую сумму остатков от деления.
К примеру квадрат $[16][16]$.Края частичного прямоугольника $M[0,0]$,$M[0,7]$,$M[5,7]$,$M[5,0]$. Можно просто сложить 48 чисел. Но если будет охвачена большая область большого квадрата...

0101 в сообщении #659039 писал(а):

Для начала можно рассмотреть закономерности получения частичной суммы для строки вышеупомянутого латинского квадрата - одномерной последовательности $A[n]$,
для которой
$ A[i]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$

Тоже нужно суммировать не по модулю остатки от деления.

[Xaositect]

А, я понял в чем проблема. Проблема в модуле.
$\sum_{i = 0}^m \sum_{j = 0}^n 2ij + i + j = \frac{mn(m+2)(n+2)-mn}{2}$.
Осталось посчитать, сколько раз надо вычесть $2^k$, то есть $\sum_{i = 0}^m \sum_{j = 0}^n \lfloor \frac{2ij+i+j}{2^k} \rfloor$.
При фиксированном $i$ выражение $\frac{2ij+i+j}{2^k}$ задает линейную функцию, вычисление суммы типа $\sum_{j = 0}^n \lfloor \frac{aj + c}{b} \rfloor$ можно посмотреть в "Конкретной математике", параграф 3.5.

[0101]

Вот пример квадрата. Остатки от деления на 32.
$\left(\begin{array}{cccccccccccccccc}\\0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\1&4&7&10&13&0&3&6&9&12&15&2&5&8&11&14\\2&7&12&1&6&11&0&5&10&15&4&9&14&3&8&13\\3&10&1&8&15&6&13&4&11&2&9&0&7&14&5&12\\4&13&6&15&8&1&10&3&12&5&14&7&0&9&2&11\\5&0&11&6&1&12&7&2&13&8&3&14&9&4&15&10\\6&3&0&13&10&7&4&1&14&11&8&5&2&15&12&9\\7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\9&12&15&2&5&8&11&14&1&4&7&10&13&0&3&6\\10&15&4&9&14&3&8&13&2&7&12&1&6&11&0&5\\11&2&9&0&7&14&5&12&3&10&1&8&15&6&13&4\\12&5&14&7&0&9&2&11&4&13&6&15&8&1&10&3\\13&8&3&14&9&4&15&10&5&0&11&6&1&12&7&2\\14&11&8&5&2&15&12&9&6&3&0&13&10&7&4&1\\15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\end{array}\right)$
Прямоугольник ширина 5, высота 3 от верхнего левого угла. Сумма 73. Совпадает?
По поводу пола и потолка из "Конкретной математики" очень интересно, только с ходу не вник.

[Xaositect]

Упс, я ошибся, там верхний предел равен знаменателю дроби. Но приемы суммирования, вполне возможно, можно будет применить.

[0101]

$\sum_{j = 0}^b \lfloor \frac{aj + c}{b} \rfloor$? А если попробовать на участках $[0,2^m]$,$m<k$?

[0101]

0101 в сообщении #661392 писал(а):

$\sum_{j = 0}^b \lfloor \frac{aj + c}{b} \rfloor$? А если попробовать на участках $[0,2^m]$,$m<k$?

Это и так легко считается. Лучше говорить об участках, кратных $2^m$,$m<k$.

[0101]

Похоже, направление решения бесперспективное

[Xaositect]

Да, я тоже посидел с этими суммами, как-то они не считаются сильно быстрее, чем суммированием.