What is the largest value that X!<= 2^8,388,608 can be (X Factorial)?

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)

and:

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
above).

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 +
1/2]:

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
is:

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

GREAT