Тождество от Андрея А.

[Sonic86]

1. Докажите, что

$$\sum\limits_{k=1}^n\sigma(k)=\lceil\frac{n+1-t_1}{1}\rceil^2-\lceil\frac{n+1-t_2}{2}\rceil^2+\lceil\frac{n+1-t_3}{3}\rceil^2-...$$

Здесь $\sigma(k)$ - сумма всех делителей числа $k$, $t_k=1+2+...+k$ - треугольные числа, а в сумме справа все числители положительны.
2. Есть ли аналогичные формулы для $\varphi(n)$, например?

[Руст]

Красивая формула, только надо уточнить до какого надо суммировать справа и преобразовать к виду:

$$\sum\limits_{k=1}^n\sigma(k)=\sum_{k(k+1)\le 2n}(-1)^{k-1}\lceil\frac{n+1}{k}-\frac{k+1}{2}\rceil^2$$

Я вначале думал, что наверно используется техника Эйлера, как в формуле:

$$\sum_k(-1)^k\sigma(n-\frac{k(3k-1)}{2})\equiv 0.$$

После преобразования стало ясно, что пойдет и обычное вычисление, разбивая на две части сумму $\sum_k k[\frac{n}{k}$, где выполняется неравенство, преобразуя ту часть где не выполняется.

Цитата:

2. Есть ли аналогичные формулы для $\varphi(n)$, например?

Я не знаю.