View Question
 Question
 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)?`
 ```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```
 mrsneaky-ga rated this answer: and gave an additional tip of: \$20.00 `GREAT`