On May 14, 3:02=A0pm, "Jim Dars" <jim-d...@[EMAIL PROTECTED]
> wrote:
> "Chip Eastham" <hardm...@[EMAIL PROTECTED]
> wrote in message
>
>
news:eb4efd04-7489-4316-8f14-def61ddc6249@[EMAIL PROTECTED]
> On May 13, 7:49 pm, "Jim Dars" <jim-d...@[EMAIL PROTECTED]
> wrote:
>
> > Hi All,
>
> > Find y:
>
> > Given: g =3D a googolplex - 1
> > y =3D the largest number smaller than g such that
>
> > Sum(i =3D y to g) 1/i >=3D 1
>
> > If you can't, can you recommend a good estimate of y?
>
> > Best wishes, Jim
>
> The obvious tack is to approximate the sum
> by an integral:
>
> SUM 1/k FOR k =3D y to g
>
> is approximately INTEGRAL 1/x dx FROM x =3D y to g+1
> or ln(googolplex) - ln(y). =A0Because the integral
> is a lower bound on the sum, we can infer a lower
> bound for y:
>
> y > exp(ln(googolplex) - 1) =3D googolplex/e
>
> A tighter estimate can be given by bringing Euler's
> gamma constant into the picture.
>
> regards, chip
>
> Hi Chip,
>
> This summation is required in the "Dowry" problem. =A0When the number of
> numbers goes to infinity the probability of choosing the largest goes to
> 1/e. =A0However, choosing the two regions when the number is finite, but
v=
ery
> large, isn't clear to me. =A0I used a googolplex for my finite large
numbe=
r.
> Even with today's computers I suspect the calculation would take a long
> time. =A0I wonder how accurate the estimate might be? =A0(I suspect you
wo=
uld
> induce little error, but "suspect" (in mathematics) just doesn't seem
righ=
t.
>
> Best wishes, Jim
Thanks for the background, Jim.
As your probably realize, because a googolplex is
ten to the googol, there aren't enough bits in the
visible universe to write down the exact binary or
decimal representation of floor(googolplex/e).
But I think I understand your concern. Given a
large but finite integer N, efficiently find the
largest integer y(N) s.t.
SUM 1/k FOR k =3D y to N-1 >=3D 1
Thinking of this as an upper Riemann sum for the
integral of 1/x from y to N (with subintervals of
length 1), the sum bounds the definite integral
above. Looking at it the other way round, the
definite integral is a lower bound for the sum.
This leads to the lower bound floor(N/e) for y(N).
We can vary the recipe a bit and come up with an
upper bound on the sum, which in turn gives an
upper bound for y(N). The definite integral of
1/x from y-1 to N-1 has the sum above as a lower
Riemann sum. Therefore the solution to:
ln(N-1) - ln(y-1) =3D 1
y-1 =3D exp(ln(N-1) - 1) =3D (N-1)/e
gives y(N) < ceil((N-1)/e) + 1.
Perhaps I've made a mistake along the way here,
but it doesn't seem that there could be a lot
of room between:
floor(N/e) <=3D y(N) <=3D ceil((N-1)/e).
If there is a genuine gap here, then our task
becomes to choose between floor(N/e) and one
more than that for y(N). For that we would
need an accurate enough estimate of the sum,
which is where Euler's gamma constant comes
into play. More later...
regards, chip
|
