Сумма остатков

[Cancre]

Sonic86 в сообщении #1086570 писал(а):

Если Вы действуете здесь чисто индуктивно, то нет, скорее всего неверно, формула здесь неочевидна. Ясен будет только главный член $\int\limits_1^n \left\lfloor\frac{ax}{k}\right\rfloor dx$. Можете взять его для самоконтроля, но это не сильно поможет - все равно он сократится.

Формула с а не верна, что не удивляет.
Первое, что видится, это нужно найти количество разных образующихся остатков. В самом простом случае остатков k, но может быть и меньше при различных k и a. Так при k=4 а=6 остатков всего две штуки 0 и 2.
Второе, оказывается важным для вычисления суммы не полного "элементарного дробного ряда" в конечной части всего ряда, какой именно остаток в "элементарном дробном ряде" первый, и он, естественным образом, равен r1= a mod k (i=1) в рассматриваемом ряде$\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor$
Вот, где-то такое моё понимание.

[Cancre]

Тут ещё немного поразмышлял и вот что нафантазировал.
Если первый остаток не делит k, то количество остатков равно k.
Если же первый остаток делит k, то количество остатков равно результату деления.
Можно ввести обобщённую функцию
$\tilde{\mathfrak{Q}}(a\mod k)=\begin{cases} k,&\text{если $(a\mod k)\bar{\mid} k$;}\\ \frac{k}{a\mod k},&\text{если $(a\mod k)\mid k$;} \end{cases}$

[Sonic86]

(Оффтоп)

Cancre в сообщении #1086951 писал(а):

Можно ввести обобщённую функцию
$\tilde{\mathfrak{Q}}(a\mod k)$

зачем такие страшные буквы писать?

Cancre в сообщении #1086510 писал(а):

$\sum\limits_{i=1}^{n}(ai \bmod k)=\sum\limits_{i=1}^{n}(ai-k\left[\frac{ai}{k}\right])=\frac{an}{2}(n+1)-k\sum\limits_{i=1}^{n}\left[\frac{ai}{k}\right]$

Ясно, что общий случай сводится к случаю $a<k, n<k, \gcd(a,k)=1$
$\sum\limits_{j=1}^n\left[\frac{aj}{k}\right]$ геометрически $=ak-\sum\limits_{j=1}^n\left[\frac{kj}{a}\right]+D$, $D$ - число квадратов, через которые проходит диагональ, значит $D=k+a-1$. А т.к.$k>a$, то мы можем отщепить от суммы одно слагаемое и снова прийти к предыдущему случаю. Значит все это можно рекуррентно раскрутить.
http://www.mccme.ru/circles/oim/mmks/wo ... nesian.pdf

[Sonic86]

(Оффтоп)

поскольку эту курсовую никто читать не будет, я волен здесь написать любую ахинею, так что сердечник трансформатора сделаем из дерева

Правильная формула такая: для $n < k, a<k, \ m:=\left\lceil\frac{a}{k}(n+1)\right\rceil$ имеем

$$\sum\limits_{j=1}^n\left[\frac{aj}{k}\right]+\sum\limits_{j=1}^m\left[\frac{kj}{a}\right]=mn$$

Доказательство очевидно.
Отсюда легко строится быстрый алгоритм расчета сумм вида $\sum\limits_{j=1}^n\left[\frac{aj}{k}\right]$. Подставляя $\sum\limits_{j=1}^n\left[\frac{aj}{k}\right]=\sum\limits_{j=1}^n\frac{aj}{k}-\sum\limits_{j=1}^n\frac{aj\bmod k}{k}$, мы можем получить аналогичную, но более страшную, формулу и для $\sum\limits_{j=1}^n aj\bmod k$.

[Cancre]

С новым годом!
Во-первых, спасибо, что уделили время на данную тему, прочитал, поразмышлял.
Во-вторых, мало чего понял.
Какой смысл находить рекурентную форму, если требуется закрытая форма?
Ещё меня смутили условия.
В третьих, (оффтоп) буковки красивые. Но по сути это НОД, поэтому нафиг что-то вводить новое, это результат размышлений после новогодней ночи )))
А результат праздников таков:

