Остатки

[Terraniux]

Рассмотрим натуральное число $n > 1000$. Найдём остатки от деления числа $2^n$ на числа $1, 2, 3, \ldots, n$ и сложим все эти остатки. Докажите, что сумма больше $2n$.

[Sonic86]

$S(n):=\sum\limits_{k=1}^{n}2^n\bmod k\geqslant \sum\limits_{k=1, k=2^ra,a\neq 1}^{n}2^r-\sum\limits_{k=2^r}^{n}2^r=\sum\limits_{k=1}^{n}2^{v_2(k)}-2^{[\log_2n]+1}+2$
$f(n):=\sum\limits_{k=1}^{n}2^{v_2(k)}$
$f(n)=\left[\frac{n+1}{2}\right]+2f\left(\left[\frac{n}{2}\right]\right)=\sum\limits_{k=1}^{[\log_2n]}2^{k-1}\left[\frac{n+2^{k-1}}{2^k}\right]\geqslant\sum\limits_{k=1}^{[\log_2n]}2^{k-1}\frac{n-2^{k-1}}{2^k}=n\frac{[\log_2n]}{2}-\frac{2^{[\log_2n]}-1}{2}=n\frac{\ln n}{2\ln 2}+O(n).$
В итоге $S(n)\geqslant n\frac{[\log_2n]}{2}-\frac{5}{2}\cdot 2^{[\log_2n]}+3>2n$ при $n>1000$.

Интересно, насколько точно она вычисляется?

[Terraniux]

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

(Решение)

$S(n):=\sum\limits_{k=1}^{n}2^n\bmod k\geqslant \sum\limits_{k=1, k=2^ra,a\neq 1}^{n}2^r-\sum\limits_{k=2^r}^{n}2^r=\sum\limits_{k=1}^{n}2^{v_2(k)}-2^{[\log_2n]+1}+2$
$f(n):=\sum\limits_{k=1}^{n}2^{v_2(k)}$
$f(n)=\left[\frac{n+1}{2}\right]+2f\left(\left[\frac{n}{2}\right]\right)=\sum\limits_{k=1}^{[\log_2n]}2^{k-1}\left[\frac{n+2^{k-1}}{2^k}\right]\geqslant\sum\limits_{k=1}^{[\log_2n]}2^{k-1}\frac{n-2^{k-1}}{2^k}=n\frac{[\log_2n]}{2}-\frac{2^{[\log_2n]}-1}{2}=n\frac{\ln n}{2\ln 2}+O(n).$
В итоге $S(n)\geqslant n\frac{[\log_2n]}{2}-\frac{5}{2}\cdot 2^{[\log_2n]}+3>2n$ при $n>1000$.

Интересно, насколько точно она вычисляется?

Все-таки сложная это задача оказалась.

[Sonic86]

Terraniux в сообщении #752286 писал(а):

Все-таки сложная это задача оказалась.

Хочется заметить, что оценка $S(n)>Cn\ln n$ крайне слабая. Похоже, что $S(n)$ растет почти как квадрат. Но руки не доходят поразбирать сумму.