2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Сумма остатков
Сообщение30.12.2015, 04:47 
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$
Вот, где-то такое моё понимание.

 
 
 
 Re: Сумма остатков
Сообщение30.12.2015, 06:38 
Тут ещё немного поразмышлял и вот что нафантазировал.
Если первый остаток не делит 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}$

 
 
 
 Re: Сумма остатков
Сообщение31.12.2015, 18:13 

(Оффтоп)

Cancre в сообщении #1086951 писал(а):
Можно ввести обобщённую функцию
$\tilde{\mathfrak{Q}}(a\mod k)$
:shock: зачем такие страшные буквы писать?

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

 
 
 
 Re: Сумма остатков
Сообщение03.01.2016, 13:50 

(Оффтоп)

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

Правильная формула такая: для $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$.

 
 
 
 Re: Сумма остатков
Сообщение09.01.2016, 02:50 
С новым годом!
Во-первых, спасибо, что уделили время на данную тему, прочитал, поразмышлял.
Во-вторых, мало чего понял.
Какой смысл находить рекурентную форму, если требуется закрытая форма?
Ещё меня смутили условия.
В третьих, (оффтоп) буковки красивые. Но по сути это НОД, поэтому нафиг что-то вводить новое, это результат размышлений после новогодней ночи )))
А результат праздников таков:
$$\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)$$ в обычную формулу переводиться не хочет. В связи с этим вопрос: Возможна ли здесь, вообще, закрытая форма?

 
 
 
 Re: Сумма остатков
Сообщение09.01.2016, 08:58 
Cancre в сообщении #1089164 писал(а):
В связи с этим вопрос: Возможна ли здесь, вообще, закрытая форма?

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

Cancre в сообщении #1089164 писал(а):
Какой смысл находить рекурентную форму, если требуется закрытая форма?
Ну попробуйте ее найти, особенно с учетом того, что ее может не быть.

 
 
 
 Re: Сумма остатков
Сообщение12.01.2016, 23:42 
Sonic86 в сообщении #1089184 писал(а):
Ну попробуйте ее найти, особенно с учетом того, что ее может не быть.

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

 
 
 
 Re: Сумма остатков
Сообщение14.01.2016, 07:42 
Просьба показать.

 
 
 
 Re: Сумма остатков
Сообщение14.01.2016, 19:03 
Как всегда дьявол кроется в мелочах. Приходится исправлять. Надеюсь, исправление не затянется на долго.

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

Итак, нужно выразить конечную не полную часть ряда
$$ \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 - редукция

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

 
 
 
 Re: Сумма остатков
Сообщение15.01.2016, 08:22 
Я в конце Ваш пост перепишу покороче и тогда проверю.
А пока: что такое $\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 писал(а):
Формула получается слишком громоздкой.
может просто отпасть

 
 
 
 Re: Сумма остатков
Сообщение15.01.2016, 15:45 
Обозначив $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)$

 
 
 
 Re: Сумма остатков
Сообщение15.01.2016, 15:49 
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)$
:lol:
сами понимаете

 
 
 
 Re: Сумма остатков
Сообщение16.01.2016, 04:53 
Внутри суммы всё впорядке
$\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)$$

 
 
 
 Re: Сумма остатков
Сообщение17.01.2016, 09:01 
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)$, что сильнее, потому подозрительнее.

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


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