On 2008-05-14, Jim Dars <jim-dars@[EMAIL PROTECTED]
> wrote:
> Even with today's computers I suspect the calculation would take a
> long time.
Approximations to y can be made accurate to as many figures as you can
handle, very rapidly. The only problem with making it exact is the
difficulty of representing the answer, which has more than 10^300 bits
and so a naive representation cannot work.
> I wonder how accurate the estimate might be?
It's just looking at harmonic numbers H_n, and tons is known about
them. In particular,
|H_n - (ln n + gamma + 1/(2n))| < 1/n^2 for all n.
Since you're just interested in differences of H_y and H_g, the gamma
term in the approximation drops out entirely, so for y' = g/e and
y = floor(y'),
H_g - H_y = ln g - ln y + 1/(2g) - 1/(2y) + O(y^-2),
which reduces to
H_g - H_y = 1 + (frac(y') + 1/(2e) - 1/2) / y + O(y^-2).
So the solution y = floor(g/e) is exact if
frac(g/e) > (e - 1) / 2e + some number of magnitude 10^(-10^100),
otherwise we need to let y = ceil(g/e). At most the approximation can
be out by 1.
There might be some clever theoretical argument that can determine
whether in this particular case the floor or the ceiling operation
should be taken without having to compute the first 10^100 or so
decimal digits of e, but I suspect there isn't.
- Tim
|
