The harmonic series is the sum
1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + ... + 1/n + ...
It is known that this sum diverges, meaning (informally) that the sum is infinite and (more formally) that for any real number x, there there is some number n such t that the sum of the first n terms of the harmonic series is greater than x. For example, given x = 3, we have that
1 + 1/2 + 1/3 + ... + 1/11 = 83711/27720 ≈ 3.02
So eleven terms must be summed together to exceed 3.
Consider the following question
Given an integer x, find the smallest value of n such that the sum of the first n terms of the harmonic series exceeds x.
Clearly we can compute this by just adding in more and more terms of the harmonic series, but this seems like it could be painfully slow. The best bound I'm aware of on the number of terms necessary is 2O(n), which uses the fact that
1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ...
is greater than
1 + (1/2) + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + ...
which is in turn
1 + 1/2 + 1/2 + 1/2 + ...
where each new 1/2 takes twice as many terms as the previous to accrue. This means that the brute-force solution is likely to be completely infeasible for any reasonably large choice of x.
Is there way to calculate the harmonic series which requires less operations than the brute-force solution?