Google Answers Logo
View Question
Q: Large Numbers ( Answered 5 out of 5 stars,   0 Comments )
Subject: Large Numbers
Category: Science
Asked by: mrsneaky-ga
List Price: $5.00
Posted: 02 Jan 2004 18:48 PST
Expires: 01 Feb 2004 18:48 PST
Question ID: 292562
What is the largest value that X!<= 2^8,388,608 can be (X Factorial)?
Subject: Re: Large Numbers
Answered By: mathtalk-ga on 02 Jan 2004 22:01 PST
Rated:5 out of 5 stars
Hi, mrsneaky-ga:

I will assume you are looking for the largest natural number X such that:

X! <= 2^8,388,608

where X! denotes the factorial of X.

From a practical computation standpoint we can take the logarithms of
both sides.  The natural logarithm is a monotone increasing function,
so it preserves the sense of the inequality:

ln( X!) <= ln( 2^8,388,608 )

and by skillful(?) application of the laws of logarithms:

SUM ln(k) [FOR k = 1 to X] <= 8,388,608 * ln(2)

is an equivalent criterion.  Now we are working with much smaller
numbers, albeit still roughly six or seven digit numbers.  Certainly
we can write a short computer program to accumulate the sums on the
left hand side until they reach just short of exceeding the right hand
side.  Round-off error is negligible if we do the computation in naive
fashion, for all the summands are nonnegative and increasing (with k).
 In fact I wrote two such programs, one in Prolog and one in
Transact-SQL, and both give as a result X = 481176.

If we want to be truly paranoid about the answer, however, and insist
on more mathematical rigor (and less reliance on computer "science"),
then we can apply instead some calculus estimates.  Basically we need
to demonstrate two things:

SUM ln(k) [FOR k = 1 to 481176] < 8,388,608 * ln(2)


SUM ln(k) [FOR k = 1 to 481177] > 8,388,608 * ln(2)

In fact we might suspect that there is a good reason to be paranoid,
for it does happen that 8,388,608 * ln(2) = 5814539.984... is a little
unreasonable close to a whole number.  That doesn't really cause much
of a problem, as we'll see, but it does increase the interest in
making an estimate "free" of programming considerations (at least in
some superficial sense; we are after all relying on the basic accuracy
of the logarithm function to compute ln(2) or to do the multiplication

Let's tackle the upper bound on the sum from 1 to 481176 first, as
this makes the most elementary use of calculus.  Recall that ln(1) =
0, and that the terms of the summation:

SUM ln(k) [FOR k = 2 to 481176]

can be interpreted as terms of a lower Riemann sum for the definite integral:

INTEGRAL ln(x) dx [OVER x = 2 to 481177]

since the monotone increasing function ln(x) has its minimum on each
subinterval [k,k+1] at the left hand endpoint.  But ln(x) has as its
indefinite integral:

INTEGRAL ln(x) dx = x(ln(x) - 1) + C

Consequently the given definite integral is "exactly":

[481177 * (ln(481177) - 1)] - [2 * (ln(2) - 1)]
    =    5814538.8935706411...

Now the summation is a lower bound to the integral, and in turn the
integral is less than 8,388,608 * ln(2) = 5814539.984... by a clear
margin, so the first part of our claim is established.

The estimate in the second part of the claim we must do with a little
more finesse.  What we will argue is that:

SUM ln(k) [FOR k = 1 to 481177]

is an upper bound on:

INTEGRAL ln(x) dx [OVER x = 1.5 to 481177.5]

Again we start by dropping the zero term ln(1) corresponding to k = 1,
so that we are really analyzing:

SUM ln(k) [FOR k = 2 to 481177]

The claim we want to make is that because of the concave "downness" of
the logarithm function, we have on each subinterval [k - 1/2, k +

ln(k) > INTEGRAL ln(x) dx [OVER x = k - 1/2 to k + 1/2]

I won't belabor this point (unless I'm encouraged!) except to say that
the concave down nature of the logarithm function ln(x) follows from
its negative second derivative, ie. the first derivative of 1/x, for
all x > 0.

Piecing the summation of ln(k) on the left hand sides together with a
smooth joining of the intervals of integration on the right hand sides
gives the desired bound.  Thus:

SUM ln(k) [FOR k = 2 to 481177]
   > INTEGRAL ln(x) dx [OVER x = 3/2 to 481177.5]

with the "exact" definite integral being computed from the same
indefinite integral x(ln(x) - 1) + C as before.  The result this time

INTEGRAL ln(x) dx [OVER x = 1.5 to 481177.5]
   = [481177.5 * (ln(481177.5) - 1)] - [1.5 * (ln(1.5) - 1)]
   = 5814545.713662832...

which now exceeds 8,388,608 * ln(2) = 5814539.984... by a very
comfortable margin.  So we have established both of the required
estimates, ie.

481176! < 2^8,388,608 < 481177!

with "hand" calculus and only such computations as can be done on a
suitable calculator.

regards, mathtalk-ga
mrsneaky-ga rated this answer:5 out of 5 stars and gave an additional tip of: $20.00

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy