Chip Eastham <hardmath@[EMAIL PROTECTED]
> wrote:
> On May 17, 4:35 pm, "Jim Dars" <jim-d...@[EMAIL PROTECTED]
> wrote:
> > "Tim Little" <t...@[EMAIL PROTECTED]
> wrote in message
> >
> > news:slrng2nbs2.lul.tim@[EMAIL PROTECTED]
> >
> >
> >
> > > On 2008-05-14, Jim Dars <jim-d...@[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
> >
> > Hi Tim, Chip,
> >
> > Well, I know how to go about it now. I suspect mathematical would
get
> > one pretty close.
> >
> > Thanks for the input.
> >
> > Best wishes, Jim
>
> A few final thoughts, Jim.
>
> Using the summation s(y) = SUM 1/k FOR k = y to N-1
> where N is a suitably large integer, as an upper or
> lower Riemann sum for an integral of 1/x, we get:
>
> floor(N/e) <= y <= ceiling((N-1)/e)
>
> A determination of the exact value of the largest
> integer y s.t. s(y) >= 1 can be quickly made in
> most cases by the following steps:
>
> (A) If floor(N/e) = ceiling((N-1)/e), then this
> is the value of y. Since this happens just
> when the interval ((N-1)/e,N/e) contains an
> integer, the probability is 1/e ~ 36.8%.
>
> (B) If v = ceiling((N-1)/e) exceeds floor(N/e),
> then compute an upper bound:
>
> s(v) < ln(N - 1/2) - ln(v - 1/2)
>
> and check if this shows s(v) < 1. If so,
> then y = floor(N/e).
>
> (C) If the upper bound of the previous step
> fails to show s(v) < 1, then compute a
> lower bound:
>
> s(v) > (1/v + 1/(N-1))/2 + ln(N-1) - ln(v)
>
> and check if this shows s(v) > 1. If so,
> then y = v = ceiling((N-1)/e).
>
> (D) If none of the above, apply refined upper
> and lower bounds as in (B) and (C), e.g.
> by taking the leading term(s) of s(v) as
> an exact rational and estimating the
> remaining terms.
>
> A tabulation of the outcomes for the first few
> powers of ten:
>
> POWER FLOOR CEILING Outcome
> Of 10 N/e (N-1)/e A,B,C,D
> 10^1 3 4 B
> 10^2 36 37 C
> 10^3 367 368 C
> 10^4 3678 3679 C
> 10^5 36787 36788 C
> 10^6 367879 367880 B
> 10^7 3678794 3678795 B
> 10^8 36787944 36787944 A
> 10^9 367879441 367879441 A
>
> In these cases the outcome D did not occur.
Sorry that I had not noticed this thread until just now.
With s(y) = SUM 1/k FOR k = y to N-1, the largest integer y
such that s(y) >= 1 is, with high probability, always given by
y = floor((N - 1/2)/e + 1/2 - (e^2 - 1)/(24e (N - 1/2)))
if N >= 3.
David W. Cantrell
|
