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

[0101]

Насчет упрощения полиномов от 3-значных переменных идея в принципе перспективная. Однако проблемы следующие:
1. Мало литературы. Бухбергер в этом плане в основном работал. Но под упрощением он подразумевает обычно как раз приведение к каноническому виду, что в данном случае бесполезно.
2. Стандартные методы минимизации булевых уравнений тут тоже мало полезны, так как не могут учесть свойств конкретных полиномов.
3. Как учесть свойства конкретных полиномов с точки зрения минимизации.
Пытаюсь еще усмотреть нечто в палиндромах типа сообщение #658250 которые являются табличным представлением полиномов и наверняка обладают какими-то нужными свойствами.

[0101]

Все таки Xaositect вывел из тупика. По крайней мере для поиска суммы типа $\sum_{j = 0}^x(( j\cdot y )\mod z)$, $y<z$
для одномерной последовательности.
Идея очевидная, ее может еще Гаусс или Эйлер знали. Переходим от остатков к полам, от полов к остаткам и т.д. с уменьшением модуля, пока до единицы не дойдем. Только формула громоздкая получается, цепная дробь. Намного проще рукописный текст сфотографировать, чем в тексе набирать. Количество элементов в формуле зависит от $y$.
И под большим вопросом двумерный случай.
Может быть, если эту идею найти у кого-то типа Эйлера или Гаусса, там и обобщение на двумерный случай найдется?

[0101]

Пытаюсь выразить идею без цепной дроби.

$\sum_{j = 0}^x(( j\cdot y )\mod z)=\sum_{j = 0}^xj\cdot y-\sum_{j = 0}^n\Delta S_j $

$\sum_{j = 0}^x(( j\cdot y )\mod z)$ - сумма остатков

$\sum_{j = 0}^xj\cdot y$ - cумма арифметической прогрессии

$\sum_{j = 0}^n\Delta S_j $ - сумма полосок полов

$y<z$

$n= \lfloor\frac{x\cdot y}{z} \rfloor $ - длина самой длинной полоски, деленная на $z$

Площадь отдельной полоски

$\Delta S_j= j\cdot z\cdot(\lfloor\frac{j\cdot z}{y} \rfloor- \lfloor\frac{(j-1)\cdot z}{y} \rfloor) $

поэтому

$\sum_{j = 0}^n\Delta S_j= z( n\lfloor\frac{n\cdot z}{y} \rfloor- \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor )$.

$\lfloor\frac{j\cdot z}{y} \rfloor=\frac{j\cdot z-((j\cdot z)\mod y)}{y}$,

поэтому

$ \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor =\frac{ \sum_{j = 0}^{n-1}j\cdot z- \sum_{j = 0}^{n-1}((j\cdot z)\mod y)}{y}$

Теперь нужно думать, что делать с суммой остатков

$\sum_{j = 0}^{n-1}((j\cdot z)\mod y)$

Поскольку $z>y$
$j\cdot z \mod y =( j( z \mod y))\mod y$

$Z= z \mod y$

$\sum_{j = 0}^{n-1}((j\cdot z)\mod y) = \sum_{j = 0}^{n-1}((j\cdot Z)\mod y)$

$Z<y$

Будем представлять сумму остатков $\sum_{j = 0}^{n-1}((j\cdot Z)\mod y)$ согласно выше написанному.

И т.д.

[0101]

Эту часть

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

$\lfloor\frac{j\cdot z}{y} \rfloor=\frac{j\cdot z-((j\cdot z)\mod y)}{y}$,

поэтому

$ \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor =\frac{ \sum_{j = 0}^{n-1}j\cdot z- \sum_{j = 0}^{n-1}((j\cdot z)\mod y)}{y}$

Теперь нужно думать, что делать с суммой остатков

$\sum_{j = 0}^{n-1}((j\cdot z)\mod y)$

Поскольку $z>y$
$j\cdot z \mod y =( j( z \mod y))\mod y$

$Z= z \mod y$

$\sum_{j = 0}^{n-1}((j\cdot z)\mod y) = \sum_{j = 0}^{n-1}((j\cdot Z)\mod y)$

$Z<y$

Будем представлять сумму остатков $\sum_{j = 0}^{n-1}((j\cdot Z)\mod y)$ согласно выше написанному.

И т.д.

можно представить в лучшем виде, а именно:

Цитата:

Поскольку $z>y$

$ \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor = \lfloor\frac{z}{y} \rfloor\sum_{j = 0}^{n-1}j + \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot Z}{y} \rfloor$

$Z= z\mod y$ , $Z<y$

Будем представлять сумму $\sum_{j = 0}^{n-1}\lfloor\frac{j\cdot Z}{y} \rfloor$ согласно выше написанному как сумму полосок полов.

И т.д.

[0101]

В еще лучшей редакции

$\sum_{j = 0}^x(( j\cdot y )\mod z)=\sum_{j = 0}^xj\cdot y-\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor$

$x, y<z$

$\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor=\sum_{j = 0}^n\Delta S_j$

$\sum_{j = 0}^n\Delta S_j $ - сумма полосок полов

