2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4
 
 Re: Сумма остатков
Сообщение24.01.2016, 18:24 
Для лучшего понимания рисунок сделал.

Изображение

 
 
 
 Re: Сумма остатков
Сообщение25.01.2016, 22:31 
Упрощающие обозначения:

$\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{\alpha\nu(\nu+1)}{2}-\nu(\alpha-q-1))$$

Данная формула верна при взаимно простых a и k, а также при условии $\left\lfloor\frac{k-a}{a}\right\rfloor > 0$
Если $\left\lfloor\frac{k-a}{a}\right\rfloor = 0$ , тогда остатки в ряде по вычетам зеркально меняются местами и пока не ясно, как это отражение выразить в формуле.

 
 
 
 Re: Сумма остатков
Сообщение26.01.2016, 19:47 
В случае $\left\lfloor\frac{k-a}{a}\right\rfloor=0$ из полной суммы вычетов $\frac{ak(k+1)}{2}$ нужно вычесть $\sum\limits_{j=0}^{k-r}((k-a)j \bmod k)$

Ещё нужно ввести функцию, учитывающую нули при соответствующих остатках и случай $a=k$
$$\chi_m (x,y) =\begin{cases}
0,&\text{если $x \bmod y = 0$;}\\
1,&\text{если $x \bmod y > 0$}
\end{cases}$$
И добавляется НОД(a,k).
Всё вместе:
$$\sum\limits_{i=1}^{n}(ai \bmod k)= \chi_m (a,k)\frac{ak(k+1)}{2\gcd(a,k)}\left\lfloor\frac{n}{k}\right\rfloor$+\begin{cases}
\chi_m (aj,k)$$\sum\limits_{j=1}^{r}(aj \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor>0$;}\\
\frac{ak(k+1)}{2\gcd(a,k)}-\chi_m ((k-a)j,k)$$\sum\limits_{j=1}^{k-r}((k-a)j \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor=0$}
\end{cases}$$

 
 
 
 Re: Сумма остатков
Сообщение26.01.2016, 21:11 
Я пока в основном по обозначениям:
Cancre в сообщении #1094492 писал(а):
$\left\lfloor\frac{k-a}{a}\right\rfloor=0$
Изврат: $\Leftrightarrow k \in [a;2a) $.
Cancre в сообщении #1094492 писал(а):
$\left\lfloor\frac{k-a}{a}\right\rfloor>0$
Аналогично: $k\geqslant 2a$.
Cancre в сообщении #1094492 писал(а):
$$\chi_m (x,y) =\begin{cases}
0,&\text{если $x \bmod y = 0$;}\\
1,&\text{если $x \bmod y > 0$}
\end{cases}$$
индекс $m$ зачем? можно стереть.
и вообще самое короткое, что здесь можно писать, это - нотация Айверсона: $\chi (x,y)=[x\nmid y]$ (здесь $[P]=1 \Leftrightarrow P\text{ истинно}$, иначе $[P]=0$)

Cancre в сообщении #1094492 писал(а):
$\chi_m (aj,k) \sum\limits_{j=1}^{r}(aj \bmod k)$
переменная суммирования вне суммы, кроме того, $\chi_m (aj,k)$ сильно упрощаемо.

Cancre в сообщении #1094492 писал(а):
$\chi_m ((k-a)j,k)$
Аналогично + еще более упрощаемо.

И, теряя уже надежду что-то донести, в 3-й раз Вам говорю: достаточно рассмотреть случай $\gcd(a,k)=1$, общий случай тривиально к нему сводится.

Но пока, все что я вижу, похоже на попытку итерирования формулы для НОДа, что, как я уже писал, бесполезно.

 
 
 
 Re: Сумма остатков
Сообщение26.01.2016, 22:22 
Sonic86 в сообщении #1094506 писал(а):
Я пока в основном по обозначениям:
Cancre в сообщении #1094492 писал(а):
$\left\lfloor\frac{k-a}{a}\right\rfloor=0$
Изврат: $\Leftrightarrow k \in [a;2a) $.

Но именно так оно и есть. )))

-- 26.01.2016, 22:25 --

Sonic86 в сообщении #1094506 писал(а):
Cancre в сообщении #1094492 писал(а):
$$\chi_m (x,y) =\begin{cases}
0,&\text{если $x \bmod y = 0$;}\\
1,&\text{если $x \bmod y > 0$}
\end{cases}$$
индекс $m$ зачем? можно стереть.

Вместо m хотел mod , но система не дала.

-- 26.01.2016, 22:31 --

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

Cancre в сообщении #1094492 писал(а):
$\chi_m (aj,k) \sum\limits_{j=1}^{r}(aj \bmod k)$
переменная суммирования вне суммы,

Конечно же под знаком суммы
$$\sum\limits_{i=1}^{n}(ai \bmod k)= \chi_m (a,k)\frac{ak(k+1)}{2\gcd(a,k)}\left\lfloor\frac{n}{k}\right\rfloor$+\begin{cases}
$$\sum\limits_{j=1}^{r}\chi_m (aj,k)(aj \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor>0$;}\\
\frac{ak(k+1)}{2\gcd(a,k)}-$$\sum\limits_{j=1}^{k-r}\chi_m ((k-a)j,k)((k-a)j \bmod k)$$,&\text{если $\left\lfloor\frac{k-a}{a}\right\rfloor=0$}
\end{cases}$$


-- 26.01.2016, 22:40 --

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

И, теряя уже надежду что-то донести, в 3-й раз Вам говорю: достаточно рассмотреть случай $\gcd(a,k)=1$, общий случай тривиально к нему сводится.

Но пока, все что я вижу, похоже на попытку итерирования формулы для НОДа, что, как я уже писал, бесполезно.

95% времени искал формулы именно для (а,к)=1
И, вообще-то, то что искал нашёл. :-) В две формулы, но хоть так, я очень доволен. Так что, дааалеко не бесполезно.

Спасибо за замечания. Может, в каких-то моментах Вам казалось, что что-то не доносили, но это не так. Все замечания обдумывались.

 
 
 
 Re: Сумма остатков
Сообщение27.01.2016, 11:48 
Аватара пользователя

($\chi_{mod}$)

Cancre в сообщении #1094516 писал(а):
Вместо m хотел mod , но система не дала.
используйте фигурные скобки для группировки.
Код:
$\chi_{mod}$
$\chi_{mod}$

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


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