$$\sum\limits_{i=1}^{n}(ai \bmod k)= \frac{k}{2}(\frac{k}{gdc(a,k)}-1)\left\lfloor\frac{n\cdot gdc(a,k)}{k}\right\rfloor+\sum\limits_{j=1}^{n \bmod k}((a \bmod k)j \bmod k)$$

Конечная не полная часть ряда

$$ \sum\limits_{j=1}^{n \bmod k}((a \bmod k)j \bmod k)$$

в обычную формулу переводиться не хочет. В связи с этим вопрос: Возможна ли здесь, вообще, закрытая форма?

[Sonic86]

Cancre в сообщении #1089164 писал(а):

В связи с этим вопрос: Возможна ли здесь, вообще, закрытая форма?

Спросить легко, ответить трудно. Ее легко может и не быть. У $\gcd(a,b)$ уже нет замкнутой формы.

Cancre в сообщении #1089164 писал(а):

Какой смысл находить рекурентную форму, если требуется закрытая форма?

Ну попробуйте ее найти, особенно с учетом того, что ее может не быть.

[Cancre]

Sonic86 в сообщении #1089184 писал(а):

Ну попробуйте ее найти, особенно с учетом того, что ее может не быть.

Могу точно сказать, что формула существует и, в принципе, её нашёл. Осталось её проверить на возможные мелкие неточности. Формула большая, но ничего особенного не содержит. )

[Sonic86]

Просьба показать.

[Cancre]

Как всегда дьявол кроется в мелочах. Приходится исправлять. Надеюсь, исправление не затянется на долго.

[Cancre]

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

Итак, нужно выразить конечную не полную часть ряда

$$ \sum\limits_{j=1}^{n \bmod k}((a \bmod k)j \bmod k)$$

В основе лежит последовательность

$$(a \bmod k)j $$

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

$$ j=\left\lfloor k/(a \bmod k)\right\rfloor$$

а затем переходит на значение

$$ (a \bmod k)\left\lfloor k/(a \bmod k) \right\rfloor-k+(a \bmod k)$$

в следующем цикле значение будет

$$2(a \bmod k)\left\lfloor k/(a \bmod k)\right\rfloor-2k+(a \bmod k)$$

и т.д.

$$\lambda(a \bmod k)\left\lfloor k/(a \bmod k)\right\rfloor-\lambda k+(a \bmod k)$$

До тех пор пока все остатки не пробегут k значений. Значения $\lambda$ очевидно определяются, как

$$ \lambda=\left\lfloor(a \bmod k)j/k\right\rfloor $$

Обозначив $r = a \bmod k$
Составляется следующая сумма
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)\oplus(r\left\lfloor\frac{rj}{k}\right\rfloor\left\lfloor\frac{k}{r}\right\rfloor - k\left\lfloor\frac{rj}{k}\right\rfloor))$
$\oplus$ - означает плюс, но суммировать отдельно левые скобки и отдельно правые нельзя.
red - редукция

Тут ещё проблемка в наборе формул. Формула получается слишком громоздкой.

[Sonic86]

Я в конце Ваш пост перепишу покороче и тогда проверю.
А пока: что такое $\oplus$ и $\operatorname{red}$? Без определения этих символов формула смысла не имеет.

Cancre в сообщении #1090841 писал(а):

Итак, нужно выразить конечную не полную часть ряда

$$ \sum\limits_{j=1}^{n \bmod k}((a \bmod k)j \bmod k)$$

Я так понимаю, Вы прогер, потому я Вам предлагаю не плодить код копипастом, что некошерно (https://ru.wikipedia.org/wiki/Don%E2%80 ... t_yourself), а завести новую переменную $a\bmod k = A$ (или любая другая милая сердцу буква) или просто ограничится рассмотрением случая $n,a<k$.
Сделайте, пожалуйста, рефакторинг После него проблема

Cancre в сообщении #1090841 писал(а):

Формула получается слишком громоздкой.

может просто отпасть

[Cancre]

Обозначив $r = a \bmod k$
$ a \operatorname {red} b = \begin{cases} a \bmod b,&\text{если b не делит a;}\\ b,&\text{если b делит a;} \end{cases}$

Составляется следующая сумма
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)\oplus\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k))$
Смысл $\oplus $ в том, что
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)+\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k))\ne \sum\limits_{j=1}^{n \bmod k}r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)+ \sum\limits_{j=1}^{n \bmod k}\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k)$