$n= \lfloor\frac{x\cdot y}{z} \rfloor $ - длина самой длинной полоски, деленная на $z$

Площадь отдельной полоски

$\Delta S_j= j\cdot z\cdot(\lfloor\frac{j\cdot z}{y} \rfloor- \lfloor\frac{(j-1)\cdot z}{y} \rfloor) $

поэтому

$\sum_{j = 0}^n\Delta S_j= z( n\lfloor\frac{n\cdot z}{y} \rfloor- \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor )$.

Поскольку $z>y$

$ \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot z}{y} \rfloor = \lfloor\frac{z}{y} \rfloor\sum_{j = 0}^{n-1}j + \sum_{j = 0}^{n-1}\lfloor\frac{j\cdot Z}{y} \rfloor$

$Z= z\mod y$ , $Z<y$

Будем представлять сумму $\sum_{j = 0}^{n-1}\lfloor\frac{j\cdot Z}{y} \rfloor$ согласно выше написанному как сумму полосок полов.

И т.д.

А вот что делать с \sum_{i = 0}^{y}\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor$? Кто-нибудь кроме Р. Грэхема, Д. Кнута, О. Паташника вникал в вопрос?

[0101]

Ошибка в формуле. В исправленном виде

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

А вот что делать с \sum_{i = 0}^{y}\sum_{j = 0}^{x}\lfloor\frac{j\cdot i}{z} \rfloor$? Кто-нибудь кроме Р. Грэхема, Д. Кнута, О. Паташника вникал в вопрос?

[0101]

Потерялась площадь самой длинной полоски, поэтому внесены небольшие исправления

$\sum_{j = 0}^x(( j\cdot y )\mod z)=\sum_{j = 0}^xj\cdot y-\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor$

$x, y<z$

$\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor=\sum_{j = 0}^n\Delta S_j$

$\sum_{j = 0}^n\Delta S_j $ - сумма полосок полов

$n= \lfloor\frac{x\cdot y}{z} \rfloor $ - длина самой длинной полоски, деленная на $z$

Площадь отдельной полоски

$\Delta S_j= j\cdot z\cdot(\lfloor\frac{j\cdot z}{y} \rfloor- \lfloor\frac{(j-1)\cdot z}{y} \rfloor) $

поэтому

$\sum_{j = 0}^n\Delta S_j= z( x\cdot n - \sum_{j = 0}^{n}\lfloor\frac{j\cdot z}{y} \rfloor )$.

Поскольку $z>y$

$ \sum_{j = 0}^{n}\lfloor\frac{j\cdot z}{y} \rfloor = \lfloor\frac{z}{y} \rfloor\sum_{j = 0}^{n}j + \sum_{j = 0}^{n}\lfloor\frac{j\cdot Z}{y} \rfloor$

$Z= z\mod y$ , $Z<y$

Будем представлять сумму $\sum_{j = 0}^{n}\lfloor\frac{j\cdot Z}{y} \rfloor$ согласно выше написанному как сумму полосок полов.

И т.д.

Для двумерного случая нужно рассмотреть суммы типа $ \sum_{i = 0}^{y}(\lfloor\frac{z}{i} \rfloor\lfloor\frac{x\cdot i}{z} \rfloor)$,$ \sum_{i = 0}^{y}(\lfloor\frac{z}{i} \rfloor\lfloor\frac{x\cdot i}{z} \rfloor^2)$

[0101]

Еще одно важное исправление

$\sum_{j = 0}^x(( j\cdot y )\mod z)=\sum_{j = 0}^xj\cdot y-z\cdot\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor$

$x, y<z$

$\sum_{j = 0}^{x}\lfloor\frac{j\cdot y}{z} \rfloor=\sum_{j = 0}^n\Delta S_j$ - сумма полосок полов

$n= \lfloor\frac{x\cdot y}{z} \rfloor $ - длина самой длинной полоски
Площадь отдельной полоски

$\Delta S_j= j\cdot (\lfloor\frac{j\cdot z}{y} \rfloor- \lfloor\frac{(j-1)\cdot z}{y} \rfloor) $

поэтому

$\sum_{j = 0}^n\Delta S_j= x\cdot n - \sum_{j = 0}^{n}\lfloor\frac{j\cdot z}{y} \rfloor $.

Поскольку $z>y$

$ \sum_{j = 0}^{n}\lfloor\frac{j\cdot z}{y} \rfloor = \lfloor\frac{z}{y} \rfloor\sum_{j = 0}^{n}j + \sum_{j = 0}^{n}\lfloor\frac{j\cdot Z}{y} \rfloor$

$Z= z\mod y$ , $Z<y$

Будем представлять сумму $\sum_{j = 0}^{n}\lfloor\frac{j\cdot Z}{y} \rfloor$ согласно выше написанному как сумму полосок полов.

И т.д.

-- Ср янв 16, 2013 19:41:02 --

Как получить сумму типа $ \sum_{i = 1}^{y_0}(\lfloor\frac{x\cdot z}{i} \rfloor)$? Как эта сумма называется? Натуральный логарифм для непрерывного случая, а это дискретный. Но то, что называется дискретным логарифмом, явно не оно. Думается, классическое что-то, но нигде такого не видел.