This problem is taken from a Russian textbook of past Olympiads.
Its statement looks like this :
Given a natural number $n > 1000$ prove that $\sum_{k=1}^{n} 2^n \text{ mod }k > 2n$.
Apart from a few basic considerations:
$2^n$ is not divisible by any odd number except $1$ so the remainder of $2^n$ divided by any such number will always be greater or equal to $1$, I haven't been able to make any notable progress from here.
The solution provided in the textbook is also very unintuitive, or at least I perceive it as such. The author sets out right off the bat to prove that
$$S_n > \frac{n}{2}(\log_2n - 4), \text{ where $S_n$ denotes $\sum_{k=1}^{n} 2^n \text{ mod }k$}.$$
Let me do the calculations. The method is the one pointed out by Greg Martin in the comments.
Suppose $k = 2^m \ell$, where $\ell$ is odd and $\neq1$. Then $$2^n \bmod k \geq 2^m$$ ($2^n \bmod k$ is divisible by $2^m$, but non-zero).
Hence, counting the number of $k$'s of the form above (for each value of $m$): $$\sum_{k=1}^{n} 2^n \bmod k \geq \sum_{m=0}^{\log_2 n -1}2^m \times \left(\left\lfloor\frac{n}{2^m}\right\rfloor - \left\lfloor\frac{n}{2^{m+1}}\right\rfloor - 1\right) \geq \sum_{m=0}^{\log_2n-1}2^m \times \left(\frac{n}{2^{m+1}} - 2\right)$$
which is happily $> \frac{n}{2}\lfloor\log_2 n\rfloor- 2n$.