triton_megiston_moser
3.2.6
Steinhaus-Moser Polygon Notation Part II
Triton, Megiston, Moser
Introduction
In part I we explored the mega, a number coined by Hugo Steinhaus, and one among many numbers we can define using Steinhaus-Moser Polygon Notation. In this article we expand our study to the broader implications of Steinhaus-Moser Polygon Notation by exploring the many more numbers we can create...
Three in a Circle
From the definition of Steinhaus-Moser polygons it should be clear that any time we place a 1 inside any polygon, it always returns 1. For example:
1[5] = 1[4] = 1[3] = 1^1 = 1
In general 1[k+1] = 1[k], therefore for any 1[m] it will always eventually reduce to 1[3] = 1^1 = 1. In googology we refer to this as a degenerate case. The key thing of a degenerate case is that no matter how powerful the operator is involved, the number remains something very small (less than 10 usually) and nowhere near the caliber of numbers generated by the operator, and therefore not representative of the class of numbers the operator typically produces. Depending on the particular system, degenerate cases may be a single value, or several small values. Usually there is a critical point which is the smallest non-degenerate case. The output is usually non-trivially large and representative of the kinds of numbers typical for that function to produce.
For Steinhaus-Moser notation, 1 is a degenerate case, while 2 will result in a typically vast value, excluding only the cases of 2 in a triangle and 2 in a square:
2[3] = 2^2 = 4
2[4] = 2[3][3] = 2^2[3] = 4[3] = 4^4 = 256
However "2" does still not produce values that really reveal the full power of the particular operator. "3" will give a value which gives one a better idea of what to expect later in the sequence:
3[4] = 3[3][3][3] = 3^3[3][3] = 27[3][3] = 27^27[3] ~ 10^38[3] ~ 10^10^38
Notice what a huge jump it is from 1[4] = 1 , 2[4] = 256 to 3[4] ~ 10^10^38. So "2"s actually produce a semi-degenerate case.
Now let's consider the circle or pentagonal operator, [5]. Firstly we have:
1[5] = 1
Which is about as small as you can typically get in googology since 1 or 0 is typically the default value, and therefore the smallest value possible. Next we have mega:
mega = 2[5] ~ 10^10^10^10^...^10^10^10^10^619 w/256 10s
This seems like such an insane leap from 1! And yet mega is still semi-degenerate. You might get the impression from this that the numbers in the sequences become power towers whose height is proportional to the input. That "3 in a circle/pentagon", 3[5], is probably a power tower of maybe a few thousand 10s or something. But it's so much worse than that! Just how much worse?! ...
3[5] is a number which neither Steinhaus nor Moser provided a name for, but I dubbed it the triton while I was researching the last digits of numbers generated using Steinhaus-Moser Notation. Just how BIG is the triton? Let's find out...
The Size of Triton
We begin with 3[5]:
3[5] = 3[4][4][4]
Remember mega only involved two [4] operators. Just what is going to happen with 3? Well first let's expand out the first [4]:
3[4][4][4] = 3[3][3][3][4][4]
Now let's start applying the [3] operators:
3[3][3][3][4][4]
3^3[3][3][4][4]
27[3][3][4][4]
27^27[3][4][4]
443,426,488,243,037,769,948,249,630,619,149,892,803[3][4][4]
443,426,...,892,803443,426,...,892,803[3][4][4]
At this point we hit a calculation impasse. So let's instead devise a lower bound for triton. Firstly we have 10^38 < 443,426,488,243,037,769,948,249,630,619,149,892,803. So we can say:
27^27[3][4][4] > 10^38[3][4][4] = (10^38)^(10^38)[4][4] = 10^(38*10^38)[4][4]
> 10^10^38[4][4] = 10^10^38[3]_10^10^38[4]
o_0;
How are we going to apply 10^10^38 [3] operators? Simple. We know that:
10^N[3] > 10^10^N
So each [3] operator has an effect less than taking the input and raising 10 to that power. So the end result would be...
10^10^10^10^10^ ... ^10^10^10^10^10^38[4]
where there are 2+10^10^38 10s
In Hyper-E Notation we may write this as:
E38#(2+10^10^38)
The 2 can be safely ignored here and we can say this is still larger than
E38#(10^10^38)
This is way way way more than having 256 10s. The number of 10s is itself a hyper-exponential number! Even if we just compared the height of the towers alone mega would be utterly dwarfed before this! And we aren't done yet ... we still have one more [4] operator to apply:
E38#(10^10^38)[4]
= E38#(10^10^38)[3]_E38#(10^10^38)
> E38#(10^10^38+E38#(10^10^38))
> E38#(E38#(10^10^38))
Let's unpack this a little bit. This means triton is larger than:
10^10^10^10^10^ ... ^10^10^10^10^10^38
where there are
10^10^10^10^10^ ... ^10^10^10^10^10^38 10s
where there are
10^10^38 10s
This is just beyond imagining. mega now looks very tiny in comparison. Even the height of the power tower lower bounding triton is a value we can't really wrap our brains around and must describe with an unimaginably large power tower number.
This kind of number is so big in fact that the Stack Notation is a little inconvenient. For this reason I will introduce a three-argument extension. Let:
Ea#b#1 = Ea#b
and
Ea#b#c = Ea#(Ea#b#(c-1))
Using this we can then say that:
E38#(E38#(10^10^38)) = E38#(E38#(E38#2)) = E38#(E38#(E38#2#1))
= E38#(E38#2#2) = E38#2#3
and furthermore:
E38#2#3 < triton
So we know triton is a very very large number, and that it isn't difficult to bound from below. But just how much bigger is triton than E38#2#3? To answer that we will also want to upper-bound triton. The answer might surprise you.
To create an upperbound we begin with the observation that:
27^27 < 10^39
Now we resume from:
27^27[3][4][4] < 10^39[3][4][4]
= (10^39)^(10^39)[4][4] = 10^(39*10^39)[4][4]
< 10^(100*10^39)[4][4] = 10^(10^2*10^39)[4][4]
= 10^10^(2+39)[4][4]
= 10^10^41[4][4]
= 10^10^41[3]_10^10^41[4]
At this point it seems like we reach an impasse. While it's true that x[3] > 10^x, what possible upper-bound could we place on it? If we can the 10 with any other number, it will still not be an upper-bound if x is greater than that number. The secret is to develop a systematic way to account for accretions. Although naively we might assume that this can have a drastic effect on the value, in fact the effect of the accretions on the topmost exponent is strictly bounded no matter how tall the power tower becomes. To understand why we observe that:
x+10^y < 10^(y+1) provided x < 10^y
From this we can make the further observation that:
(10^10^10^x)^(10^10^10^x)
= 10^(10^10^x * 10^10^10^x)
= 10^10^(10^x + 10^10^x)
< 10^10^10^(1+10^x)
This process may be iterated. For example, let y = 1+10^x:
then (10^10^10^y)^(10^10^10^y)
< 10^10^10^(1+10^y)
= 10^10^10^(1+10^(1+10^x))
We will keep accumulating these "1"s throughout the power tower. This forms what we will call the zipper. At any particular stage the zipper may be completely accumulated into the topmost exponent. It turns out it's effect is always less than adding 1 to the topmost exponent. To understand this consider an expression of the form:
10^10^10^(1+10^(1+10^(1+10^( ... (1+10^x)) ... ))))
notice that in each instance the 1 is being added to some massive power of 10. Since each 10 is being raised to a positive integer (we assume "x" is itself a positive integer), this means each is at least 10^1 = 10. Therefore each 1 can ascend one level up the tower and be added to the exponent instead to get a larger value:
1+10^n < 10^(n+1) : An is a positive integer
From that we gather the following:
10^10^10^(1+10^(1+10^(1+10^( ... (1+10^x)) ... ))))
< 10^10^10^(10^(1+1+10^(1+10^( ... (1+10^x)) ... ))))
This is again the technique of the ascending-one. But this time ascending-ones accumulate with each other, but their sum never exceeds 2. The reason for this is simple. 2 is also less than 10^n for any positive integer n, so the same principle applies:
10^10^10^(10^(1+1+10^(1+10^( ... (1+10^x)) ... ))))
= 10^10^10^(10^(2+10^(1+10^( ... (1+10^x)) ... ))))
< 10^10^10^(10^(10^(1+1+10^( ... (1+10^x)) ... ))))
= 10^10^10^(10^(10^(2+10^( ... (1+10^x)) ... ))))
So we now get an ascending-two. The ascending-two is the place where the zipper is closed. It will be followed by a series of 1s. As the 2 ascends the 1s disappear, until all that is left is a single 2:
10^10^10^10^10^10^ ... ^10^10^(2+10^x)
At this point we may ascend one more time, and the end result is the accumulation of a single unit on the topmost exponent:
10^10^10^10^10^10^ ... ^10^10^10^(x+1)
Notice that it doesn't matter how long the zipper is, so all the accruement never actually amounts to more than a +1 on top (good thing interest rates don't work that way!). Now let's apply these principles to our current dilemma. First we have:
(10^10^41)^(10^10^41)
= 10^(10^41 * 10^10^41)
= 10^10^(41+10^41)
Continuing onwards
(10^10^(41+10^41))^(10^10^(41+10^41))
= 10^(10^(41+10^41)*10^10^(41+10^41))
= 10^10^(41+10^41+10^(41+10^41))
< 10^10^(10^42+10^(41+10^41))
< 10^10^10^(42+10^41)
Now let x = 42+10^41
(10^10^10^x)^(10^10^10^x)
< 10^10^10^(1+10^x) = 10^10^10^(1+10^(42+10^41))
Now let y = 1+10^(42+10^41)
(10^10^10^y)^(10^10^10^y)
< 10^10^10^(1+10^y)
= 10^10^10^(1+10^(1+10^(42+10^41)))
As you can see we are starting to form a zipper of ones. This time there is a "42" at the top of the zipper but this is of no concern. The point is that for any number of applications of [3] applied to 10^10^41 we will get an upper-bound of the form:
10^10^10^(1+10^(1+10^(1+10^( ... (1+10^(1+10^(42+10^41))) ... ))))
Zipping up the 1s into 2s we eventually get
...2+10^(42+10^41)...
This is still much smaller than
...10^(43+10^41)...
which is still much smaller than
...10^10^42
but just how many 10s are going to be in the resulting power tower? Well we can see that:
10^10^41[3] < 10^10^(41+10^41) < 10^10^10^42 = E42#3
10^10^41[3]_2 < 10^10^10^(42+10^41) < 10^10^10^10^42 = E42#4
10^10^41[3]_3 < 10^10^10^(1+10^(42+10^41)) < 10^10^10^10^10^42 = E42#5
so in general
10^10^41[3]_n < E42#(n+2)
Therefore:
10^10^41[3]_10^10^41 < E42#(2+10^10^41)
We want to simplify this further while still always upper-bounding. We can do the following:
E42#(2+10^10^41) < E42#(10^(1+10^41)) < E42#(10^10^42)
= E42#(E42#2) = E42#2#2
So now all that's left is to compute:
E42#2#2[4] = E42#2#2[3]_E42#2#2
The zipper technique tells us however that the topmost exponent will only increase by 1. We also know the height of the power tower will be increased exactly by the number of [3] operators applied. From this we gather the following:
E42#2#2[3]_E42#2#2 < E43#(10^10^42+E42#(10^10^42))
Again we want to simplify and upper-bound. But how do we simplify the second argument?! We can use a combination of techniques. Firstly we can use the ascending-one technique to say that y+10^10^10^...^10^x < 10^10^10^...^10^(x+1) : y < 10^10^10^...^10^x. Certainly 10^10^42 is much smaller than E42#2#2, so we can have an ascending 1:
E43#(10^10^42+E42#(10^10^42))
< E43#(E43#(10^10^42))
Now for the sake of symmetry we can say:
E43#(E43#(10^10^42)) < E43#(E43#(10^10^43))
= E43#(E43#(E43#2)) = E43#2#3
So we have now upper-bounded a triton. We can now say:
E38#2#3 < triton < E43#2#3
Can we tighten this bound? For example, could we find an "n" such that:
En#2#3 < triton < E(n+1)#2#3
To accomplish this we will have to refine our technique quite a bit. Firstly we tighten the lower and upper bounds on 27^27:
4*10^38 < 27^27 < 5*10^38
Getting the correct lower bound isn't too difficult. Remember that to compute triton we need to compute 27^27[3][4][4]. So first we come up with a simple lower bound for 27^27[3]:
(4*10^38)^(4*10^38) > (10^38)^(4*10^38) = 10^(38*4*10^38) = 10^(152*10^38)
> 10^(100*10^38) = 10^(10^2*10^38) = 10^10^40
From here the rest is easy:
10^10^40[4] > E40#(2+10^10^40) > E40#(10^10^40) = E40#2#2
and
E40#(10^10^40)[4] > E40#(10^10^40+E40#(10^10^40))
> E40#(E40#(10^10^40)) = E40#(E40#2#2)
= E40#2#3
Done.
The upper-bound is a great deal more of a hassle. First we upper bound 27^27[3], but this time we don't simplify it to a single topmost exponent:
(5*10^38)^(5*10^38)
This time we can't simply eliminate the "5" at the bottom. Instead:
(5*10^38)^(5*10^38) < (10*10^38)^(5*10^38) = (10^39)^(5*10^38)
= 10^(39*5*10^38) = 10^(195*10^38)
If we attempt to upper bound this as 10^10^41 then we will not be able to prove that triton < E41#2#3, because we will have to eventually accumulate at least 1 extra unit on the topmost exponent. So instead we leave it as 10^(195*10^38), even though this is more complicated. Now we attempt to generate a zipper sequence, by repeatedly raising the previous number to its own power and creating a simple upper bound to the result:
10^(195*10^38)[3]
= (10^(195*10^38))^(10^(195*10^38))
= 10^(195*10^38*10^(195*10^38))
< 10^(10^41*10^(195*10^38))
= 10^10^(41+195*10^38)
< 10^10^(10^38+195*10^38)
= 10^10^(196*10^38)
Now raise that to its own power:
10^10^(196*10^38)[3]
= (10^10^(196*10^38))^(10^10^(196*10^38))
= 10^(10^(196*10^38)*10^10^(196*10^38))
= 10^10^(196*10^38+10^(196*10^38))
< 10^10^(10^41+10^(196*10^38))
< 10^10^10^(1+196*10^38)
< 10^10^10^(10^38+196*10^38)
= 10^10^10^(197*10^38)
Not bad. So 10^(195*10^38)[3]_2 < 10^10^10^(197*10^38)
And now we have a power tower of the form 10^10^10^x. So let x = 197*10^38.
Then we have:
10^10^10^x[3]
= (10^10^10^x)^(10^10^10^x)
= 10^(10^10^x*10^10^10^x)
= 10^10^(10^x+10^10^x)
< 10^10^10^(1+10^x)
By iterating this formula we eventually get a zipper of the form:
10^10^10^(1+10^(1+10^(1+10^( ... (1+10^(1+10^(1+10^(197*10^38)))) ... ))))
The number of "1"s here corresponds to the number of times we apply the [3] operator to 10^10^10^x. In all such cases we may simplify the zipper by removing the lowest ranking "1" and ascending it to the next rank, where it combines with the next "1" to make a "2". The "2" may then be zipped up until it reaches below "x":
...2+10^(197*10^38)...
< ...10^(1+197*10^38)...
< ...10^(198*10^38)...
The number of 10s below (198*10^38) will be the number of "1"s +3. So from this we may say:
10^10^10^(197*10^38)[3]_n < E(198*10^38)#(n+3)
combining this with:
10^(195*10^38)[3]_2 < 10^10^10^(197*10^38)
We get:
10^(195*10^38)[3]_2[3]_n < E(198*10^38)#(n+3)
This is enough to upper bound 10^(195*10^38)[4]. Observe:
10^(195*10^38)[4]
= 10^(195*10^38)[3]_10^(195*10^38)
= 10^(195*10^38)[3]_2[3]_10^(195*10^38)-2
< E(198*10^38)#(10^(195*10^38)-2+3)
= E(198*10^38)#(10^(195*10^38)+1)
< E(198*10^38)#(10^(1+195*10^38))
< E(198*10^38)#(10^(196*10^38))
< E(198*10^38)#(10^(198*10^38))
= E(198*10^38)#1#2
Now we have only one more [4] operator to apply. We now have a very tall power tower of the form:
10^10^10^10^ ... ^10^10^10^10^(198*10^38)
where there are 10^(198*10^38) 10s
When raising very tall power towers to their own power like this, it has almost no noticable effect. Let "T" be a very tall power tower. It still holds that:
(10^10^10^T)[3] < 10^10^10^(1+10^T)
By applying many [3] operators we can create a zipper of 1s, which can then be zipped up into a single 2:
(10^10^10^T)[3]_n < ...2+10^T... < 10^(1+T)
At this critical juncture there is no longer any "1"s above, so instead of a zipper we just get an ascending 1 until it reaches the top of the power tower. So we can say, for sufficiently tall power towers, Em#n that:
(Em#n)[3]_k < E(m+1)#(n+k)
Therefore:
E(198*10^38)#(10^(198*10^38))[3]_E(198*10^38)#(10^(198*10^38))
<
E(1+198*10^38)#(10^(198*10^38)+E(198*10^38)#(10^(198*10^38)))
Now it's time to simplify and upper bound this mess:
E(1+198*10^38)#(10^(198*10^38)+E(198*10^38)#(10^(198*10^38)))
< E(199*10^38)#(10^(198*10^38)+E(198*10^38)#(10^(198*10^38)))
The blue portion is much much smaller than E(198*10^38)#(10^(198*10^38). It can be transformed into an ascending-one, that eventually get's added to the topmost exponent:
E(199*10^38)#(10^(198*10^38)+E(198*10^38)#(10^(198*10^38)))
<< E(199*10^38)#(E(1+198*10^38)#(10^(198*10^38)))
<< E(199*10^38)#(E(199*10^38)#(10^(198*10^38)))
At this point we can simplify the topmost exponents to 10^41 each in turn to obtain a nice and clean upper bound:
E(199*10^38)#(E(199*10^38)#(10^(198*10^38)))
<< E(10^41)#(E(199*10^38)#(10^(198*10^38))
= E41#(1+E(199*10^38)#(10^(198*10^38)))
<< E41#(E(1+199*10^38)#(10^(198*10^38)))
<< E41#(E(200*10^38)#(10^(198*10^38)))
<< E41#(E(10^41)#(10^(198*10^38)))
= E41#(E41#(1+10^(198*10^38)))
<< E41#(E41#(10^(1+198*10^38)))
<< E41#(E41#(10^(199*10^38)))
<< E41#(E41#(10^10^41))
<< E41#(E41#(E41#2))
= E41#(E41#2#2)
= E41#2#3
After all that we can finally conclude:
E40#2#3 < triton < E41#2#3
These maybe the most accurate bounds ever placed on a triton. Yet the gulf between these numbers is simply mind blowing. Recall, the lower bound is:
10^10^10^...^10^10^10^40
where there are 10^10^10^...^10^10^10^40 10s
where there are 10^10^40 10s
versus the upper bound:
10^10^10^10^...^10^10^10^10^41
where there are 10^10^10^10^...^10^10^10^10^41 10s
where there are 10^10^41 10s
Might not seem like a big deal, but remember that 10^10^41 is (10^10^40)^10. Now imagine the heights of E40#2#2 versus E41#2#2.
E40#2#2 would be much much taller than even the observable universe could fit, yet its height would be dwarfed by a factor of its own height 9 times before we got to the height of E41#2#2. This makes E40#2#2 look like a point next to a line segment in comparison to E41#2#2.
And it gets worse, E40#2#3 is a power tower whose height would have to be raised to its own power approximately 10^10^41 times to get to a height comparable to E41#2#3.
With power towers so vastly different in height, we have barely pinned down the triton at all. Yet we will never be able to say what the smallest power tower of 10s greater than triton is, let alone what the minimum top exponent would be. Such "precision", as imprecise as it may be, is a level of precision we could never hope to get triton. Such measures might be possible for little piddling numbers like mega but a god like triton would not hear of it!
So triton is BIG in a way that makes the mega look microscopic, when just an article ago it seemed like a god-like number itself! What can we know about the digits of triton? Are they are harder to compute than mega? Let's find out:
The last 11 digits of triton
It turns out that computing the last digits of triton is much harder than mega. While the digits of mega can be computed in polynomial time (cubic time specifically), the digits of triton have to be computed in exponential time. To understand why we need to dig a little into the methodology.
Firstly triton is just a VERY LARGE power of 3, at the end of the day. Therefore understanding the last digits of powers of 3 is vital here. Because 3 is relatively prime to all powers of 10 however we have a nice guarantee that there exists a power, p , greater than 1 such that 3^p mod 10^n = 1. This guarantees that 3^(p+1) mod 10^n = 3, so that we get a sequence of order p. If p also happens to be a factor of 10^n then we have an ideal situation for computing the last "n" digits. It appears that this only fails when n=1. In this case we have the following sequence:
Let S_i = 3^i % 10
This gives us:
S_1 = 3^1 % 10 = 3
S_2 = 3^2 % 10 = 9
S_3 = 3^3 % 10 = 7
S_4 = 3^4 % 10 = 1
Thus the order of S is 4. But 4 is not a factor of 10. So when we go to compute the last digit of 3^i where we only know the last digit of i and i is greater than 10, we run into the problem that we don't have enough information to determine what i % 4 is, and thus we can't find the last digit. However this problem disappears when n=2. Here we have the following order:
S_i = 3^i % 100
S = {03,09,27,81,43,29,87,61,83,49,47,41,23,69,07,21,63,89,67,01}
This has an order of 20 which is a factor of 100. This us allows us to determine the last 2 digits of 3^i as long as we know the last 2 digits of i. This allows us to perform modular arithmetic recursively. But knowing this is still not enough to compute the last two digits of triton. For this we also need a meta-order, M_i = 3[3]_i % 100. Using modular exponentiation, we can easily derive this:
3[3] = 3^3 = 27 mod 100
27[3] = 27^27 = (3^3)^27 = 3^81 = 03 mod 100
So as you can see we have a meta order:
M = {27,03}
With only 2 members this makes computing the last digits very easy:
3[5]
= 3[4][4][4]
= 3[3]_3[4][4]
The meta_order tells us that 3[3]_i = 27 when "i" is odd, and 03 when "i" is even:
3[3]_3[4][4]
= ...27[4][4]
= ...27[3]_...27[4]
To convert this into an expression of the form 3[3]_i we simply replace ...27 with 3[3]_3:
3[3]_3[3]_...27[4]
= 3[3]_...30[4]
= ...03[4]
= ...03[3]_...03
= ...27
Finding the last 3 digits is also a relatively simple task. First we ensure that the order of 3^i is a factor of 1000 by computing 3^1001 % 1000. If this is 003 then we can simply use the last 3 digits of "i" in 3^i to compute it modulo 1000. The fastest way to do this is to first compute 3^10, then 3^100, then 3^1000, and then multiply by 3, all while modding by 1000 of course:
(mod 1000)
3^1 = 003
3^10 = 049
3^100 = 001
3^1000 = 001
3^1001 = 003
In fact while performing this calculation we can see that 3^101 would also evaluate to 003 modulo 1000. So the order is also a factor of 100. The reason we instead use 1000 is because we can then treat all these different cases using the same algorithm without having to know the order in advance. As long as we return to the "seed" value at 10^n+1 we know the order is a factor of 10^n and that we can recursively apply modular arithmetic. Next we find the meta-order using the power sequence. The numbers highlighted in blue are known as the "mode", while the numbers in red are called the congruence. Both are needed in order to carry out the iterative process:
(mod 1000)
3[3]_1 = 003^003 = 027
3[3]_2 = 027^027 = 003^(003*027) = 003^081 = 803
3[3]_3 = 803^803 = 003^(081*803) = 003^043 = 627
3[3]_4 = 627^627 = 003^(043*627) = 003^961 = 603
3[3]_5 = 603^603 = 003^(961*603) = 003^483 = 227
3[3]_6 = 227^227 = 003^(483*227) = 003^641 = 403
3[3]_7 = 403^403 = 003^(641*403) = 003^323 = 827
3[3]_8 = 827^827 = 003^(323*827) = 003^121 = 203
3[3]_9 = 203^203 = 003^(121*203) = 003^563 = 427
3[3]_10 = 427^427 = 003^(563*427) = 003^401 = 003
Since 003 is the seed value we have now successfully returned to the seed in 10 iterations, so the order of the meta-sequence is 10. This means we only need to know the last digit of the number of [3]s being applied to 003 to figure out what the last 3 digits are. This calculation now follows pretty easily:
3[4][4][4]
= 3[3]_3[4][4]
= ...627[4][4]
= ...627[3]_...627[4]
= 3[3]_...630[4]
= ...003[4]
= ...003[3]_...003
= ...627
So the last 3 digits of triton are 627. From this point on the meta-order multiplies by a factor of 5, and then past 6 digits by 10. So the meta-order quickly becomes too long to compute by hand. So at this point we let the computer take over. I wrote a program, triton2.exe , which was able to compute the last 11 digits of triton. It does this in a manner similar to the approach shown above.
First it asks for a "precision", the number of digits to be computed, call it "n". Then it checks that 3^(10^n+1)%10^n = 3. It does this in 10*n steps, getting first 3^10 by going through 3^1,3^2,3^3, ... etc. then 3^100 by going through 3^10,3^20,3^30,...etc. In this way the first phase of the program is strictly linear with the number of digits. It therefore only takes a tiny fraction of a second to complete on any reasonable input. Numbers are stored as arrays of digits, so overflow, in the usual sense is not possible. One would need to have a number with several hundred million digits before overflow of the ram would occur. We never need that many digits because the other phases of the program have such long runtimes that only for the smallest number of digits is program completion practically possible.
The second phase checks the meta-order, beginning with the seed value 3. It repeatedly raises a number to its own power, generating the meta-sequence one at a time. One might well ask "why can we just do 3[3]_10 , 3[3]_100 ,3[3]_1000, like we can with powers and do all this in linear time?". The reason is because the properties of the [3] operator are very different. For powers we have that (3^10)^i = 3^(10i), in both ordinary and modular arithmetic. This means if we know the 10th value of the sequence we can skip by 10s. But knowing 3[3]_10 gives us no such advantage. Where as a power can be broken down into a product:
3^100 = 3^10*3^10*3^10*3^10*3^10*3^10*3^10*3^10*3^10*3^10
The [3] operator can only break up into a sum of iterations:
3[3]_100 = 3[3]_10+10+10+10+10+10+10+10+10+10
= 3[3]_10[3]_10[3]_10[3]_10[3]_10[3]_10[3]_10[3]_10[3]_10[3]_10
going from 3[3]_n to 3[3]_n+10 ends up being a matter of raising 3[3]_n to its own power 10 times. It is possible there is a computational short cut that is possible but I know of no such trick. This brings us back to the same problem that hampered the computation of mega initially. Only this time there is no handy "modular exponentiation" trick to reduce it to polynomial time. The result: we must compute the entire meta-order, which grows exponentially in proportion to 10^n. Thus the runtime for this phase is exponential on the order of 10^n.
When the meta-order is found the final phase takes place. It begins with the seed value 3, and applies the [4] operator 3 times. To do this it simply takes the current congruence, C, and computes C[4] using C[3]_C = 3[3]_hypermode[3]_C = 3[3]_hypermode+C. hypermode+C is then modded by the meta-order. The values of 3[3]_i are not stored in memory because then space requirements would also be exponential. Instead each 3[3]_i is computed on the fly, starting from the seed. So each of these 3 applications of the [4] operator is itself 10^n runtime. This gives us a runtime of n+4*10^n which we simplify as exponential 10^n.
So what are the results? Here is a table of results and runtimes for triton2.exe:
It will take an estimated 130 hours to compute the 12th digit. Some optimization may be possible, but the main difficultly is that we don't have a method for computing arbitrary members of a[3]_i
The Megiston
The megiston was the only other number, besides mega, named by Steinhaus in his original polygon notation. He didn't say much about it though and left it as an exercise for the reader to get a feel for how large this number is. Here we will actually come up with some fairly decent bounds for a number this size.
As mentioned earlier, mega doesn't really tap into the full power of the circle/pentagonal operator as it is a semi-degenerate case. Megiston is a different story ... it reveals the full power of the pentagonal operator and it turns out to be on par with pentation.
We begin with the definition:
megiston = 10[5]
Let's see how far we can get...
10[5] = 10[4][4][4][4][4][4][4][4][4][4] = 10[4]_10
10[4][4]_9 = 10[3]_10[4]_9
= 10^10[3]_9[4]_9
= (10^10)^(10^10)[3]_8[4]_9
= 10^(10*10^10)[3]_8[4]_9
= 10^10^11[3]_8[4]_9
So far this is exact. But for the sake of simplicity we can say that 10^10^10 < 10^10^11. Then we can observe that:
(10^10^10)^(10^10^10) > (10)^(10^10^10) = 10^10^10^10
(10^10^10^10)^(10^10^10^10) > (10)^(10^10^10^10) = 10^10^10^10^10
and in general...
(E1#k)^(E1#k) > (10)^(E1#k) = E1#(k+1)
From these two facts we may gather that:
10[3]_2 > 10^10^10
10[3]_3 > 10^10^10^10
10[3]_4 > 10^10^10^10^10
...
10[3]_10 > E1#11
Now we move on to the next [4] operator, of which there are still 9 left. We have:
E1#11[4]_9
= E1#11[3]_E1#11[4]_8
To quickly create lower bounds we may make the general observation that:
E1#k[3]_i > E1#(k+i)
So...
E1#11[3]_E1#11 > E1#(11+E1#11) > E1#(E1#11) = E1#11#2
We still have 8 more [4] operators to apply. Each application is just a map from x-->x[3]_x
So we have:
10[4]_2 > E1#11#2
10[4]_3 > E1#11#2[3]_E1#11#2 > E1#(E1#11+E1#11#2) > E1#(E1#11#2) = E1#11#3
10[4]_4 > E1#11#3[3]_E1#11#3 > E1#(E1#11#2+E1#11#3) > E1#(E1#11#3) = E1#11#4
...
So we conclude:
10[4]_10 > E1#11#10
therefore:
E1#11#10 < megiston
To understand this number it's:
10^10^10^ ... ^10^10^10
where there are
10^10^10^ .... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^ ... ^10^10^10 10s
where there are
10^10^10^10^10^10^10^10^10^10^10 10s
where there are 11 10s
Unlike a triton where there is few enough layers that we can kind of wrap our brains around it, megiston has too many layers to really grasp all at once. But notice that E1#11#3 is already bigger.
Can we devise an upper bound as well. Yes, with a small degree of difficultly.
Firstly we go back to 10^10^11. This is smaller than 10^10^10^10. Furthermore we have that (10^^a)^^b < 10^^(a+b) (Knuth Arrow Theorem). So:
(10^10^10^10)^(10^10^10^10) = (10^^4)^(10^^4) = (10^^4)^^2 < 10^^6
(10^^6)^^2 < 10^^8
(10^^8)^^2 < 10^^10
etc.
From this we gather that:
10[3]_2 < 10^10^10^10
10[3]_3 < 10^10^10^10^10^10 = 10^^6
10[3]_4 < 10^^8
...
10[3]_10 < 10^^20 = E1#20
We can further say:
E1#k[3]_i < E1#(k+2i)
From this we can obtain an upper bound as follows:
10[4] < E1#20
10[4]_2 < E1#20[3]_E1#20 < E1#(20+2*E1#20) < E1#(10*E1#20)
: let x = 10*E1#20
10[4]_3 < E1#x[3]_E1#x < E1#(x+E1#x) < E1#(10*E1#x)
: let x_2 = 10*E1#x
10[4]_4 < E1#(x_2)[3]_E1#(x_2) < E1#(x_2+E1#x_2) < E1#(10*E1#x_2)
: let x_3 = 10*E1#x_2
etc.
10[4]_10 < E1#(x_8)[3]_E1#(x_8) < E1#(x_8+E1#(x_8))
< E1#(10*E1#(x_8))
Now to simplify this we make the following observation:
10*E1#k < E2#k
We obtain this from the ascending-one method. But this implies:
E2#k < E10#k = E1#(k+1)
:: 10*E1#k << E1#(k+1)
Applying this we can simplify, in a recursive fashion, our upperbound for a megiston:
E1#(10*E1#(x_8)) < E1#(E1#(1+x_8))
= E1#(1+x_8)#2
= E1#(1+10*E1#x_7)#2 < E1#(1+E1#(1+x_7))#2 < E1#(10*E1#(1+x_7))#2
= E1#(E1#(2+x_7))#2 = E1#(2+x_7)#3
= E1#(2+10*E1#x_6)#3 < E1#(2+E1#(1+x_6))#3
< E1#(10*E1#(1+x_6))#3 < E1#(E1#(2+x_6)#3 = E1#(2+x_6)#4
= ... = E1#(2+x_5)#5 = ... = E1#(2+x_4)#6 = ... = E1#(2+x_3)#7
= ... = E1#(2+x_2)#8 = ... = E1#(2+x)#9
= E1#(2+10*E1#20)#9 < E1#(11*E1#20)#9 = E1#(11*10^E1#19)#9
< E1#(100*10^E1#19)#9 = E1#(10^(2+E1#19))#9
< E1#(10^(10*E1#19))#9 < E1#(10^E1#20)#9 = E1#(E1#21)#9
= E1#21#10
So we can now bound megiston as follows:
E1#11#10 < megiston < E1#21#10
These aren't very tight bounds, even by the loose standards of numbers this size. We can refine this to the point where we can find bounds of the form:
Ea#b#c < megiston < E(a+1)#b#c
The lower bound is not very difficult to obtain at all. We just begin with:
10[3]_2 = 10^10^11
and from there with the observation that:
Em#n[3]_i > Em#(n+i)
Therefore:
10[3]_10 = 10[3]_2[3]_8 = 10^10^11[3]_8 = E11#2[3]_8 > E11#10
So we obtain 10[4] > E11#10
going further we have:
10[4]_2 > E11#10[3]_E11#10 > E11#(10+E11#10) > E11#(E11#10) = E11#10#2
10[4]_3 > E11#10#2[3]_E11#10#2 > E11#(E11#10+E11#10#2) > E11#(E11#10#2)
= E11#10#3
...
10[4]_4 > E11#10#10
Obtaining a similarly tight upper bound is not very easy. It requires us to carry a lot of extra baggage before simplifying. So we begin making by keeping the exact answer for a while longer:
10[3]_2 = 10^10^11
10[3]_3 = (10^10^11)^(10^10^11) = 10^(10^11*10^10^11) = 10^10^(11+10^11)
10[3]_4 = (10^10^(11+10^11))^(10^10^(11+10^11))
= 10^(10^(11+10^11)*10^10^(11+10^11))
= 10^10^(11+10^11+10^(11+10^11))
At this point we'll do our first bit of simplifying...
< 10^10^(10^12+10^(11+10^11)) < 10^10^10^(12+10^11) : Let x = 12+10^11
10[3]_5 < (10^10^10^x)^(10^10^10^x)
= 10^(10^10^x*10^10^10^x) = 10^10^(10^x+10^10^x)
< 10^10^10^(1+10^x)
This you should recognize as the zipper technique covered in the bounding of triton. Continuing onwards we obtain:
10[3]_6 < 10^10^10^(1+10^(1+10^x))
10[3]_7 < 10^10^10^(1+10^(1+10^(1+10^x)))
10[3]_8 < 10^10^10^(1+10^(1+10^(1+10^(1+10^x))))
10[3]_9 < 10^10^10^(1+10^(1+10^(1+10^(1+10^(1+10^x)))))
10[3]_10 < 10^10^10^(1+10^(1+10^(1+10^(1+10^(1+10^(1+10^x))))))
< 10^10^10^10^(2+10^(1+10^(1+10^(1+10^(1+10^x)))))
< 10^10^10^10^10^(2+10^(1+10^(1+10^(1+10^x))))
< 10^10^10^10^10^10^(2+10^(1+10^(1+10^x)))
< 10^10^10^10^10^10^10^(2+10^(1+10^x))
< 10^10^10^10^10^10^10^10^(2+10^x)
= 10^10^10^10^10^10^10^10^(2+10^(12+10^11))
< 10^10^10^10^10^10^10^10^10^(13+10^11)
= E(13+10^11)#9
Now we can make the general observation that:
Em#n [3]_i < E(m+1)#(n+i)
via a combination of a zipper and an ascending-one. From this we can quickly obtain an relatively tight upper bound on megiston:
10[4]_2 < E(13+10^11)#9 [3]_E(13+10^11)#9
< E(14+10^11)#(9+E(13+10^11)#9)
< E(14+10^11)#(E(14+10^11)#9) = E(14+10^11)#9#2
10[4]_3 < E(14+10^11)#9#2 [3]_E(14+10^11)#9#2
< E(15+10^11)#(E(14+10^11)#9+E(14+10^11)#9#2)
= E(15+10^11)#(E(14+10^11)#9+E(14+10^11)#(E(14+10^11)#9))
< E(15+10^11)#(E(15+10^11)#(E(14+10^11)#9))
< E(15+10^11)#(E(15+10^11)#(E(15+10^11)#9))
= E(15+10^11)#9#3
Let m = 15+10^11
10[4]_4 < Em#9#3 [3]_Em#9#3
< E(m+1)#(Em#9#2+Em#9#3)
= E(m+1)#(Em#9#2+Em#(Em#9#2))
< E(m+1)#(E(m+1)#(Em#9#2))
< E(m+1)#(E(m+1)#(E(m+1)#9#2))
= E(16+10^11)#9#4
Let 10[4]_k < E(12+k+10^11)#9#k
and let m = 12+k+10^11
10[4]_k+1 < Em#9#k [3]_Em#9#k
< E(m+1)#(Em#9#(k-1)+Em#9#k)
= E(m+1)#(Em#9#(k-1)+Em#(Em#9#(k-1)))
< E(m+1)#(E(m+1)#(Em#9#(k-1)))
< E(m+1)#(E(m+1)#(E(m+1)#9#(k-1)))
= E(m+1)#9#(k+1)
= E(12+k+10^11+1)#9#(k+1)
= E(12+(k+1)+10^11)#9#(k+1)
Therefore:
10[4]_10 < E(22+10^11)#9#10
This expands to:
10^10^10^ ... ^10^10^10^(22+10^11)
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^10^10^10^10^10^10^(22+10^11) 10s
w/9 10s
Working from the top down observe the following
10^10^10^ ... ^10^10^10^(22+10^11) w/E(22+10^11)#9#9 10s
< 10^10^10^ ... ^10^10^10^10^12 w/1+E(22+10^11)#9#9 10s
Then we observe that:
1+E(22+10^11)#9#9 < E(23+10^11)#9#9
< E12#(1+E(22+10^11)#9#8)
1+E(22+10^11)#9#8
is in turn less than E12#(1+E(22+10^11)#9#7)
This continues downward creating a kind of hyper-ascending-one through out the power towers:
10^10^10^ ... ^10^10^10^(22+10^11)
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^10^10^10^10^10^10^(22+10^11) 10s
w/9 10s
<
10^10^10^ ... ^10^10^10^10^12
w/1+10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^10^10^10^10^10^10^(22+10^11) 10s
w/9 10s
<
10^10^10^ ... ^10^10^10^10^12
w/10^10^10^ ... ^10^10^10^10^12 10s
w/1+10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^ ... ^10^10^10^(22+10^11) 10s
w/10^10^10^10^10^10^10^10^10^(22+10^11) 10s
w/9 10s
<
...
<
10^10^10^ ... ^10^10^10^10^12
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/1+10^10^10^10^10^10^10^10^10^(22+10^11) 10s
w/9 10s
<
10^10^10^ ... ^10^10^10^10^12
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^10^10^10^10^10^10^10^12 10s
w/1+9 10s
=
10^10^10^ ... ^10^10^10^10^12
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^ ... ^10^10^10^10^12 10s
w/10^10^10^10^10^10^10^10^10^10^12 10s
w/10 10s
which is E12#10#10
So we have demonstrated that:
E11#10#10 < megiston < E12#10#10
The Megalith
An even larger value than the one's Steinhaus mentioned can only be created if we extend the concept of the operators beyond the circle operator. With Moser's extension many even larger numbers are possible. The simplest of these involves the smallest new operator, the hexagon, with the smallest non-trivial input, 2. I'm talking about "2 in a hexagon", 2[6], or what I will call the "Megalith". The Megalith, called the megision by Aarex Tiaokhiao, and a-ooga by Matt Hudelson, is on a completely different class that a mega, triton, or megiston. To understand why it suffices to just expand 2[6] to:
2[6] = 2[5][5] = mega[5]
So a great mega is a mega in a circle!!! Just going from mega to triton was a massive leap. Can we come to any grips with the size of this number. Sure we can, but not without the usual loss of precision associated with entering a new class of numbers. Here it suffices to observe that:
mega > E619#256
That mega[3]_i > E619#(256+i) > E619#i
So we have:
mega[5] = mega[4]_mega
> (E619#mega)[4]_mega-1
= (E619#256#2)[4]_mega-1
> (E619#256#3)[4]_mega-2
...
> (E619#256#mega)[4]_mega-(mega-1)
= (E619#256#mega)[4]_1
> E619#256#(mega+1)
> E619#256#mega
= E619#256#1#2
So just how big is E619#256#1#2? It's ...
10^10^10^10^ ... ^10^10^10^10^619
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/10^10^10^10^ ... ^10^10^10^10^619 10s
...
...
...
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/10^10^10^10^ ... ^10^10^10^10^619 10s
w/256 10s
Where the number of power towers is itself E619#256.
Let's see if we can develop a reasonably tight upper-bound without getting too bogged down in details.
Firstly we have mega < E620#256
Next we observe that:
(Em#n)[3]_i < E(m+i)#(n+i)
So...
mega[5] = mega[4]_mega
= mega[4][4]_mega-1
= mega[3]_mega[4]_mega-1
< E(620+E620#256)#(256+E620#256)
< E(E621#256)#(256+E620#256)
= E621#(256+256+E620#256)
< E621#(E621#256)
= E621#256#2
Now let's make the more general observation that:
Em#n[3]_Em#n
< E(m+Em#n)#(n+Em#n)
< E(E(m+1)#n)#(n+Em#n)
= E(m+1)#(n+n+Em#n)
< E(m+1)#(E(m+1)#n)
So we have:
E621#256#2 = E621#(E621#256)
Let n = E621#256
So we have:
E621#n [4] = E621#n [3]_E621#n
< E622#(E622#n)
< E622#(E622#256#2)
= E622#256#3
More generally if we have : Em#256#k = Em#n
then...
Em#n [3]_Em#n
< E(m+1)#(E(m+1)#n)
= E(m+1)#(E(m+1)#(Em#256#(k-1)))
< E(m+1)#(E(m+1)#(E(m+1)#256#(k-1)))
= E(m+1)#256#(k+1)
So ...
E620#256#1 [4]_i
< E(620+i)#256#(1+i)
So we have:
mega[4]_mega < E(620+E620#256)#256#(1+E620#256)
< E(E621#256)#256#(1+E620#256)
Let m = E621#256
Em#256#(1+E620#256)
= Em#(Em#256#(E620#256))
E621#(256+Em#256#(E620#256))
= E621#(256+E621#(256+Em#256#(E620#256-1)))
=
...
E621#(256+E621#(256+E621#(256+ ... (256+E621#(256+256)) ... )))
<
E621#(E622#(E622#(E622# ... (E622#512) ... )))
< E622#(E622#(E622#(E622# ... (E622#512) ... )))
= E622#512#(1+E620#256)
< E622#512#(E622#512)
= E622#512#1#2
So now we can bound the megalith:
E619#256#1#2 < megalith < E622#512#1#2
These are fairly tight bounds for a number so large. None the less the gap between them is enormous to contemplate. One is a number generated by E619#256 powers towers describing power towers, but the other requires E622#512 power towers, a much larger number. When one also factors in how fast the height of the power towers is growing one gets an inkling of just how googol-scopic E619#256#1#2 is compare to E622#512#1#2.