3.2.5 - Mega
A
3.2.5
Steinhaus-Moser Polygon Notation Part I
The Mega
PREV>> 3.2.3 - Ascending With Up-Arrows
Introduction
Not everything professional mathematicians contribute to "large numbers" is connected to serious mathematics. Sometimes it's just a way for mathematicians to have a little fun, and sometimes it's used as a way to popularize mathematics for the laymen. The googol and googolplex are examples of numbers that were created by a professional mathematician mostly for fun, and to make a point: the difference between a large number, an unfathomably large number, and infinity. Now days these numbers are kind of showing their age (they were coined sometime in the 1920s). They are sure to impress the man in the street, but they aren't the best examples of what professional mathematicians and googologists mean when they say something is a large number. In fact it is surprisingly easy to make a number much larger than a googol, a googolplex, Skewes' Number (record holder for largest finite number in a serious mathematical proof in 1933) or even Second Skewes' Number (record holder in 1955). We can easily define numbers Much Much larger!
In this two-part article we will see just how easy it actually is to define numbers which literally defy computation by examining the popular Steinhaus-Moser Polygon notation and the most common numbers defined in the system, ... the mega, the megiston, and the moser.
Steinhaus-Moser Polygon Notation
It is been said that Hugo Steinhaus (1887-1972), famous polish mathematician, first created his notation as a kid when trying to come up with large numbers. Although I couldn't confirm that this story is in fact true, this stuck in my mind because that is essentially what both myself and Robert Munafo did. I created my Extended Scientific Notation (the inspiration for my Hyper-E Notation), and Robert Munafo created his Extended circle operators (both of the weak and strong variety). Much later in Steinhaus' life he introduced his notation in one of his books on popular mathematics as an example of just how easy it is to generate extremely large numbers.
The earliest published material to feature the Steinhaus Notation I'm about to present is in "Mathematical Snapshots", which was first published in 1939, just a year before Kasner introduced the googol and googolplex in "Mathematics and the Imagination". Ironically, while Kasner's numbers became so famous they were eventually introduced into english dictionaries, Steinhaus' much much larger numbers never quite reached the level of household name. Here is an the actual excerpt to feature the notation from the 3rd edition of Mathematical Snapshots:
*note: there is a typo in the original. The third expression from the left should be a "2" inside two squares
It shows the definition for the Mega and how to work out it's value. Mega turns out to be way bigger than the googolplex or either of Skewes' Numbers. A Number like this would have not been considered as a record holder simply because it was not connected to any "serious" problem in mathematics. So while it was larger than the current champion of Skewes' Number at the time of publishing, it would have been mostly overlooked. None the less, the Mega became popular with laymen and became part of the early history of googology. It should be noted that the term googology itself is very recent, being coined by Andre Joyce as late as 2006. However the subject can be seen to have existed, in a sense, prior to the advent of the name as a series of loose facts and private musings. It isn't too inaccurate to say that googology really began in 1920 with the coinage of the number googol.
The notation that Steinhaus describes in Mathematical Snapshots is deceptively simple. So deceptive in fact that it comes as a shock just how fast the numbers actually grow.
It begins first with the Triangle Operator. A Number inscribed within a triangle is defined to be equal to that number raised to it's own power. That is:
Next comes the Square Operator. A Number inscribed within a square is defined to be equal to that number inscribed in that number of triangles. That is:
Next comes the Circle Operator. A Number inscribed within a circle is defined to be equal to that number inscribed in that number of squares. That is:
Steinhaus then defines not one, but two very massive numbers. The first is defined as "2 in a circle", which he called the Mega. The second is defined as "10 in a circle" which he called the Megiston. Just how big are these numbers? The only way to answer that question properly is to work them out. No qualitative description would convey to the laymen their size.
I will not be using the above notation to work them out though. While Steinhaus' Notation is conceptually simple and easy to use, the use of inscribed shapes is a little cumbersome, especially on the web. I will therefore adopt an alternative notation. Let:
triangle(n) be "n in a triangle"
square(n) be "n in a square"
circle(n) be "n in a circle"
So we can say that:
Mega = circle(2)
Megiston = circle(10)
As far as I know these are the only two numbers Steinhaus' defined using his circle notation in Mathematical Snapshots.
An unknown time later Leo Moser, a famous Austrian-canadian mathematician and world class chess player, suggested the following expansion upon Steinhaus' idea.
Firstly Moser replaced the circle operator with the pentagon, more naturally continuing the trend triangle, square, pentagon, etc. It then naturally follows that we may define a hexagon operator as iterations of the pentagon operator, a heptagon operator as iterations of the hexagon operator, an octagon operator as iterations of the heptagon operator, and so on. Just for fun, Moser then defined "2 in a mega-gon" as 2 inside a polygon with a mega sides! This was dubbed "Moser's Number" in his honor, usually abbreviated to "the moser" or just "moser".
This variant is what is known as Steinhaus-Moser Polygon notation. This notation is similar and has the same strength as a polygon notation I independently made as a kid and later developed into a full fledged googological notation (see chapter 4.3 for more details).
Given how cumbersome and impractical Steinhaus-Moser Polygon notation can be, Susan Stepney, a professor of computer science at the University of York, UK, suggested this elegant alternative:
Let n[3] be "n in a triangle"
n[4] be "n in a square"
n[5] be "n in a circle/pentagon"
and in general
n[k] is "n in a k-gon"
Conveniently these "operators" may be stacked and resolved from left-to-right. For example:
2[3][4]
means "2 inside a triangle" inside a square. Lastly Stepney suggests that we may truncate long strings of the same operator:
Let [k]_i = [k][k][k] ... [k][k][k] w/i [k]s
This will be the preferred notation for the remainder of this two-part article, however it should be known that many alternative notations have been proposed to express the same thing.
In part I of this article we will only be looking at the Mega. In a follow up article we'll examine more numbers that can be formed in Steinhaus-Moser notation including (but not limited to) a number I've dubbed the triton, the megiston, and the infamous moser.
In this Part, we will first attempt to come up with the best estimate of the Mega current technology and techniques allow. Next we will attempt to compute as many of the "terminal digits" of mega as possible. In Part II we will also examine best bounds for the various numbers and their terminating digits.
Estimating The Mega
Let's begin by working out a Mega. It begins innocently enough. By definition mega is "2 inscribed in a circle/pentagon". In Stepney's notation therefore we have:
mega = 2[5]
Next, by definition 2 in a pentagon is 2 inside 2 squares:
2[5] = 2[4][4]
We have to first compute 2[4] before we can compute 2[4][4]. 2[4] itself expands to 2 inscribed in 2 triangles:
2[4][4] = 2[3][3][4]
You might sense that things are getting a bit muddled at this point, or soon will be. The good news is that since the triangle is the lowest operator, we can now actually compute something using familiar notation. Again we must work from the innermost operator so that we must compute 2[3] before we can compute 2[3][3] before we can compute 2[3][3][4]. n[3] by definition however becomes n^n, so we just follow along with the rules:
2[3][3][4] = 2^2[3][4] = 2*2[3][4] =
4[3][4] = 4^4[4] = 4*4*4*4[4] = 16*4*4[4] = (10+6)*4*4[4] =
(40+24)*4[4] = 64*4[4] = (60+4)*4[4] = (240+16)[4] =
256[4] =
256[3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3]
That's 256 inscribed inside 256 triangles! Where the heck did that come from?! It is at this point that we reach a kind of calculation impasse, for we must first compute 256[3] before we can compute 256[3][3] before we can compute 256[3][3][3] ... and so on all the way to 256 inscribed triangles. And yet even just 256[3] is a nightmare to compute since:
256[3] = 256^256
This is not an easy number to compute, and it turns out to be pretty large. It's so big in fact that it overflows my TI-89 calculator when set to "exact mode" (which allows me to compute complete decimal strings rather than floating point approximations). The exact value of 256^256 is:
32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,484,032,130,345,
427,524,655,138,867,890,893,197,201,411,522,913,463,688,717,960,921,898,019,494,119,
559,150,490,921,095,088,152,386,448,283,120,630,877,367,300,996,091,750,197,750,389,
652,106,796,057,638,384,067,568,276,792,218,642,619,756,161,838,094,338,476,170,470,
581,645,852,036,305,042,887,575,891,541,065,808,607,552,399,123,930,385,521,914,333,
389,668,342,420,684,974,786,564,569,494,856,176,035,326,322,058,077,805,659,331,026,
192,708,460,314,150,258,592,864,177,116,725,943,603,718,461,857,357,598,351,152,301,
645,904,403,697,613,233,287,231,227,125,684,710,820,209,725,157,101,726,931,323,469,
678,542,580,656,697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,602,135,
433,229,604,645,318,478,604,952,148,193,555,853,611,059,596,230,656
That's a 617-digit number. It can be approximated in scientific notation as 3.23x10^616, or approximated as E616.509431 in E-notation. This number is already too large for most of science. It's more than the number of all the particles in the observable universe ... raised to the 7th power! But this number is NOT the Mega. Far far from it, because we still have another 255 inscribed triangles to go. We would next have to compute:
32,317,006,071,311, ... ... ... ... 059,596,230,656[3] =
32,317,006,071,311, ... ... ... ... 059,596,230,65632,317,006,071,311, ... ... ... ... 059,596,230,656
This number is now too large for anyone to ever compute it's complete decimal expansion because it contains more than E616-digits! And we still have 254 inscribed triangles to go!!!
It is at this point that the laymen is at a loss for words. It seems absolutely impossible to compute this number, and virtually impossible to even estimate! It seems to rapidly billow out of control, leaving the mind dumbfounded.
The Mega is a very big number, already much much bigger than the ordinary person would usually bother to think about. In fact, it can be shown to be bigger than a grangol ( see 4.3.2)
But if I can't even compute this number, how can I make any claims about it? How can I even say it's larger than a googolplex, even though it almost surely is. How could I possibly prove that it was greater than a grangol without being able to compute the Mega?
The key is simple: estimation. Or rather a very special kind of estimation we can call "bounding". The trick is to come up with what's called a lower bound and upper bound for the Mega. The lower-bound is an estimate for Mega which can be rigorously shown to be less than a Mega. The upper-bound is an estimate for the Mega which can be rigorously shown to be greater than a Mega. The result is that we can sandwich the complex Mega between two simpler numeric expressions, and then use these to compare the Mega to other numbers.
Not only will this strongly support my claims about the comparisons of these numbers but it will prove them beyond a shadow of a doubt!
Creating the lower-bound will turn out to be a little easier in this case, though that is not always so. It depends on the number we're estimating and what notation we are using for our estimates. Here we will be trying to estimate the Mega using my Hyper-E Notation.
First, before we continue, let me establish this convenient functional power notation. Let:
n[3]_k = n[3][3][3]...[3][3][3] w/k [3]s
Let's begin by getting a rough idea of what's going on.
We know that:
Mega = 256[3]_256
The result of applying the first triangle would be:
256256[3]_255
Without actually computing 256256 let's proceed with more and more triangles, using the exponential notation, and see what happens:
We can now see a pattern emerging. We see that each time we apply another triangle, the number of 256's doubles. So applying the first triangle we get 2, the second we get 4, then 8, 16, 32, and so on. At each stage we see that the 256's are packed into pairs, which are packed into packs of 4, which are packed into packs of 8, and so on. We can figure that by the end of this process we will have 2256 256's, and the expression would look something like this:
2256 is itself a pretty big number. It's exact decimal form is:
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936
That is a 78-digit number, approximately 1.15x10^77 in Scientific Notation or E77.063678 in E Notation. It can be pretty easy to dismiss this number as not all that big when we're working with numbers like a Mega. However if the above image were expanded until the 256's contained within it were about a centimeter tall the entire expression would stretch out roughly 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (E48) times the radius of the observable universe. In other words, if the above image is simply a scale model of the full expression written out in ordinary notation, then the observable universe would be smaller than a proton on this image! And let us not forget ... this is in it's unevaluated form!! So there are ALOT of 256s there to work out!!!
This at least can give us an image in our minds of what a Mega would look like. But it may make it seem like there is really no hope for simplifying such a complex expression into something simple and comprehensible. While this is true for any exact expression, it is not impossible to create a simple and understandable estimate.
As a first attempt at an estimate we can observe that if we removed all the parenthesis and simply had a power tower of 2256 256's, this would have to be much much larger than a Mega. This is because when computing a series of exponentiation's, the way to produce the largest possible number is almost exclusively to work from right-to-left. (There are some interesting exceptions when working with real numbers, but that's outside the scope of this article) So we can say that:
Mega ~< 256^^(2^256)
But how do we know for sure that this will evaluate to a larger number? Does it require difficult mathematics to confirm this? No. All it takes is a little High School mathematics (with power towers thrown in). Specifically we again need the Exponential Laws. Recall that:
(bp)q = b(p*q)
&
bp * bq = bp+q
Now observe the following example:
(bb)(bb) = bb*b^b = bb^(b+1)
For the sake of argument we will assume that b is a Counting Number & b>1. We can then go on to show that:
bb^(b+1) < bb^(b+b) = bb^(2b) =< bb^(bb) = bb^b^2 =< bb^b^b
The conclusion that we can draw from this is that:
(bb)(bb) < bbbb : b>1
In other words, we don't simply add the heights of the power towers , 2+2, and conclude that the result is b^b^b^b (a power tower with 4 b's). It turns out that if b is a Counting Number greater than 1, then this will be an overestimate. We can generalize this result to any Whole Number height greater than 2. Begin by imagining:
(b^^k)^(b^^k) : b>1, k>2
Following the Exponential Laws, and the first law of tetration, which states:
b^^p = b^(b^^(p-1))
We can prove that:
(b^^k)^(b^^k) < b^^(2k)
Here's the proof:
(b^^k)^(b^^k) = (b^(b^^(k-1)))^(b^^k) [1st Law of Tetration] =
b^((b^^(k-1))*b^^k) [Product Law of Exponentiation] =
b^(b^(b^^(k-2))*b^(b^^(k-1))) [1st Law of Tetration] =
b^b^(b^^(k-2)+b^^(k-1)) [Summation Law of Exponentiation]
< b^b^(b^^(k-1)+b^^(k-1))
= b^b^(2*(b^^(k-1))
=< b^b^(b*(b^^(k-1))
= b^b^b^(1+b^^(k-2))
[note: if k=3 then k-2=1 and it is sufficient to point out that b^^1=b, and 1+b^^1 = 1+b < b+b =< b^b. This would mean that (b^^3)^(b^^3) < b^^5 < b^^6, again proving our assertion. If k>3 continue until the top most exponent in the power tower = b+1 as illustrated below]
< b^b^b^b^(1+b^^(k-3))
[Note that the number of b's is 1 greater than the number being subtracted from k]
< ...
< b^b^b^ ... ^b^b^(1+b^^(k-(k-1)) w/(k-1+1) b's before lead exponent
= b^b^b^ ... ^b^b^(1+b) = b^(1+b)#k
b^(1+b)#k < b^(b+b)#k = b^(2b)#k =< b^(bb)#k = b^(b2)#k =
b^2#(k+1) =< b^b#(k+1) = b^1#(k+2) < b^1#(k+k) = b^1#(2k)
Thus we conclude that:
(b^^k)^(b^^k) < b^^(2k) : b,k>1
This has direct bearing on showing that Mega < 2^^(2^256). From the above lemma (which I'll call the additive tetrate lemma or ATL) we know that:
(256^256)^(256^256) < 256^256^256^256 = 256^^4
So we conclude that 256[3]_2 < 256^^4
Furthermore:
256[3]_3 = (256[3]_2)^(256[3]_2) < (256^^4)^(256^^4) < 256^^8
As you can probably tell, we could continue in this manner to eventually show that:
256[3]_256 < 256^^(2^256)
So we have now bounded the Mega from above. That's significant because it means we now have a definite way to prove that certain numbers are bigger than a Mega. As it turns out however, this is an absurd overestimate for the Mega. The Number we have just described is roughly a Mega, itself inside an additional E77 triangles!!!
So we know that the Mega must end with ...2656. More digits can be computed but the amount of computation seems to grow. The greatest difficultly is in constructing the table that serves as a computational shortcut.
I was actually able to go much further than the last 4 digits, but this quickly becomes impractical by hand. To go beyond the last 4 digits I wrote a program on my TI-89 Calculator back in november of 2012. I first computing the lengths of the orders for higher digits. This consistently follows the pattern of powers of 5 that we see in the first 4 digits. For 5-digits the order length is 625, for 6-digits it's 3125, and in general we find that the order length is 5^(n-1) where n is the number of desired digits. Once the order was known I would run my program based on this number. Rather than pull up Modulus values from a table it would construct each Modulus value from scratch by simply multiplying 256 by itself the appropriate number of times and taking the Modulus of the desired number of digits.
To make sure my program was running correctly I first computed the last digit, then the 2 last digits, than the last 3, and then the last 4. In all cases the program produced the correct result. To compute the last 3 digits took my calculator a mere 94 seconds, and to compute the last 4 digits took my calculator a only about 7 minutes.
After this confirmation test I ran the program to compute the last 5 digits. I obtained the result 42656 after only 36 minutes of computation (a reasonable amount of time). Next I ran the program to compute the last 6 digits. I obtained the result 742656 after 2 hours and 50 minutes of computation. Based on the computational times I determined that the run time would grow about 5 fold with each additional digit. The "7th digit" would therefore take my calculator something around 15 hours. I know from past experience of running large programs on my calculator that it's battery life is only somewhere from 24 to 30 hours of heavy computation. Since I didn't want to use up half my calculators battery life just to find the 7th digit I decided to write a program on my laptop instead.
One of the advantages of writing a program on my laptop was that I could use arrays to store a "look up table" of values. The reason the TI-89 program (dubbed "Mega") was taking so long to carry out it's calculation was simply because it was performing redundant calculations. When I was able to store a look up-table on my laptop it made the computation lightning fast, because it only needed to be executed once, resulting in a 256 fold increase in speed. In fact it was many times better than that because my laptops processing speed is so much faster than my calculator. As a test of my laptop program I computed the last 6 digits. It was able to compute this in a fraction of a second! I then used it to quickly compute the last 7, and then last 8 digits, which it calculated in mere seconds. The result I obtained for the last 8 digits was 60742656.
Naturally I next ran the laptop program, called "Mega_Com" to compute the last 9 digits. This computation however froze the program! After a bit of poking around I determined that it had failed to compute the look up-table because it had never returned to the base value of 256. For a moment it seemed like I had hit a brick wall and maybe the 9th digit was unobtainable. After some speculation and some leaps of intuition however I realized that the order length was closely related to the fact that 256 = 2^8. It is not a coincidence that I ran into a problem precisely after 8 digits because 100,000,000 has the prime factorization (2^8)(5^8). The trick around this was to use the new base value 65,536 which is 2^16. This base value can be used all the way up to 16-digits of accuracy.
Using this new base, and after some code alteration I was able to compute the 9th,10th, 11th and 12th digit without much difficultly. The last 12 digits are 539660742656. At this point a new snag was reached because the necessary look up table for 13 digits of accuracy would require more RAM than I have on my laptop! What this meant was that I couldn't use the table-method as a shortcut and would have to perform the lengthy calculations just like my Calculator program had done. Because of how much faster my laptop is however I was able to not only compute the 13th digit, but was able to compute the 14th digit as well. The last 13 digits took only 30 minutes for my computer, and the last 14 digits took 2 hours and 42 minutes. The last 14 digits are as follows:
Mega = ................................................................................................93539660742656
This is the most digits of mega I'd seen computed up to that point. I had planned to try and at least obtain the 15th digit using a new method which would balance memory and speed but I got preoccupied with many other projects, including other articles for this website. Based on this preliminary research into the Mega I believed that the digits of a Mega are actually more expensive to compute than even the digits of Graham's Number. The difficultly seemed to stem from the fact that unlike Graham's Number and those defined using Knuth Up-arrows, the "base" of exponentiation in the Mega keeps changing as we apply the 256 triangles. This results in more complex behavior that doesn't give us the nifty shortcuts that power towers tend to in the last digits (we'll learn how to obtain the last digits of Graham's Number later in another article). As it turns out however upon further analysis, the digits of Graham's Number prove to be slightly more difficult because one needs to iterate the calculation until the digits actually stabilize. Despite the calculation at each step being slightly simpler, the number of iterations is directly proportional to the number of desired digits. Mega on the other hand is always fixed at 256 iterations, and so eventually it proves easier to compute than the digits of graham's number, despite the initial lag.
Even though more digits could theoretically be computed using the methods I've developed here, the amount of memory and computation grows exponentially so that within short order (well before the last 100 digits) the task becomes impractical to impossible. Worse yet, I was already at risk of overflowing the 64-bit unsigned integer data type in the running of my program; the largest integer data type available! This would impede further progress much beyond the 16th digit. To go further would require the writing of a custom data-type in another programming language. The only way around these limitations would be to discover another more powerful method that would act as a shortcut to the necessary memory and computation requirements.
Even with better methods however, in practice the hard limit of millions or billions of digits would be reached long before we computed the Mega in full. Worse yet, we can only compute a few billion of the least significant digits. We can't actually compute the leading digit even though we know it must be either a 1,2,3,4,5,6,7,8, or 9. We'll never know exactly how the Mega begins or even exactly how many digits it has, but we can take some comfort in the fact that at least a Mega is still small enough and amicable enough that we can know it must end with ...93539660742656. Can we do better? Turns out we can...
#################################################
[under construction]
#################################################
For me this is the closest I can get to an encounter with the divine, for I really believe that these digits exist, prior and independently of their computation. Some might say that such things reside only in the mind of God, but for me it is enough to say that they exist, even when no mind will ever know them at all. For like all mathematical truths, they are contained in the premises even when we can't follow them to their conclusion. For me, that is the ultimate Platonic reality, and it's out there just waiting to be uncovered. And unlike God we needn't speculate what it is ... we can really know, and all we have to do is start computing.
Surely that's an exaggeration, right?! Nope. That is not an exaggerated statement, it's fairly accurate. The reason for the great overestimate is due to that fact that a much better upper-bound is:
(b^^k)^(b^^k) < b^^(k+2)
Although I won't go over it here this result can be established via the Left Associative Tetrates Lemma, also known as the Knuth Arrow Theorem (KAT). This important result is proven in my googological paper, "A Theorem for Knuth Arrows". The paper can be found in the Appendix here.
Actually you can already see this result reflected in the proof we did. Applying the above upper-bound provides an even better estimate that reduces the estimated size of a Mega dramatically. Firstly observe that:
256[3] = 256^256 = 256^^2
256[3]_2 = (256^256)^(256^256) = (256^^2)^^2
256[3]_3 = ((256^256)^(256^256))^((256^256)^(256^256)) = ((256^^2)^^2)^^2
etc.
So we can write a Mega much much more compactly as:
(((( ... ((((256^^2)^^2)^^2)^^2) ... )^^2)^^2)^^2)^^2 w/256 2's
Interestingly this expression is actually small enough that we could write it out in full if we wanted to. Not only does it now fit in the observable universe, but right in your living room. THAT is already a dramatic change. Now we observe that:
(b^^k)^(b^^k) = (b^^k)^^2 < b^^(k+2)
So it follows that:
(256^^2)^^2 < 256^^(2+2) = 256^^4
((256^^2)^^2)^^2 < (256^^4)^^2 < 256^^(4+2) = 256^^6
(((256^^2)^^2)^^2)^^2 < (256^^6)^^2 < 256^^(6+2) = 256^^8
etc.
Thus we conclude that:
Mega < 256^^512
This is a very big improvement. However we can actually improve it even further than this! You might get the impression that the Mega is quickly shrinking and maybe isn't all that big after all. For this reason let's develop a lower bound before we continue to improve the upper-bound to ensure that the Mega is in fact very large.
Developing a lower bound proves to be very easy. Recall that 256^256 turned out to be a 617 digit number. It follows from this that 256^256 >= E616. In fact we know that 256^256 > 3E616 from the decimal expansion and therefore 256^256 > E616. Now we observe:
(256^256)^(256^256) > (10^616)^(10^616) = 10^(616*10^616) > 10^(100*10^616) = 10^10^618
To continue simply observe:
256[3]_3 > (10^10^618)^(10^10^618) > (10)^(10^10^618) = 10^10^10^618 = E618#3
256[3]_4 > (E618#3)^(E618#3) > 10^(E618#3) = E618#4
...
Mega = 256[3]_256 > E618#256
In comparison with our estimates this one is extremely close to the actual value. It can be used to give a "tetrational" order of magnitude. Simply note that:
E618#256 > E10#256 = E1#257 = 10^^257 =
10^10^10^10^10^ ... ... ^10^10^10 w/257 10s
So the Mega is larger than a power tower of 10s 257 terms high. At this point it becomes very easy to see that a Mega is much much bigger than many other famed big numbers. Observe that:
googol = 10^100 = 10^10^2 < 10^10^10 = 10^^3 < 10^^257 < Mega
googolplex = 10^10^100 = 10^10^10^2 < 10^10^10^10 = 10^^4 < 10^^257 < Mega
Skewes' Number < 10^10^10^34 < 10^10^10^100 =
10^10^10^10^2 < 10^10^10^10^10 = 10^^5 < 10^^257 < Mega
Second Skewes' Number < 10^10^10^1000 = 10^10^10^10^3 < 10^10^10^10^10
= 10^^5 < 10^^257 < Mega
NONE OF THESE NUMBERS EVEN COME CLOSE! The largest of them is still less than a power tower of 10s only 5 terms high! Even the grangol is much smaller:
grangol = E100#100 < E(10^10)#100 = E1#102 = 10^^102 < 10^^257 < Mega
That should alleviate any concern that a Mega is small. However we still haven't quite pinned down the Mega. The best bounds we currently have still have a humongous gulf:
E618#256 < Mega < 256^512
Our goal will now be to sandwich the Mega between two consecutive tetrational orders of magnitude. Just as 10N is considered a order of magnitude estimate for a number, we can consider 10^^N to be a tetrational order of magnitude for numbers too large for the ordinary concept of magnitude. In fact it would be impossible to estimate the Mega within an Exponential order of magnitude as the number of digits is itself a number with at least 10^^256+1 digits!!!
To succeed in our tetrational estimate we need to come up with a tight upper-bound for Mega. This is a little more tricky than the lower-bound, because we won't be able to simply discard extra terms, but must incorporate them. There is an easy way to do this that will allow us to easily get a tetrational estimate, but as I will show after, we can get an even tighter bound for even better accuracy.
So again we begin with 256^256. We observe that:
256^256 < E617
We proceed in the following manner:
256[3]_2 < (10^617)^(10^617) = 10^(617*10^617) < 10^(1000*10^617) = 10^10^620
256[3]_3 < (10^10^620)^(10^10^620) = 10^(10^620 * 10^10^620) =
10^10^(620 + 10^620)
The next step is a critical one, and it's important to understand the principle at work here. Focus on "620+10^620". We know that adding 620 to 10^620 is not going to have much of an effect, but we can't simply ignore it, because then we would be "rounding down". But we observe that:
10^620 = 10000 ... ... 0000 w/620 zeroes
so 10^620+620 = 1000 ... ... 0620 w/617 zeroes before the "620"
We can see that the 620 has no hope of even turning the leading digit into a 2. So that must mean that:
620+10^620 < 2*10^620
That may already seem like a bad overestimate, but we're going to make it even worse:
2*10^620 < 10*10^620 = 10^621
So we conclude that:
(10^10^620)^(10^10^620) < 10^10^10^621
The reason we do this, is it makes all subsequent steps much easier. Despite what seems like gross overestimating, this will result in a superbly good overestimate, at least compare to what we've had so far. Continuing we observe that:
256[3]_4 < (10^10^10^621)^(10^10^10^621)
= 10^10^(10^621+10^10^621)
< 10^10^10^(1+10^621)
< 10^10^10^10^622
256[3]_5 < (10^10^10^10^622)^(10^10^10^10^622)
= 10^10^(10^10^622+10^10^10^622)
< 10^10^10^(1+10^10^622)
< 10^10^10^10^10^623
...
...
256[3]_256 < 10^10^10^10^ ... ... ^10^10^10^(623+251) w/256 10s =
E874#256
Now to obtain our tetrational-order overestimate we simply observe that:
E874#256 < E10,000,000,000#256 = E(10^10)#256 = E1#258 = 10^^258
So our tetrational-order bounds are:
10^^257 < Mega < 10^^258
Not bad at all. What at first seemed impossible to estimate has now been narrowed down quite a bit; and yet there is still a tremendous gulf between these numbers. Roughly speaking you'd have to take the lower-bound and raise it to the power of itself to get in the vicinity of the upper-bound:
(10^^257)^(10^^257) ~ 10^^258
This may be hard to believe at first. After all the upper-bound is a power tower with only 1 additional term, yet what I'm saying implies that:
(10^^257)^(10^^257) ~ (10)^(10^^257)
How is that possible when 10^^257 is SO MUCH BIGGER THAN 10! Keep in mind that we are only talking about approximate figures here. Of coarse (10)^(10^^257) must be less than (10^^257)^(10^^257), but from a tetrational-order perspective they are virtually the same thing.
Point being, that there is still a considerable gulf between our bounds. Can we do better? Yes we can, but we must now pay more attention to fine points of detail.
What I want to try now is to get a Leading Power estimate on a Mega. To explain what that means, let me explain a little about so called level-index number formats. Recall that scientific notation is just a rough way of expressing very large (exponential class) numbers. In computers this format is represented as something called a floating point number. This number format is used to perform calculations on large numbers using only a small amount of memory and processing. The method can generally get the order of magnitude, along with a few of the lead digits down correctly, even though truth be told it is only an estimate. For numbers in the tetrational range an even more radical number format would be needed; one that currently isn't implemented in most computers, although it has already been designed. Robert Munafo's HyperCalc is an example of just such a number format. The format is fairly simple, and mimics that of scientific notation.
We can begin by observing that any positive real number can theoretically be represented as:
10x where x is a real number
Furthermore any positive real number greater than 1 can theoretically be represented as:
10^10^x where x is a real number
Further still any positive real number greater than 10 can theoretically be represented as:
10^10^10^x where x is a real number
With each additional 10 the minimum value expressible becomes 10 to the power of the previous minimum. So we can see that any number can be expressed as a power tower of 10s with a "leading power" , x. If we want x is be fairly small we simply add more 10s to the tower. In this format any number can be expressed as the number of 10s in the tower, and the top most exponent. So let:
Ex#N = 10^10^ ... ^10^10^x w/N 10s
N is a Whole Number but we can allow x to be a decimal. What I want to do here is to bound Mega as follows:
Ek#N < Mega < E(k+1)#N
Where k is an Integer. Currently, if we take our best bounds we have:
E618#256 < Mega < E874#256
While these are very good bounds, and they were pretty easy to obtain, the distance between 618 and 874 is pretty wide. It's actually quite feasible to get a leading exponent bound. We begin by getting a lower-bound, but this time we try to be more exacting in our methods. First observe that:
256^256 > 3.23E616
We follow pretty much as before, but we discard less along the way:
256[3]_2 > (3.23*10^616)^(3.23*10^616) = 3.23*10^(616*3.23*10^616) =
3.23*10^(1989.68*10^616) > 10^(1.98968*10^619) > 10^10^619
256[3]_3 > (10^10^619)^(10^10^619) = 10^10^(619+10^619) > 10^10^10^619
...
256[3]_256 > E619#256
The additional effort may not have seemed like much of an improvement, but in fact we can now show that this is the correct leading-exponent lower-bound by proving that Mega < E620#256:
256^256 < 3.24E616
256[3]_2 < (3.24*10^616)^(3.24*10^616) =
3.24*10^(616*3.24*10^616) =
3.24*10^(1995.84*10^616) =
3.24*10^(1.99584*10^619)
< 10*10^(1.99584*10^619)
= 10^(1+1.99584*10^619)
< 10^(1.99585*10^619)
< 10^(2*10^619)
256[3]_3 < (10^(2E619))^(10^(2E619)) =
10^(2E619 * 10^(2E619))
< 10^(E620 * 10^(2E619))
= 10^10^(620+2E619)
Let N = 620+2E619
256[3]_4 < (10^10^N)^(10^10^N) =
10^10^(N+10^N) =
10^10^(620+2E619+10^(620+2E619))
< 10^10^(E620+10^(620+2E619))
< 10^10^10^(621+2E619)
Let N2 = 10^(621+2E619)
256[3]_5 < (10^10^N2)^(10^10^N2)
= 10^10^(N2+10^N2) =
10^10^(10^(621+2E619)+10^10^(621+2E619))
< 10^10^(10^10^620+10^10^(621+2E619))
< 10^10^10^(1+10^(621+2E619))
< 10^10^10^10^(622+2E619)
...
...
256[3]_256 < 10^10^10^ ... ^10^10^10^(622+251+2E619) w/255 10s
= E(873+2E619)#255
< E(3E619)#255
< E(E620)#255
= E620#256
Thus we can now bound the Mega:
E619#256 < Mega < E620#256
This may seem like a tight bound. However you would have to raise the lower-bound approximately to the power of E620#255 to get the upper-bound!
(E619#256)^(E620#255) ~ E620#256
That's a tremendous gulf! The power we are raising to is itself a power tower with 256 terms! Seen this way you begin to realize that this is a large field on which we've sandwiched the Mega, and just where between these bounds is it?! Surely we can do better than that? Just how accurately can we bound the Mega?
To really push the limits we have to go beyond hand-calculations and start using brute force computer calculation. Rather than approximate 256^256, we can use the exact value, since we were able to compute it. Using this with 9999 digits of precision I'm able to arrive at the next level of approximation. I will be using a "large number calculator" to get precise results. You can find these online. The one I'm using can be found here.
The result I get is:
E19 923 739 028 520 154 087 706 422 945 147 014 652 916 223 529 059 455 829 739 546
236757 445 592 829 019 852 096 549 871 643 037 231 579 555 867 729 029 727 837 739
722 687243 833 688 041 650 758 866 703 047 684 995 147 926 044 802 500 789 969 233
229 482 277620 428 871 361 665 114 606 086 501 621 360 310 636 409 247 822 506 979
293 012 834 235605 892 457 887 360 583 787 492 777 424 798 206 285 182 369 042 469
497 447 438 158 240050 711 323 245 053 205 431 372 163 355 524 614 258 748 270 064
178 183 600 550 138 767745 559 315 784 832 858 638 844 869 498 054 620 521 042 914
198 455 705 585 134 437 206064 557 323 165 937 735 931 605 786 380 378 378 018 264
857 422 432 758 696 743 477 636 091 751 483 267 310 595 348 292 927 018 011 128 165
226 311 150 554 708 199 087 683 524 760 666 293 693 562 405 279 021 537#255
~<
Mega
~<
E19 923 739 028 520 154 087 706 422 945 147 014 652 916 223 529 059 455 829 739 546
236 757 445 592 829 019 852 096 549 871 643 037 231 579 555 867 729 029 727 837 739
722 687 243 833 688 041 650 758 866 703 047 684 995 147 926 044 802 500 789 969 233
229 482 277 620 428 871 361 665 114 606 086 501 621 360 310 636 409 247 822 506 979
293 012 834 235 605 892 457 887 360 583 787 492 777 424 798 206 285 182 369 042 469
497 447 438 158 240 050 711 323 245 053 205 431 372 163 355 524 614 258 748 270 064
178 183 600 550 138 767 745 559 315 784 832 858 638 844 869 498 054 620 521 042 914
198 455 705 585 134 437 206 064 557 323 165 937 735 931 605 786 380 378 378 018 264
857 422 432 758 696 743 477 636 091 751 483 267 310 595 348 292 927 018 011 128 165
226 311 150 554 708 199 087 683 524 760 666 293 693 562 405 279 021 538#255
Robert Munafo's own highly accurate estimation of a Mega has:
Mega ~ E(1.992373902865 X 10619)#255
Robert Munafo's estimate agrees with mine up to 11 decimal places. I used bold/red to highlight the difference. It may seem that we have drastically improved the bounds, and we have ... though maybe not quite as drastically as you might think. You'd still have to raise the lower-bound to the power of approximately E620#254 to get the upper-bound. What we have done is simply reduce the required exponent from E620#255 to E620#254. The power tower now has just one less 10. It might seem that with some more effort we could get it down to E620#253, and a little more E620#252 ... until we got it within something reasonably small. However the next step is already impossible. The best we can do is extend the number 19,923, ... ,537 with it's decimal point with a few billion additional digits even with the most powerful computers. This may seem like a big deal, but we'd have to compute about E619 additional digits after the decimal point to properly compute the next level of the approximation. So the best we can do is get about a billion digits of the next level. We will never know what the next level down is ... let alone know every digit of Mega itself.
Mega exists somewhere between the ginormous gulf of the above best bounds, but we will never know exactly where. We have now more or less reached the practical limits of estimating the Mega. Even with our best technology we will never be able to get bounds so accurate that the lower-bound raised to a googolplex is the upper-bound, or even a googolduplex, or a googoltriplex, googolquadriplex, etc. Not even close. The best we will ever get is about E620#254.
The last 14 digits of the Mega
Despite the fact that we can never even come close to a "good estimate" of a Mega, let alone compute it's exact value, it isn't difficult to show that the ones place digit must be a 6. In fact this is common knowledge in the googology community. Note that any number of the form XX...XX6^N must end in a 6. Simply observe that:
6^2 = 36.
Now note that when we take the product of integers we simply have to take the product of their ones place values to determine the ones place value of the result. Example:
267,384 x 38,492 = 10,292,144,928
4 x 2 = 8
What this means is that the product of any two integers ending in 6 will also end in 6. Furthermore any positive integer power of a number ending in 6 must end in 6. 256^256 must end in 6 because 256 ends in 6. So we get some result of the form XX...XX6. When we go to apply the next triangle we would just get:
XX...XX6XX...XX6
But since the base ends in 6, any positive integer power will end in 6 and thus this also results in some number of the form XX...XX6. As you can see this will continue indefinitely, so that means the Mega must be of the form:
...6
So even though we can't compute it, we can at least know it's last digit. In fact we can go ahead and find the tens digit as well. This time we look at the powers of 56:
56^1 = 56
56^2 = 3136
56^3 = 175,616
56^4 = 9,834,496
56^5 = 550,731,776
56^6 = 30,840,979,456
56^7 = 1,727,094,849,536
56^8 = 96,717,311,574,016
The only feature that is of importance here is the last two digits. These cycle through the pattern 56,36,16,96,76. This is an order of 5, and we can use the remainder of the power divided by 5 to determine where on the cycle it is. If there is no remainder we get 76, remainder=1 results in 56, remainder=2 results in 36, etc. Since any power ending in 6 must be remainder=1 the result of XX...XX56XX...XX6 = XX...XX56. We can now exploit this fact to find the tens digit of the Mega. Simply observe:
256256 = X56XX6 = XX...XX56
XX...XX56XX..XX56 = XX...XX56XX..XXX6 = XXX ... ... XXX56
XXX ... ... XXX56XXX ... ... XXX56 = XXX ... ... XX56XXX ... ... XXXX6 = XXXX ... ... ... XXXX56
...
Therefore the Mega must be of the form:
... ... ... ... 56
We can even get the hundreds digit but we must go up another level of abstraction to do so efficiently. For this we study the last 3 digits in the powers of 256. This tedious search results in the following order of 25:
256, 536, 216, 296, 776,
656, 936, 616, 696, 176,
056, 336, 016, 096, 576,
456, 736, 416, 496, 976,
856, 136, 816, 896, 376,
Of particular interest to us here is the 1st, 6th, 11th, 16th, and 21st member of this sequence, forming the first column of the above table. The reason will become clear momentarily. What we want to know when we raise any number which ends in any of the above triplets is what the remainder of that power is when dividing by 25. Since 100 is divisible by 25 we don't actually need to look at any digits other than the last two to determine the remainder. We now observe that:
256256 = 256250 * 2566
In other words the power 256 has remainder 6 when divided by 25. So we know that 256256 is of the form XX...XX656. This is confirmed by our earlier computation of 256256.
What we do next requires an extra level of abstraction. Firstly observe that:
6562 = XXX336
6563 = XXXXXX416
6564 = XX...XX896
6565 = XX...XX776
Now 336 is the 12th member of our sequence, 416 is the 18th, and 896 is the 24th. You can confirm for yourself using the above table. Now remember that 656 is the 6th member. Now observe that if we multiply the membership number (6 in this case) with the power we get the resulting member! So 6562 results in the 6x2 member, 6563 results in the 6x3 member and 6564 results in the 6x4 member. What about 6565? It results in the 5th member. This might seem strange since 6x5 = 30, but notice that 30/25 leaves remainder 5. In other words it cycles around. This fact allows us to establish yet a larger and more abstract cycle that will let us discover what the last three digits of a Mega really are.
To understand this clearly, I'll use the notation {n} for the nth member of the triplet sequence. Now we can say that:
{1} = XX...XX256
{2} = XX...XX536
{3} = XX...XX216
etc.
Furthermore let "A mod N" be the remainder from dividing A by N.
With that notation we state the following lemma:
{n}k = {(n*k) mod 25}
We now apply this to our problem to obtain the following meta-sequence:
256 = {1}
256256 = {1}256 = {(1*256) mod 25} = {256 mod 25} = {6} = XX...XX656
XX..XX656XX..XX656 = {6}XX..XXX56 = {(6*XX..XXX56) mod 25} = {XX...XXX36 mod 25} = {36 mod 25} = {11}
{11}XX..XX056 = {11}XX..XXX56 = {(11*XX..XXX56) mod 25} = {XX...XX16 mod 25} = {16 mod 25} = {16}
{16}XX...XX456 = {(16*XX...XXX56) mod 25} = {XX...XXX96 mod 25} = {96 mod 25} = {21}
{21}XX...XX856 = {(21*XX..XXX56) mod 25} = {XX..XXX76 mod 25} = {76 mod 25} = {1}
As you can see we have a 5 stage meta-cycle: {1}, {6}, {11}, {16}, {21}. To determine which part of the meta-cycle the Mega is on simply observe that:
256 = {1}
256[3] = {6}
256)[3]_2 = {11}
256[3]_3 = {16}
256[3]_4 = {21}
256[3]_5 = {1}
256[3]_6 = {6}
...
256[3]_10 = {1}
...
256[3]_15 = {1}
...
...
256[3]_255 = {1}
Mega = 256[3]_256 = {6} = ... ... ... ... ... ... ... ... 656
Note the additional level of difficultly that went with figuring out the last 3 digits. Going one additional level to 4 digits proves to be computationally much more difficult. The 4 digit order is 125 members long. To make use of this we must construct the complete table of 125 members. This takes a lot more computation than the 3 digit order, but it's still small enough to obtain easily enough.
Because 256 is itself not even a 4-digit number (although technically it can be expressed as 0256), I decided to convert 256^256 in the following manner:
256256 = 65,536128 = X5536128
For this reason I've decided to use "5536" as my "radix" value. What we want to do now is create a table of the 4-digit moduli of the powers of 5536. This produces the following order of 125 quadruplets:
4-digit Power Modulus of 5536 Table
5536, 7296, 0656, 1616, 6176,
0336, 0096, 1456, 0416, 2976,
5136, 2896, 2256, 9216, 9776,
9936, 5696, 3056, 8016, 6576,
4736, 8496, 3856, 6816, 3376,
9536, 1296, 4656, 5616, 0176,
4336, 4096, 5456, 4416, 6976,
9136, 6896, 6256, 3216, 3776,
3936, 9696, 7056, 2016, 0576,
8736, 2496, 7856, 0816, 7376,
3536, 5296, 8656, 9616, 4176,
8336, 8096, 9456, 8416, 0976,
3136, 0896, 0256, 7216, 7776,
7936, 3696, 1056, 6016, 4576,
2736, 6496, 1856, 4816, 1376,
7536, 9296, 2656, 3616, 8176,
2336, 2096, 3456, 2416, 4976,
7136, 4896, 4256, 1216, 1776,
1936, 7696, 5056, 0016, 8576,
6736, 0496, 5856, 8816, 5376,
1536, 3296, 6656, 7616, 2176,
6336, 6096, 7456, 6416, 8976,
1136, 8896, 8256, 5216, 5776,
5936, 1696, 9056, 4016, 2576,
0736, 4496, 9856, 2816, 9376,
Once this table is constructed it provides amazing computational efficiency for our particular task. The same lemma we used earlier applies, but with a new modulus (125):
{n}k = { (n*k) mod 125}
Furthermore we needn't actually use k in the computation. Only the last 3 digits of k are needed for the calculation because 1000 mod 125 = 0, so all the other digits have no effect on the result. With this in mind we can now easily apply a similiar approach to what we had used to get the last 3 digits of Mega. We can begin as follows:
256[3] = {1}^128 = {128 mod 125} = {3} = XX...XX0656
256[3]_2 = {3}^(XX..XX656) = {3*656 mod 125} = {1968 mod 125} = {968 mod 125} = {93}
256[3]_3 = {93}^(XX..XX5056) = {93*056 mod 125} = {208 mod 125} = {83}
...
Contininuing on in this manner eventually reveals a meta-cycle of 25 members. This is illustrated in the table below: