A teacher once told me the minimum number of operations needed to calculate the exact value of the nth Harmonic number was n operations. Using something similar to Euler's proof of:
$\sum_{i=1}^n i = \frac{n(n+1)}{2} $, we can easily show that it can be calculated with n/2 operations:
$\ 2\times\sum_{i=1}^8 \frac{1}{i} = $
$\ \frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8} $
$\ \frac{1}{8}+\frac{1}{7}+\frac{1}{6}+\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2}+\frac{1}{1} $
$\ (\frac{1+8}{1\times8}+\frac{2+7}{2\times7}+\frac{3+6}{3\times6}+\frac{4+5}{4\times5})+(\frac{4+5}{4\times5}+\frac{3+6}{3\times6}+\frac{2+7}{2\times7}+\frac{1+8}{1\times8}) $
With a little bit of work, this shows that
$\ \sum_{i=1}^n \frac{1}{i} = (n+1)\sum_{i=1}^\frac{n}{2} \frac{1}{ni-i^2+i}$
I didnt find much information on this subject, is there a known proof for the minimum number of operations needed to compute Harmonic numbers ? Of course i'm not talking about asymptotic expantion here.