[Sonic86]

Cancre в сообщении #1090991 писал(а):

Обозначив $r = a \bmod k$
$ a \operatorname {red} b = \begin{cases} a \bmod b,&\text{если b не делит a;}\\ b,&\text{если b делит a;} \end{cases}$

Ясно: $ a \operatorname {red} b = a\bmod b +b[b|a]$

Cancre в сообщении #1090991 писал(а):

Составляется следующая сумма
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)\oplus\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k))$
Смысл $\oplus $ в том, что
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)+\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k))\ne \sum\limits_{j=1}^{n \bmod k}r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)+ \sum\limits_{j=1}^{n \bmod k}\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k)$

сами понимаете

[Cancre]

Внутри суммы всё впорядке
$\sum\limits_{j=1}^{n \bmod k}(r(j \, red \left\lfloor \frac{k}{r}\right\rfloor)+\left\lfloor\frac{rj}{k}\right\rfloor(r\left\lfloor\frac{k}{r}\right\rfloor - k))$
Пришлось таблицу промежуточных результатов составлять, чтоб разобраться.

Сумма от редукции легко находится, что очень приятно:

$$\sum\limits_{i=1}^{n}(i \, red \, k) = \frac{k(k+1)}{2}\left\lfloor\frac{n}{k}\right\rfloor + \frac{(n \bmod k)((n \bmod k)+1)}{2}$$

Дополнительно обозначу через
$r_e = n \bmod k$
$\tilde{r} = \left\lfloor\frac{k}{r}\right\rfloor$
И получается не маленькая формула

$$\sum\limits_{j=1}^{r_e}(rj \bmod k)=\frac{r\tilde{r}(\tilde{r}+1)}{2}\left\lfloor\frac{r_e}{k}\right\rfloor+\frac{r(r_e \bmod \tilde{r})((r_e \bmod \tilde{r})+1)}{2}+$$

$$+(r\tilde{r}-k)(\frac{rr_e(r_e+1)}{2k}-\frac{1}{2}(\frac{k}{gcd(r,k)}-1)\left\lfloor\frac{r_e\cdot gcd(r,k)}{k}\right\rfloor)$$

[Sonic86]

Cancre в сообщении #1091143 писал(а):

И получается не маленькая формула

$$\sum\limits_{j=1}^{r_e}(rj \bmod k)=\frac{r\tilde{r}(\tilde{r}+1)}{2}\left\lfloor\frac{r_e}{k}\right\rfloor+\frac{r(r_e \bmod \tilde{r})((r_e \bmod \tilde{r})+1)}{2}+$$

$$+(r\tilde{r}-k)(\frac{rr_e(r_e+1)}{2k}-\frac{1}{2}(\frac{k}{gcd(r,k)}-1)\left\lfloor\frac{r_e\cdot gcd(r,k)}{k}\right\rfloor)$$

Формула неверна, поскольку $(r\tilde{r}-k)\frac{rr_e(r_e+1)}{2k}$ не обязано быть целым (проверял на компе для $a=3, n=13, k=20$).(Вы так же зачем-то обозначили $a$ через $r$ - тоже не комильфо, я пишу по прежнему $a$).

Опять же: чтобы не усложнять, рассматривайте $n:n<k$ и $\gcd(a,k)=1$ - меньше буковок, а случай вполне общий.

И я опять же хочу сказать: вот сейчас мы символ Лежандра можем считать бинарным возведением в степень допустим за $O(\ln ^2p)$. Если бы формула существовала, то мы бы могли его считать за $O(1)$, что сильнее, потому подозрительнее.