2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Сумма остатков
Сообщение28.12.2015, 00:36 
Нужно найти общую формулу суммы для ряда \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}
И где можно о таких рядах почитать?

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 00:55 
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$ и т.д.

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 01:05 
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$ и т.д.

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

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

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 04:16 
ewert в сообщении #1086386 писал(а):
Ну вынесите самый правый мод за знак суммы, потом из-под неё первый сомножитель, потом ещё чего.

Может я ооочень сильно туплю, как всегда, но не понимаю как можно вынести mod за знак суммы, чтобы не получилась ерунда. По какому правилу он выносится? Здесь у меня видимо пробел в знаниях.
Вот, то что имеем $$\sum\limits_{i=1}^{n}(((a\bmod k)\cdot(i \bmod k))\bmod k)$$
И чтобы что-то вынести без потери целостности, моя фантазия пасует.

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 04:20 
Аватара пользователя
Не число же выносить! А сам знак сравнения! То есть сначала просуммировать, а потом уж взять остаток

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 04:24 
provincialka в сообщении #1086421 писал(а):
Не число же выносить! А сам знак сравнения! То есть сначала просуммировать, а потом уж взять остаток

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

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 04:27 
Аватара пользователя
Ага! И дальше по алгоритму, указанному ewert

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 04:34 
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$$

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

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 08:12 
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$ за знак суммы, то получим выражение меньше модуля, в то время как очевидно, что сумма не ограниченна.

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 16:51 
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

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 17:54 
Чтоб было попроще и не ошибиться сначала найду сумму ряда
$\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}$

 
 
 
 Re: Сумма остатков
Сообщение28.12.2015, 20:52 
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$. Можете взять его для самоконтроля, но это не сильно поможет - все равно он сократится.

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

 
 
 
 Re: Сумма остатков
Сообщение29.12.2015, 00:45 
$\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

 
 
 
 Re: Сумма остатков
Сообщение29.12.2015, 16:02 
Аватара пользователя
Cancre в сообщении #1086372 писал(а):
И где можно о таких рядах почитать?

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

 
 
 [ Сообщений: 51 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group