Обозначим сумму остатков от деления 2ⁿ на числа 1, 2, ..., n через S_n. Мы докажем, что  S_n > 3,5n  при  n > 1000.

  2ⁿ не делится нацело ни на какое нечётное число, отличное от 1, значит, остаток от деления 2ⁿ на такое число не меньше 1. Отсюда легко вывести, что для любого нечётного  k > 1  остаток от деления 2ⁿ на 2^lk не меньше 2^l.

  Отсюда следует, что  S_n ≥ n₀ + 2n₁ + 2²n₃ + ... + 2^mn_m,  где n_i – количество не превосходящих n чисел вида  2ⁱ(2k + 1),  k > 1,  а m определяется условиями

3·2^m ≤ n < 3·2^m+1  (нет смысла брать большее m, так как тогда выражение в скобке будет равно нулю).

  Рассмотрим (i+1)-e слагаемое 2ⁱn_i. Число n_i равно числу не превосходящих n членов арифметической прогрессии 3·2ⁱ, 5·2ⁱ, 7·2ⁱ, .... Число таких членов не меньше  ,  и, значит, это слагаемое не меньше  ⁿ/₂ – 3·2^i–1.

  Заменив сумму в правой части первыми восемью слагаемыми, получим  S_n > 8·ⁿ/₂ – 3(2^–1 + 1 + 2 + 2² + ... + 2⁶) > 4n − 3·2⁷ = 3,5n + (ⁿ/₂ – 384).

  При  n > 1000  выражение в скобке положительно, то есть  S_n > 3,5n.

Ответ задачи отсутствует