Can the harmonic sum $H_n = \sum_{k=1}^n \frac{1}{k}$ be efficiently computed?
$H_n$ can be computed in $n$ reciprocals and adds. Is there a way of getting the exact rational sum in $o(n)$ operations?
An operation is an add, subtract, multiply or divide of rational numbers.
A possible start is $H_{2n} =\frac{1}{2}H_n+\sum_{k=1}^n \frac{1}{2k-1} $, but this does not reduce the number of operations.
I am not concerned with the fact that rational operations will take longer for larger numerators and denominators, though taking this into account would be interesting.
I am aware that the denominator would be $\text{lcm}(1, 2,\dots, n) \sim e^n $ and that $H_n$ has an asymptotic expansion of the form $\ln(n)+\gamma+\sum_{k \ge 1} \frac{a_k}{n^k} $.