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

[Cancre]

Нужно найти общую формулу суммы для ряда \sum\limits_{i=1}^{n}(ai \bmod k) при \forall(k\in\mathbb{N}; a\in\mathbb{N})
С более простым рядом проблем не возникло
\sum\limits_{i=1}^{n}(i \bmod k)=\frac{k(k-1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+\frac{(n\bmod k)((n\bmod k)+1)}{2}
И где можно о таких рядах почитать?

[ewert]

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

\sum\limits_{i=1}^{n}(ai \bmod k) при \forall(k\in\mathbb{N}; a\in\mathbb{N})

(это что-то из Блока: "Я послал тебе чёрную розу в бокале...")

$(ai \bmod k)=((a\bmod k)\cdot(i \bmod k))\bmod k$ и т.д.

[Cancre]

ewert в сообщении #1086374 писал(а):

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

\sum\limits_{i=1}^{n}(ai \bmod k) при \forall(k\in\mathbb{N}; a\in\mathbb{N})

(это что-то из Блока: "Я послал тебе чёрную розу в бокале...")

$(ai \bmod k)=((a\bmod k)\cdot(i \bmod k))\bmod k$ и т.д.

Мне известно это свойство, а вот "и т.д." очень загадочно ...

[ewert]

Ну вынесите самый правый мод за знак суммы, потом из-под неё первый сомножитель, потом ещё чего.

[Cancre]

ewert в сообщении #1086386 писал(а):

Ну вынесите самый правый мод за знак суммы, потом из-под неё первый сомножитель, потом ещё чего.

Может я ооочень сильно туплю, как всегда, но не понимаю как можно вынести mod за знак суммы, чтобы не получилась ерунда. По какому правилу он выносится? Здесь у меня видимо пробел в знаниях.
Вот, то что имеем

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

И чтобы что-то вынести без потери целостности, моя фантазия пасует.

[provincialka]

Не число же выносить! А сам знак сравнения! То есть сначала просуммировать, а потом уж взять остаток

[Cancre]

provincialka в сообщении #1086421 писал(а):

Не число же выносить! А сам знак сравнения! То есть сначала просуммировать, а потом уж взять остаток

Так?

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

[provincialka]

Ага! И дальше по алгоритму, указанному ewert

[Cancre]

provincialka в сообщении #1086423 писал(а):

Ага! И дальше по алгоритму, указанному ewert

Но здесь же нет равенства
между

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

и

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

Кстати, где значёк неравенства? Не нашёл.

[Sonic86]

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

Нужно найти общую формулу суммы для ряда \sum\limits_{i=1}^{n}(ai \bmod k) при \forall(k\in\mathbb{N}; a\in\mathbb{N})
С более простым рядом проблем не возникло
\sum\limits_{i=1}^{n}(i \bmod k)=\frac{k(k-1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+\frac{(n\bmod k)((n\bmod k)+1)}{2}
И где можно о таких рядах почитать?

Можно разбить отрезок $[1;n]$ на отрезки длины $k$ - тогда все сведется к рассмотрению суммы с $n<k$. Далее можно попытаться разбить отрезок на более мелкие отрезки размера $\approx \frac{k}{a}$ - на них можно снять целую часть и явно просуммировать. Для начала можно рассмотреть простые случаи типа $a=2;3$ .
Можно попытаться воспользоваться соотношением $a \bmod b = a-b\left[\frac{a}{b}\right]$.
Но ответа я не знаю - думать надо часа 2, а времени мне не дадут.

ewert в сообщении #1086386 писал(а):

Ну вынесите самый правый мод за знак суммы, потом из-под неё первый сомножитель, потом ещё чего.

Неправильно: если вынести $\bmod$ за знак суммы, то получим выражение меньше модуля, в то время как очевидно, что сумма не ограниченна.

[Cancre]

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

Можно попытаться воспользоваться соотношением $a \bmod b = a-b\left[\frac{a}{b}\right]$.

А в этом что-то есть!
\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\cdot\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor

[Cancre]

Чтоб было попроще и не ошибиться сначала найду сумму ряда
$\sum\limits_{i=1}^{n}\left\lfloor\frac{i}{k}\right\rfloor$
В качестве наглядного примера выпишем все члены ряда $\sum\limits_{i=1}^{10}\left\lfloor\frac{i}{4}\right\rfloor$
$(\left\lfloor\frac{1}{4}\right\rfloor+\left\lfloor\frac{2}{4}\right\rfloor+\left\lfloor\frac{3}{4}\right\rfloor)+\left\lfloor\frac{4}{4}\right\rfloor+(\left\lfloor\frac{5}{4}\right\rfloor+\left\lfloor\frac{6}{4}\right\rfloor+\left\lfloor\frac{7}{4}\right\rfloor)+\left\lfloor\frac{8}{4}\right\rfloor+\left\lbrace\left\lfloor\frac{9}{4}\right\rfloor+\left\lfloor\frac{10}{4}\right\rfloor\right\rbrace$

Выделенные круглыми скобками части периодически повторяются. Сумма элементарной дробной части, т.е. (1/4 + 2/4 + 3/4), в общем виде находится
$\frac{\sum\limits_{i=1}^{k-1}i}{k}=\frac{\frac{k(k-1)}{2}}{k}=\frac{k-1}{2}$

Соответственно, сумма всех полных элементарных дробных частей будет
$\frac{k-1}{2} \left\lfloor\frac{n}{k}\right\rfloor$

Но возможна не полная часть, выделенная фигурными скобками. Эта не полная часть ищется, так же как и элементарная, но берутся остатки. Обозначим n mod k = r
$\frac{\sum\limits_{i=1}^{r}i}{k}=\frac{r(r+1)}{2k}$

Теперь из суммы обычного (не целых частей) ряда вычтем дробные части и получим
$\sum\limits_{i=1}^{n}\left\lfloor\frac{i}{k}\right\rfloor=\frac{n(n+1)}{2k}-\frac{k-1}{2}$\left\lfloor\frac{n}{k}\right\rfloor-\frac{r(r+1)}{2k}$

Теперь что-то в этом роде нужно проделать с $\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor$
Будет ли верным?
$\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor=\frac{an(n+1)}{2k}-\frac{a(k-1)}{2}$\left\lfloor\frac{an}{k}\right\rfloor-\frac{ar(r+1)}{2k}$

[Sonic86]

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

Выделенные круглыми скобками части периодически повторяются.

Угу, $\left[\frac{4}{4}\right]$ и $\left[\frac{8}{4}\right]$ можно тоже включить в круглые скобки - они туда органично вписываются.
Впрочем, это все самый простой случай.

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

Эта не полная часть ищется, так же как и элементарная, но берутся остатки.

Только в случае $a=1$ все получается так просто за один шаг. Для $a=2$ понадобится 2 шага и один if, для $a=3$ - 3 шага. В общем случае я пока не вижу.

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

Теперь из суммы обычного (не целых частей) ряда вычтем дробные части и получим
$\sum\limits_{i=1}^{n}\left\lfloor\frac{i}{k}\right\rfloor=\frac{n(n+1)}{2k}-\frac{k-1}{2}\left\lfloor\frac{n}{k}\right\rfloor-\frac{r(r+1)}{2k}$

Теперь что-то в этом роде нужно проделать с $\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor$
Будет ли верным?
$\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor=\frac{an(n+1)}{2k}-\frac{a(k-1)}{2}\left\lfloor\frac{an}{k}\right\rfloor-\frac{ar(r+1)}{2k}$

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

У меня пока руки не дошли. В четверг м.б. дойдут.

[Cancre]

$\sum\limits_{i=1}^{n}\left\lfloor\frac{i}{k}\right\rfloor=\frac{n(n+1)}{2k}-\frac{k-1}{2}$\left\lfloor\frac{n}{k}\right\rfloor-\frac{r(r+1)}{2k}$
Найденное решение не единственно,так как результат может быть получен другим способом. В основу может быть положен так же ряд 0+1+2+3+4.+…
В примере это будет выглядеть так: 0+0+0+0+1+1+1+1+2+2+2
В этом случае из суммы 0+0+0+0+1+1+1+1+2+2+2+2 +... нужно вычесть недостающую часть
$\sum\limits_{i=1}^{n}\left\lfloor\frac{i}{k}\right\rfloor=\frac{k\left\lfloor\frac{n}{k}\right\rfloor(\left\lfloor\frac{n}{k}\right\rfloor+1)}{2}-\left\lfloor\frac{n}{k}\right\rfloor(k-r-1) , где r = n mod k

[Andrey A]

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

И где можно о таких рядах почитать?

Посмотрите формулу в конце начального поста http://dxdy.ru/post1049459.html#p1049459. Может пригодится. Там $t_n=\frac{n(n+1)}{2}.$