googol-bang
googol-bang
Let's try to bound the value (10^100)!, known as a googol-bang.
Firstly it should be observed that it is overwhelmingly likely that googolplex < googol-bang. A googolplex can be thought of as 10*10*10*10* ... ... *10*10*10 w/googol 10s, where as a googol-bang can be thought of as 1*2*3*4* ... ... *(googol-2)*(googol-1)*googol where there are a googol terms being multiplied together. Even though the first 9 terms will be less than 10, the vast majority of them will be vastly greater than 10, so it seems inevitable that at some point, probably early on, n-plex is overtaken by n-bang. In fact we can see exactly when this happens:
So n! overtakes 10^n at n=25. By necessity n! must be greater than 10^n when n>25. So we can say:
10^n < n! : n>24
For very large n, 10^n can serve as a decent lower-bound on n!. Using this we can say that:
10^(10^100) < (10^100)!
Thus a googolplex is less than a googol-bang. If a googol-bang is larger than a googolplex the next natural question is, by how much?
To narrow down the answer we will create an upper-bound. Firstly, n-bang < n^n for all n>1. This can easily be seen as follows:
n-bang = 1*2*3* ... *(n-1)*n < n*n*n* ... *n*n w/n n's = n^n
Therefore it follows that:
googol-bang < googol^googol = (10^100)^(10^100) = 10^(100*10^100) = 10^10^102
So a googol-bang must be less than 10^10^102. So we know that:
10^10^100 < googol-bang < 10^10^102
Can we improve on these bounds? Yes we can. Let's improve on the lower bound. Assume that "n" is even. It follows then that:
n-bang = 1*2*3* ... *(n/2-1)*(n/2)*(n/2+1)* ... *(n-1)*n
is greater than ...
(n/2+1)* ... *(n-1)*n
is greater than ...
(n/2)*(n/2)* ... *(n/2)*(n/2) w/(n/2) terms
is equal to ...
(n/2)^(n/2)
Since a googol is an even number it follows that:
googol-bang > (googol/2)^(googol/2) = (5*10^99)^(5*10^99)
= 5^(5*10^99) * 10^(99*5*10^99) > 10^(495*10^99) > 10^(100*10^99) = 10^10^101
Thus we conclude that:
10^10^101 < googol-bang < 10^10^102
Thus a googol-bang turns out to be only "a little bit larger" than a googolplex. In truth however the 2nd exponent is very deceptive. What this actually means is that a googol-bang is between googolplex^10 and googolplex^100. This shows that not only is a googol-bang "much much bigger" than a googolplex but also that our bounds are not nearly as close to each other as they seem. Better lower bounds can be obtained, and the result seems to be that a googol-bang is closer to 10^10^102 than 10^10^101.
To obtain a better lower bound we can simply refine the approaches we've already used. We know for example that in the product of a googol-bang there will be the numbers 1000 ... 000 , 1000 ... 001, 1000 ... 002 , ... ... , 1999 ... 999 where each of these number contains 100 digits. We can replace all of these with 1000 ... 000 w/100 digits which is equal to 1E99. There will be 1E99 of these terms from 1000 ... 000 to 1999 ... 999. Next replace all the terms from 2000 ... 000 to 2999 ... 999 with 2E99. Continue on in this manner until we've replaced all the terms from 1000 ... 000 to 9999 ... 999 with itself or a smaller value. We can discard all other terms and we will still get an improved upper-bound from our last. This is because we are now accounting for exactly 90% of all terms, where in our last estimate we only accounted for exactly 50% of them. The terms we will be using are also a closer fit than before. So we can say that:
googol-bang > (1E99)^(1E99) * (2E99)^(1E99) * (3E99)^(1E99) * ... ... * (9E99)^(1E99)
=
1^(1E99) * 10^(99E99) * 2^(1E99) * 10^(99E99) * 3^(1E99) * 10^(99E99) * ... ... 9^(1E99) * 10^(99E99)
=
2^(1E99)*3^(1E99)*...*9^(1E99)*10^(99E99+99E99+99E99+99E99+99E99+99E99+99E99+99E99+99E99+99E99)
=
2^(1E99)*3^(1E99)*4^(1E99)* ... *9^(1E99)*10^(9*99E99)
=
2^(1E99)*3^(1E99)*4^(1E99)* ... *9^(1E99)*10^(8.91E101)
=
16^(2.5E98)*81^(2.5E98)*16^(5E98)*25^(5E98)*36^(5E98)*49^(5E98)*64^(5E98)*81^(5E98)*10^(8.91E101)
>
10^(2.5E98)*10^(2.5E98)*10^(5E98)*10^(5E98)*10^(5E98)*10^(5E98)*10^(5E98)*10^(5E98)*10^(8.91E101)
=
10^(8.91E101 + 2.5E98 + 2.5E98 + 5E98 + 5E98 + 5E98 + 5E98 + 5E98 + 5E98)
=
10^(8910E98 + 7*5E98)
=
10^(8910E98 + 35E98)
=
10^(8945E98) = 10^(8.945E101)
We can even improve this figure by factoring in that there are 9E98 terms from 100 ... 000 to 999 ... 999 w/99 digits each. Replace these with 1E98. So we can say that:
googol-bang > 10^(8.945E101) * (1E98)^(9E98)
= 10^(8945E98 + 98*9E98) = 10^(8945E98 + 882E98) = 10^(9827E98) = 10^(9.827E101)
> 10^(9.8E101)
Using this we confirm that the googol-bang actually resides somewhere between the 98th and 100th power of a googolplex. So we have narrowed it down considerably. So far we have that:
10^(9.8E101) < googol-bang < 10^(10.0E101)
So we can now see that the googol-bang must be closer to 10^10^102 than 10^10^101.
To improve these figures further would require either more calculation or a deeper method. We can actually achieve a deeper method that will allow us to calculate the googol-bang to far greater accuracy without as much calculation. The basic idea is to take n^n as an overestimate of n! and then try to come up with a conversion factor. What we want to know is, how many times larger is n^n than n! for any given n. So we look at fractions of the form n^n/n!. From this we obtain the following table of values:
We can see that this ratio is actually growing. That shouldn't be too surprising. It might seem like there is no discernible pattern to these ratios, but what if we look at the ratio of these ratios. Let S(n) = n^n/n!. This gives us the sequence S(1) = 1, S(2) = 2, S(3) = 4.5, S(4) = 10.666, etc. Now we want to look at the ratio of each term to its predecessor. That is we want to find the ratios of S(n+1)/S(n). We now construct the following table:
We now see that far from being random the ratio of consecutive terms seems to be converging to a limit. What is that limit and how would we obtain it? To find this out we need to do some algebraic manipulation:
As can be seen from the algebra above, S(n+1)/S(n) is the same as (1+1/n)^n. The limit as n approaches infinity of (1+1/n)^n is a converging value defined as e. It can be approximated as:
e ~ 2.718281828...
Believe it or not we now have a powerful tool for estimating the factorial for large n. The above results can be used to derive the following equation:
Note that this is not an approximation, it is exact. The expression itself is no easier to compute than n!, and in fact would probably be more difficult. However the advantage is that it gives us insight into estimating the factorial when direct computation is impractical or impossible. The product seen in the denominator is the correction factor equal to n^n/n!. By increasing or decreasing this value to something more easy to compute we can get excellent bounds on n!. Firstly, since each term in the product is less than e (the value of convergence), we could replace each term with e, to obtain the lower-bound n^n/e^(n-1). We can then add in an additional e for ease of computation and we obtain:
(n/e)^n < n!
What we have just achieved is the "light version" of Stirling's approximation for the factorial. Even this formula however is already very accurate for our purposes. Here is a table of value to confirm that we indeed have a lower-bound formula for n! :
Although this might not seem like a very tight bound the difference will matter very little for n=10^100.
To obtain an upper bound we need to replace the terms in the product with underestimates. This can be varied according to the desired accuracy. With this in mind we can now obtain a very accurate bounds on the googol-bang. First we can compute the lower-bound using (n/e)^n. Firstly we will replace e with 2.8, since e is irrational we want to make sure that we pick a decimal which is larger to ensure that we are obtaining a true underestimate. Working it out we obtain:
(10^100)! > (10^100/e)^(10^100) > (10^100/2.8)^(10^100) > (3.57E99)^(10^100)
= 10^(log(3.57E99) * 10^100) > 10^(99.552 * 10^100) = 10^(9.9552E101)
The accuracy of this result can really only be confirmed with a tight upper-bound. To do so we first come up with a value less than e. We can use 2.7 and still get good results. Next we determine a small n such that (1+1/n)^n >= 2.7. We can use n=101 for this purpose since this results in 2.70494 and will be easy to work with. This means that for all n>100, (1+1/n)^n > 2.7. Consequently we drop the first 100 terms, and replace the rest of the terms with 2.7. Keep in mind that in order to get a proper overestimate we need to overestimate the numerator and under-estimate the denominator. Working this out we obtain:
(10^100)! < (10^100)^(10^100)/(2.7^(10^100-101)) = 10^10^102/2.7^(1E100-101)
= 10^log(10^10^102/2.7^(1E100-101)) = 10^(10^102 - log(2.7^(1E100-101)))
= 10^(10^102 - (1E100-101)log(2.7)) = 10^(10^102 -1E100log(2.7)+101log(2.7))
< 10^(10^102 -1E100(0.431)+101(0.432))
= 10^(1000E99 - 4.31E99 + 43.632 )
= 10^(995.69E99 + 43.632)
< 10^(99569E97 + 1E2)
< 10^(99569E97 + 1E97)
= 10^(99570E97) = 10^(9.9570E101)
Thus we conclude:
10^(9.955E101) < googol-bang < 10^(9.957E101)
This result confirms that the googol-bang lies somewhere between the 99th and 100th power of a googolplex. The next thing this result confirms is that the first 3 digits of the "number of digits" of a googol-bang is 995. The next digit can either be a 5 or 6 but can't be a 7 since we've proved conclusively
googol-bang < 10^(9.957E101)
These bounds are already very accurate for a number in this range. We only need to raise the lower-bound to the power of 1.0002 to obtain the upper-bound. This sounds exceedingly close, but if we look at the ratio we see that the gulf is still dramatically huge. We would need to multiply the lower-bound by more than 10^10^98 to obtain the upper-bound! Consequently the lower-bound is vanishingly small compare to the upper-bound.
How far can this method take us in terms of accuracy? Could we get the ratio of the bounds down to something like a googol?
In theory there is no limit to the accuracy this method could achieve, since we could choose values arbitrarily close to the actual values to get arbitrary close to the true value. However in practice this is simply impossible. As we improve the accuracy the number of calculations involved would quickly become impractical to unfeasible. That being said, would this method at least enable us to compute the exact number of digits, if not the number itself?
To take these methods to the extreme we can use n^n/e^(n-1), and we can choose a value arbitrary close to e from below. The problem is computing how many terms we must underestimate in the denominator. Eventually we would have to discard all of the terms, in which case the method would no longer provide an improvement.
Performing a high precision lower-bound using (n^n)/e^(n-1) I obtain
10^995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,517.2472334144523369626635831
Next we perform a high-precision upper-bound. I'll replace the first 1% of terms with "2". That means the first 10^98 terms will be replaced. Next we come up with a value for the 10^98+1st term. The value of this term is extremely close to the value of e, which is exactly what we want. It matches up with the digits of e for the first 97 digits after the decimal point! Despite the high accuracy of these calculations I obtain the upperbound
10^995,670,381,629,591,408,786,732,449,813,253,160,382,608,650,654,397,490,141,335,864,800,545,229,
153,904,736,879,231,980,276,337,707,117.5218255299060018055984652
Despite the high level of accuracy all I've managed to do is confirm that the next digit after 995 is a 6. So we can say that:
10^(9.95657E101) < googol-bang < 10^(9.95671E101)
It seems that a significant amount of computation would be needed to determine exactly how many digits the googol-bang has. In any case we can not push this method much further. If we replace more than 1% of the terms with 2 we risk hurting our upper-bound. A much tighter fit would probably be needed. If we compare
(n/e)^n to (n/2)^n we can probably get a rough idea of the gulf to be expected between bounds. Here is a table of values:
We immediately can detect a pattern. The difference in "order of magnitudes" is proportional to n. In fact it appears to be about n/10. So when n=10^100 our expected error would be about 10^99 orders of magnitude. So our error is not so unusual. To get a much more accurate figure we would need to account for the very small changes in the terms of the denominator. So it seems that we now reach an impasse.
Robert Munafo has a estimate for the googol-bang on his Number List:
10^(9.9565705518098E101)
Interestingly this estimate agrees with my high-precision lower-bound for 12-digits after the decimal point. But how close is this to the correct value? It turns out that (n/e)^n is a very accurate estimate for the factorial already, much better than the upper-bounds we've been using. This can be seen when we compare it to true factorial values that we can actually compute:
Even at n=100,000 the error is only about 3 orders of magnitude. In fact the error is growing logarithmically. This suggests that a logarithmic correction factor should be applied to tighten the upperbound. By means of this result I eventually obtained the following bounds for n! :
n^n/e^(n-1) < n! < n^(n+1)/e^(n-1) : n>1
I won't go into the details of how I obtained and proved this result here, although I may write an article detailing it in the future. In any case these bounds achieve only a logarithmic error, rather than a proportional error to n. This is a very good thing because it means we can calculate a googol-bang within a mere 100 orders-of-magnitude error; a very small error for a number with about 10^102 orders of magnitude.
Computing the lower-bound using a high precision calculation we again obtain:
10^995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,517.2472334144555887903147121260450154432287047951570365661
I now compute the upper-bound using a high precision calculation to obtain the result:
10^995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,617.2472334144555887903147121260450154432287047951570465662
As predicted these agree within a 100 orders of magnitude. That means you'd need to multiply the lower-bound by a googol to get the upper-bound. Still a huge gulf, but nothing compare to what we had before.
Is this the limit of the accuracy we could achieve? Is it possible to determine the exact number of digits? It turns out that it is. We can do so by utilizing an important property of Stirling's approximation:
sqrt(2*pi*n)(n/e)^n
It turns out that not only is this a fairly close lower-bound, but it actually improves with the size of n. That is to say, with large n, Stirling's Approximation approaches n!. Technically speaking we can say that as n goes to infinity the ratio of n! to Stirling's Approximation approaches 1. This means that not only can we use Stirling's approximation to obtain the exact number of digits, but we could even use it to determine some of the leading digits.
Carefully computing the formula as a lower-bound I obtain:
10^995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,567.212028866731
(originally I had computed the decimal part as .012482932, and obtained 102916007987 as the leading digits of the googol-bang. I have not been able to determine how the error cropped up, but props go to Robert Munafo for pointing out the error to me. After re-computing it, my result was in agreement with the various links Munafo sent me. You can find these links at the bottom of this article)
So we find that this formula winds up almost dead-center between our lower and upper-bounds. This suggests very strongly that a googol-bang has exactly:
995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,568 digits.
Because the ratio of Stirling's formula to n! approaches 1, we can also assume that the first couple of digits that we could obtain from the decimal part are probably correct. I get:
10^0.212028866731 ~ 1.62940433246
The most accurate value I can obtain for a googol-bang is therefore:
1.62940433246
x
E995,657,055,180,967,481,723,488,710,810,833,949,177,056,029,941,963,334,338,855,462,168,341,353,
507,911,292,252,707,750,506,615,682,567
From my preliminary research on Stirling's approximation, it seems that the number of correct leading digits is roughly the logarithm of n. Therefore even Stirling's approximation probably wouldn't provide more than 100 correct leading digits for the googol-bang. More correct digits could be obtained using Stirling's expansion series, but even if this was carried to the limits of practical computation it would only amount to a few billion correct leading decimal places. Yet there are about 10^102 decimal places in a googol-bang so we would barely scratch the surface of this number. We know the number must end in a lot of zeroes since 10*20*30* ... *googol is a factor of a googol-bang. This means there are at least 10^99 zeroes from the right of the decimal point. So we know the googol-bang looks something like this:
162940433246 ... ... ... ... 000000000000
There are digits buried in the middle that we will never know, and yet this is actually a generous amount of information that we can gather about this number. There are numbers much much larger where we will never even know the first leading digit ... and yet there is an answer ...
Other Results for a googol-bang
http://www.realsoftware.com/listarchives/realbasic-nug/2012-01/msg01551.html