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

[Cancre]

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

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

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

Последнее меня повергает в депрессию ((

[Cancre]

Ну, нету формул и нету ...
Отрицательный результат, тоже результат.
Спасибо за участие!!

[Cancre]

Однако, меня заинтересовало, какое отношение имеет символ Лежандра к рассматриваемому ряду?

И давайте начнём с начала, так как увидел некоторые упрощения. Так же хотелось бы разобраться, где именно то слагаемое, которое нельзя выразить формулой без знака суммы? Этот момент не даёт мне покоя.

Итак, для нахождения формулы, нужно её найти для ряда

$$\sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor$$

Как мне видится, наиболее понятный способ это сделать - это взять разность рядов

$$\sum\limits_{i=1}^{n}\frac{ai}{k}-\sum\limits_{i=1}^{n}\frac{ai \bmod k}{k}$$

Первое упрощение: $\sum\limits_{i=1}^{k-1}\frac{ai \bmod k}{k}=\frac{k-1}{2}$

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

Второе упрощение для $\frac{a}{k}(\sum\limits_{j=1}^{n \bmod k}(j\, red \left\lfloor\frac{k}{a}\right\rfloor))$

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

Так как $n = n \bmod k$, то $\left\lfloor\frac{n}{k}\right\rfloor=0$

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

Где $g = (n \bmod k) \bmod \left\lfloor\frac{k}{a}\right\rfloor$
Sonic86, согласны?

[Cancre]

Для ряда $\sum\limits_{j=1}^{n \bmod k}\left\lfloor\frac{aj}{k}\right\rfloor$
$\frac{k-1}{2}\left\lfloor\frac{n \bmod k}{k}\right\rfloor = 0$
И не учтено, что необходимо так же вычитать дроби.
$r=n \bmod k$

$$\sum\limits_{j=1}^{n \bmod k}\left\lfloor\frac{aj}{k}\right\rfloor = \frac{ar(r+1)}{2k}-\sum\limits_{m=1}^{n \bmod \left\lfloor\frac{k}{a}\right\rfloor}\frac{am \bmod \left\lfloor\frac{k}{a}\right\rfloor}{k}$$

Появляется как бы ещё один уровень. Не знаю как правильно сказать.

[whitefox]

Ещё можно попробовать представить "дробную часть" в виде ряда Фурье.

[Sonic86]

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

Sonic86, согласны?

Я пока ниасилил. Вроде все норм, только 1-е вычисление никак не связано с вычислением $\operatorname{red}$. Кроме того, мне неясно, откуда вылез 2-й аргумент у $\operatorname{red}$ в

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

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

Могу пока сказать только такое:

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

Так же хотелось бы разобраться, где именно то слагаемое, которое нельзя выразить формулой без знака суммы?

Как бе такое слагаемое конкретно не определено. Потому что если бы оно было определено - $A$, то мы могли бы от балды представить $A=B+C$, где $B$ - что-нибудь левое, но вычислимое аналитически. Тогда если $A$ не выразимо, то ясно, что $C$ тоже невыразимо. И тогда встает вопрос, что "правильнее": $A$ или $C$? Т.е. невыразимость определяется сразу для класса каких-то формул, причем совершенно неясно, какой конкретный представитель из этого класса брать.

Вообще, такое ощущение, что Вы пытаетесь итерировать основную формулу. А это бесполезно - глубина итерирования неограниченна.

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

Однако, меня заинтересовало, какое отношение имеет символ Лежандра к рассматриваемому ряду?

Ну вот же:

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

http://www.mccme.ru/circles/oim/mmks/works/oganesian.pdf

Ниасилили?
Причем символ Лежандра выражается чисто через младший бит частного варианта этой суммы.

[Cancre]

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

Вообще, такое ощущение, что Вы пытаетесь итерировать основную формулу. А это бесполезно - глубина итерирования неограниченна.

Пытаюсь найти элементарный ряд.
Но даже если бы этот процесс был бы итерированием, то в виду целочисленности и конечности ряда, он не может быть не ограниченным.

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

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

Однако, меня заинтересовало, какое отношение имеет символ Лежандра к рассматриваемому ряду?

Ну вот же:

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

http://www.mccme.ru/circles/oim/mmks/works/oganesian.pdf

Ниасилили?
Причем символ Лежандра выражается чисто через младший бит частного варианта этой суммы.

Наверное не осилил, так как по прежнему не вижу связи. А фраза "младший бит частного варианта этой суммы" вводит меня в ступор.

[Sonic86]

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

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

Не Надо различать конечность и ограниченность. Например, $\gcd(x,y)$ насколько я знаю, не выражается в замкнутой форме через $x,y$, хотя остаток на каждом шаге - выражается: $r_2=x\bmod y, r_3=y\bmod r_2$ и т.п.. И число шагов, которые надо сделать для нахождения $\gcd(x,y)$, оно всегда конечно. Но оно неограниченно: не существует константы $C$, не зависящей от $x,y$, такой, что число шагов алгоритма $\leqslant C$. Именно поэтому нет замкнутой формулы для $\gcd$, однако мы можем найти такую для $\gcd(x,2), \gcd(x,3)$ и вообще $\gcd(x,k)$ для любого $k\in\mathbb{N}$.

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

Наверное не осилил, так как по прежнему не вижу связи.

Ну вот же:

ссылка писал(а):

$\left(\frac{a}{p}\right)=(-1)^{\sum\limits_{j=1}^{\frac{p-1}{2}}\left[\frac{aj}{p}\right]}$

. В числителе - наша сумма, причем у нее верхний предел конкретным образом зависит от $p$. Но так так $-1$ возводится в степень, то точное значение суммы не важно - достаточно знать ее значение по модулю 2.

[Cancre]

С каждым разом представление, как происходит процесс, всё более чёткое.
Допустим у нас есть ряд
$\frac{3}{7}+\frac{6}{7}+\frac{2}{7}+\frac{5}{7}+\frac{1}{7}+\frac{4}{7}$
Его можно представить в виде
$(\frac{3}{7}-\frac{0}{7})+(\frac{6}{7}-\frac{0}{7})+(\frac{3}{7}-\frac{1}{7})+(\frac{6}{7}-\frac{1}{7})+(\frac{3}{7}-\frac{2}{7})+(\frac{6}{7}-\frac{2}{7})$
$\frac{3}{7}+\frac{6}{7}$ - есть повторяющаяся часть ряда $\frac{a}{k}\sum\limits_{j=1}^{n \bmod k}(j\, red \left\lfloor\frac{k}{a}\right\rfloor) $
$-\frac{0}{7}-\frac{0}{7}-\frac{1}{7}-\frac{1}{7}-\frac{2}{7}-\frac{2}{7}$ - есть ряд

$$\frac{1}{k}(a\left\lfloor\frac{k}{a}\right\rfloor-k)\sum\limits_{m=0}^{(n \bmod k)-1}\left\lfloor\frac{m}{\left\lfloor\frac{k}{a}\right\rfloor}\right\rfloor$$

При этом числитель в $\frac{1}{7}$ - есть разность $(a\left\lfloor\frac{k}{a}\right\rfloor-k)$

Но уже известно, что $\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}$

Осталось совместить
$r = n \bmod k$

$$\sum\limits_{m=0}^{(n \bmod k)-1}\left\lfloor\frac{m}{\left\lfloor\frac{k}{a}\right\rfloor}\right\rfloor = \frac{r(r-1)}{2\left\lfloor\frac{k}{a}\right\rfloor}-\frac{\left\lfloor\frac{k}{a}\right\rfloor-1}{2}\left\lfloor\frac{r-1}{\left\lfloor\frac{k}{a}\right\rfloor}\right\rfloor-\frac{((r-1) \bmod \left\lfloor\frac{k}{a}\right\rfloor)((r-1) \bmod \left\lfloor\frac{k}{a}\right\rfloor+1)}{2k}$$

Наверняка где-то что-то не то, но надеюсь, мысль донёс.

[Sonic86]

Не, это просто продолжение неизвестно откуда взявшегося вычисления, опять же, зачем столько букв было плодить, ежели можно было обозначить $[k/a]=q$.

Все-таки давайте разберемся с обрывом:

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

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

До сюда я дошел, тут все понятно.

А дальше:

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

Второе упрощение для $\frac{a}{k}\sum\limits_{j=1}^{n \bmod k}j\, red \left\lfloor\frac{k}{a}\right\rfloor$

Вот это все откуда вылезло? Как оно связано с предыдущим вычислением? Вы пользовались этим?:

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

для $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$$

[Cancre]

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

[...]
До сюда я дошел, тут все понятно.

Значит, так же понятно, что проблема в хвостике ряда, который нужно просумировать.

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

А дальше:

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

Второе упрощение для $\frac{a}{k}\sum\limits_{j=1}^{n \bmod k}j\, red \left\lfloor\frac{k}{a}\right\rfloor$

Вот это все откуда вылезло?

Как я понял, никто ещё суммировать остатки не умеет, иначе бы была бы известна формула.
Но равномерно возрастающие линейные последовательности мы суммировать умеем. Вот, выразить хвостик через линейные возрастающие кусочки и надо. И если получится, то получим формулу.
В приведённом конкретном примере:

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

Допустим у нас есть ряд
$\frac{3}{7}+\frac{6}{7}+\frac{2}{7}+\frac{5}{7}+\frac{1}{7}+\frac{4}{7}$
Его можно представить в виде
$(\frac{3}{7}-\frac{0}{7})+(\frac{6}{7}-\frac{0}{7})+(\frac{3}{7}-\frac{1}{7})+(\frac{6}{7}-\frac{1}{7})+(\frac{3}{7}-\frac{2}{7})+(\frac{6}{7}-\frac{2}{7})$
$\frac{3}{7}+\frac{6}{7}$ - есть повторяющаяся часть ряда $\frac{a}{k}\sum\limits_{j=1}^{n \bmod k}(j\, red \left\lfloor\frac{k}{a}\right\rfloor) $

Если убрать множитель $\frac{a}{k}$ , то только начальная элементарная часть и будет.
С этим моментом как?...

Кстати, наверное проще находить ряд \sum\limits_{i=1}^{n}(ai \bmod k), а не \sum\limits_{i=1}^{n}\left\lfloor\frac{ai}{k}\right\rfloor из-за того, что в первом случае не нужно ничего сложного вычитать.

[Sonic86]

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

Вот, выразить хвостик через линейные возрастающие кусочки и надо. И если получится, то получим формулу.

А где ответ-то? Ответа я не получил.

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

С этим моментом как?...

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

[Cancre]

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

Просто я пока не понимаю, зачем это надо.

Ну, хорошо, а как ещё выразить, например, последовательность {1, 2, 1, 2, 1, 2, ...} ?

[Sonic86]

Да выразить-то можно, хоть через этот Ваш $\operatorname{red}$.
Проблема в том, что отношение этого к исходному вычислению неясно. Я Вам предлагаю написать это ясно. 3-й раз уже предлагаю. И, пожалуй, в последний.

[Cancre]

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

Да выразить-то можно, хоть через этот Ваш $\operatorname{red}$.
Проблема в том, что отношение этого к исходному вычислению неясно.

Как буд-то у меня сразу готовые ответы появляются. Сначала идеи. Они могут быть ошибочны. Но вы же сами писали

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

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

Что, собственно, и пытаюсь сделать. Разбиваю на более мелкие "отрезки".

Упрощающие обозначения:

$\alpha = \left\lfloor\frac{k}{a}\right\rfloor$

$r= n \bmod k$

$\nu=\left\lfloor\frac{r-1}{\alpha}\right\rfloor$

$q=(r-1) \bmod \alpha$

$ x \operatorname {red} y = \begin{cases} x \bmod y,&\text{если y не делит x;}\\ y,&\text{если y делит x;}\\ 0,&\text{если x=0;} \end{cases}$

$$\sum\limits_{j=1}^{n}(aj \bmod k)=\frac{ak(k+1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+ a( \sum\limits_{j=1}^{\nu}\frac{\alpha(\alpha+1)}{2}+\sum\limits_{j=1}^{r \bmod \alpha}(j \,red\,\alpha))+(a\alpha-k)\sum\limits_{j=0}^{r-1}\left\lfloor\frac{j}{\alpha}\right\rfloor=$$

$$=\frac{ak(k+1)}{2}\left\lfloor\frac{n}{k}\right\rfloor+a(\nu\cdot\frac{\alpha(\alpha+1)}{2}+\frac{(r\,red\,\alpha)((r\,red\,\alpha)+1)}{2})+(a\alpha-k)(\frac{r(r-1)}{2\alpha}-\frac{\alpha-1}{2}\left\lfloor\frac{r-1}{\alpha}\right\rfloor-\frac{q(q+1)}{2\alpha})$$

Но с последним слагаемым (где q) не всё в порядке, на нём накапливается ошибка при увеличении n на кратность tk. Может ряд $\sum\limits_{j=0}^{r-1}\left\lfloor\frac{j}{\alpha}\right\rfloor$ нужно находить по другому.