How to optimize the sum of a series?

Question

Mathematics

Good day, tell me how you can optimize the algorithm for counting a series for large values ​​of k?

Answer 1

Analytically.
I found a truly wonderful proof of this, but the input field is too narrow for it. (C) Farm.

Decision

Рассмотрим дроби - слагаемые данной суммы. Очевидно, что знаменатели могут меняться от 2 до 2k.
Попробуем определить, какие числители будут в дробях со знаменателем n. Для этого нам надо разложить n на пары x и y всеми возможными способами, учитывая ограничения 1 ≤ x ≤ k, 1 ≤ y ≤ k и взять допустимые значения x.
Если 2 ≤ n ≤ k, то допустимыми значениями x будут 1 ... n-1. Для k+1 ≤ n ≤ 2k допустимыми значениями x будут n-k ... k. Таким образом, мы можем записать сумму числителей для каждого знаменателя:
Теперь, с учётом полученной системы запишем, как будет выглядеть полная сумма всех дробей:
Заметим, что если в первой сумме начать суммирование не с 2, а с 1, то сумма не изменится, поскольку добавленное слагаемое равняется нулю. Во второй сумме перенесём k из пределов суммирования в слагаемое. Получим две суммы с одинаковыми пределами, а значит их можно объединить в одну: