I am not so sure that this is exact. The equation (52) at the mathworld link, which Alex gave in his post above, shows that the estimate given by ln(n) + g is a little bit low, specifically, by an amount between 1/(2n+1) and 1/(2n). Now, for any integer N, if you want to find n such that the n-1st harmonic sum, H(n-1) < N but H(n) >= N, it may happen that H(n) is just barely above N, i.e. H(n) = N + epsilon, and we have no apriori way of knowing just how small epsilon may be. Certainly epsilon may be no larger than H(n)-H(n-1) = 1/n, and this only about twice the size of the error in the ln(n) + g estimate, so it is quite likely that epsilon could fairly often be less than 1/(2n+1), in which case the estimate would say that H(n) < N, which is wrong. Therefore, this estimate may sometimes return an answer n+1 when the true answer is n.

It is also not easy to fix this problem. If we decided to use ln(n) + g + 1/(2n+1) as our estimate, that the estimate is still low, and the error is now at most 1/(2n(2n+1)). This makes it less likely that epsilon could be smaller than the error, but does not eliminate the possibility. The answer will sometimes still be wrong by one. If one wanted to work harder and get a succession of better estimates, it would improve the probability that each answer given by the estimate is correct, but it would never become a certainty, because there is no known lower limit on epsilon.

Another problem, which is of a more computational nature, is that we don't know all the digits of g. Using the estimate as an approximation to the true solution, one would expect that n is roughly exp(N-g), which means that the difference between H(n) and H(n+1) is about exp(g-N), or 10 ^(-(N-g)/2.3), since 10 is roughly exp(2.3). This means that an error in the ((N-g)/2.3)th decimal place of g would throw off the answer. I believe that the mathworld site mentions that g is known to about 104 million digits, so n cannot be found for N > 230,000,000.

These sorts of computational issues are often ignored in pure mathematics, but here I think they are relevant. Of course, if you only want estimates of n, rather than the exact integer, then everything is fine. However, questions in number theory or integer arithmetic in general often depend on knowing the precise integer in question, because its divisibility properties, etc, may be needed. So the answer above is either completely satisfactory or completely unsatisfactory, depending on one's point of view. Since I'm not trying to investigate number theoretic questions just now, I'm happy with the estimate.

Thank you

--Stuart Anderson

Nor am I (or anyone else AFAIK). That's why I said "conjecturally".

I'm not sure when I first thought of the conjecture. Perhaps in 2001, in the course of investigating the inverse of H(x). In any event, it's unlikely that I was the first person to make that conjecture. And, yes, I was well aware of the type of concern you raise below.

Regarding that type of concern, please look at
<https://www.research.att.com/~njas/sequences/A002387>, in which Dean
Hickerson mentions "a simple heuristic argument" supporting the
conjecture. If you see anything wrong with his argument, please let us
and OEIS know! (BTW, that OEIS entry also shows that Benoit Cloitre knew of the conjecture in 2002. Also note that, in the title of that entry, the lower limit on the summation should obviously be 1, not 0.)

Regards,
David W. Cantrell

>The equation (52) at
>the mathworld link, which Alex gave in his post above, shows
>that the estimate given by ln(n) + g is a little bit low,
>specifically, by an amount between 1/(2n+1) and 1/(2n).
>Now, for any integer N, if you want to find n such that the
>n-1st harmonic sum, H(n-1) < N but H(n) >= N, it may happen
>that H(n) is just barely above N, i.e. H(n) = N + epsilon,
>and we have no apriori way of knowing just how small epsilon
>may be. Certainly epsilon may be no larger than H(n)-H(n-1)
>= 1/n, and this only about twice the size of the error in
>the ln(n) + g estimate, so it is quite likely that epsilon
>could fairly often be less than 1/(2n+1), in which case the
>estimate would say that H(n) < N, which is wrong.
>Therefore, this estimate may sometimes return an answer n+1
>when the true answer is n.
>
>It is also not easy to fix this problem. If we decided to
>use ln(n) + g + 1/(2n+1) as our estimate, that the estimate
>is still low, and the error is now at most 1/(2n(2n+1)).
>This makes it less likely that epsilon could be smaller than
>the error, but does not eliminate the possibility. The
>answer will sometimes still be wrong by one. If one wanted
>to work harder and get a succession of better estimates, it
>would improve the probability that each answer given by the
>estimate is correct, but it would never become a certainty,
>because there is no known lower limit on epsilon.

Spurred by this discussion, I recently reconsidered how to invert
harmonic numbers and found an asymptotic series for the inverse. See
<https://groups.google.com/group/sci.math/msg/0926db8773d69b81>.
This allows us to give stronger conjectural answers to the question
posed here.

Previously, I had said conjecturally that "the first sum to exceed n
has exactly floor(e^(n - g) + 1/2) terms" and Dean Hickerson's
heuristic argument had shown that conjecture to be true with
probability > 97%. But now, for example, using just two more terms
of the asymptotic series, we can say, based on that same type of
heuristic argument, that with probability > 99.995%, the first
harmonic sum to exceed n has exactly

floor(u + 1/2 - 1/(24u) + 3/(640u^3)) terms,

where u = e^(n - g).

Regards,
David W. Cantrell