Googology Wiki
Register
Advertisement
Googology Wiki

How to compute more last digits of Mega[]

I know how compute more last digits of Mega, if you want to compute the last d digits:

1) Compute last d digits of 256^256

2) Take this digits, raise it to power of itself, find last digit. Using exponential laws you can decompose number by factors, for example:

24593590^24593590 = (24593590^16777216)*(24593590^4194304)*(24593590^2097152)*(24593590^1048576)*(24593590^262144)*(24593590^131072)*(24593590^65536)*(24593590^16384)*(24593590^1024)*(24593590^128)*(24593590^32)*(24593590^16)*(24593590^4)*(24593590^2)

That is, we expand exponent of number to powers of two, then compute last d digits of this factors using repeated squaring last digits, for example: 24593590^16777216 = 24593590^(2^24), this means that need to square 24593590 24 times and take last digits, but answer will be very large, so need to take last d digits in intermediate results:

24593590^(2^1) = 24593590^2 = ...69088100


24593590^(2^2) = ...69088100^2 = ...61610000


24593590^(2^3) = ...61610000^2 = ...00000000


...


Repeat this until we get last digit of 24593590^(2^24). Perform this operation with each factor, then multiply it, take last digits and it is the new input. 24593590 was only example, It is possible to apply to Mega and compute myriads or even millions of last digits. Ikosarakt1 (talk) 09:51, November 27, 2012 (UTC)

Challenge: What about computing the first digit? FB100Ztalkcontribs 23:51, November 27, 2012 (UTC)

The problem reduces to the calculation of the fractional part of the common logarithm and raising 10 to this power.

Then consider the some possible results:

10^0.1 = 1.258...

10^0.2 = 1.584...

10^0.3 = 1.995...

10^0.4 = 2.511...

10^0.5 = 3.162...

10^0.6 = 3.981

10^0.7 = 5.011

10^0.8 = 6.309

10^0.9 = 7.943

And so Mega probably starts at 1... but so far it is unprovable.

We can not calculate it, raising the first digits in the power of itself, since the last digits push other digits and accumulate error. To know for sure what first digit is, we need to know the full decimal expansions of all triangles of 256 up to 256[3]255. However, I can now compute the first digits of 256[3]2. It starts at 39844342006... and has about 20 quadrillion ducentillion (2*10^619) digits. To obtain first digits of 256[3]3 I need to know the full decimal expansion of this number, and decimal expansion of common logarithm of 2 up to 2*10^619 digits. Ikosarakt1 (talk) 09:53, November 28, 2012 (UTC)

Now I computed, using my method, last 255 digits. Mega = ...0149295996978794394300467772313313256427303946108540066329239113 1838502897561606601450696228009791206968151401164151569201969226596 5864251890278286738700271908166330741936373885240123541091811174680 59671715057145877044749894910112922449731993539660742656 Ikosarakt1 (talk) 14:12, February 13, 2013 (UTC)

Down arrows[]

Exercise: Prove that Mega = 2↓↓↓259. -- I want more clouds! 05:40, March 23, 2013 (UTC)

Lemma 1: \(a \uparrow\uparrow 2 = a \downarrow\downarrow 2\)

Proof:

\(a \uparrow\uparrow 2 = a^a\)

\(a \downarrow\downarrow 2 = a^a\)

Therefore, \(a \uparrow\uparrow 2 = a \downarrow\downarrow 2\). There is no place for associativity.

Lemma 2: \(a[3] = a \downarrow\downarrow 2\)

Proof:

\(a[3] = a^a = a \downarrow\downarrow 2\)

Lemma 3: \(\text{Mega} = 2[3]258\)

Proof:

\(\text{Mega} = 2[5] = 2[4]_2 = (2[4])[4] = 256[4] = 256[3]256 = 2[3]2[3]256 = 2[3]258\)

Now consider:

\(2[3] = 2 \downarrow\downarrow 2 = 2 \downarrow\downarrow\downarrow 2\)

\(2[3]_2 = (2[3])[3] = (2 \downarrow\downarrow 2) \downarrow\downarrow 2 = 2 \downarrow\downarrow\downarrow 3\) (by definition of down-arrows)

By induction:

\(2[3]_n = 2 \downarrow\downarrow\downarrow (n+1)\)

Therefore, Mega = \(2 \downarrow\downarrow\downarrow 259\).


 Ikosarakt1 (talk ^ contribs) 09:04, March 23, 2013 (UTC)

Fast-growing hierarchy[]

The mega is very, very closely upper bounded by \(f_2^{258}(2)\) in the fast-growing hierarchy, and in fact the Mega is exactly equal to \(2^{f_2^{257}(2)}\). This is due to the laws of exponents: \({(2^n)}^{(2^n)} = 2^{n \times 2^n} = 2^{f_2(n)} \). Simply observe:

256 = \(2^8\)

\(256^{256}\) = \({(2^8)}^{(2^8)}\) = \(2^{8\times{2^8}}\) = \(2^{2^{11}}\) = \(2^{2048}\) = \(2^{f_2^2(2)}\) 

256[3][3] = \(2^{2048}[3]\) = \({(2^{2048})}^{(2^{2048})}\) = \(2^{2048\times(2^{2048})}\) = \(2^{2^{2059}}\) = \(2^{f_2^3(2)}\) 

Allam948736 (talk) 01:57, January 11, 2020 (UTC)

Cool! Could you add the equality to 2^{f_2^{257}(2)} (with your explanation above) to the article?
p-adic 02:33, January 11, 2020 (UTC)

Apocalyptic number question[]

Well, is this number an "apocalyptic number"? (sorry for the short question) ARsygo (talk) 02:10, 20 February 2022 (UTC)

Considering the amount of digits this number has, I am almost certain that it is, but I do not know if anyone has actually proved it, and if there is no source or proof, it cannot be claimed that it is an apocalyptic number. 🐟 Fish fish fish ... 🐠 09:13, 20 February 2022 (UTC)
Based on the last 2048 digits of it from this page, I noticed that there is a string that contains "666" in it. The string is actually "
9866684
". Hence, it is an apocalyptic number. ARsygo (talk) 11:14, 20 February 2022 (UTC)
Yes, I found that digit. So we can describe it with a source of the site. It is better if we can identify the location of 666 precisely, which just requires counting the digits. 🐟 Fish fish fish ... 🐠 12:28, 20 February 2022 (UTC)
It seems that Wojowu also calculated. From this result, the last 666 is from 1079th to 1077th digit from last. 🐟 Fish fish fish ... 🐠 19:27, 20 February 2022 (UTC)

Precise calculation of mega[]

I found a way to calculate mega precisely via the following recursive algorithm:

\(t_0 = 0\)

\(t_{n+1} = 256^{t_n} + t_n\)

The mega is \(256^{256^{t_{256}}}\). It's precise and not difficult to prove:

\(256^{256^{t_0}} = 256^{256^0} = 256^1 = 256\)

\(256^{256^{t_{n+1}}} = 256^{256^{256^{t_n} + t_n}} = 256^{256^{256^{t_n}}*256^{t_n}} = {256^{256^{t_n}}}^{256^{256^{t_n}}}\), so by induction it's true.

Tetramur (talk) 15:58, 10 July 2022 (UTC)


On Saibian's computation[]

The article says "The last 14 digits computed by Sbiis Saibian are ...93,539,660,742,656", but the source does not seem to include this result. Moreover, the source says "Only the last 3 digits of k are needed for the calculation because 1000 mod 125 = 0", but the reasoning is wrong. (n^k mod 125 for natural numbers n and k are not necessarily the same as n^{k mod 125} mod 125, while it is the same as n^{k mod 100} mod 125 when n is coprime to 5.) It is based on a wrong computation essentially explained in Tetration#Moduli_of_power_towers.

So, I propose to replace the description by the fact that Saibian stated that the last 3 digits are 656 but Saibian's reasoning is wrong, although it might fortunately gives a correct answer. I emphasise that I am not claiming that the answer is incorrect.

p-adic 06:19, 11 July 2022 (UTC)

The source says

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

🐟 Fish fish fish ... 🐠 08:14, 11 July 2022 (UTC)
Should we rewrite the sentence to "The last 14 digits computed by the program of Sbiis Saibian are 93539660742656, but it is based on a wrong computation essentially explained in Tetration#Moduli_of_power_towers."? 🐟 Fish fish fish ... 🐠 08:34, 11 July 2022 (UTC)


Thank you. I somewhy assumed that the result is written in "The last 14 digits of the Mega" section, and did not notice the sentence which you quoted. Anyway, I agree with the rewriting. Maybe it is a little better to refer to "wrong reasoning" rather than "wrong computation", because the computation itself might fortunately be correct despite of the wrong reasoning. (I note that the digits can be computed by Chinese reminder theorem and modular exponential, as I wrote in the article of tetration. Unlike the table-based method by Saibian, it does not require so much time, I guess. Therefore we can check whether the result is correct or not, but I am too lazy to do so.)
p-adic 10:01, 11 July 2022 (UTC)
I also found this page where Saibians calculated last 2048 digits of mega. As it writes "(b^p)%m = ((b%m)^p)%m" as property 1, without the condition of b is coprime to m, the calculation may not be correct. I have not evaluated the page, and I am not sure Saibian is using this relationship where b is not a coprime to m. I will describe this point and leave verification to other users. 🐟 Fish fish fish ... 🐠 13:50, 11 July 2022 (UTC)
The property "(b^p)%m = ((b%m)^p)%m" holds even when b is not coprime to m (as long as % is defined as the usual non-negative remainder unlike operations in several programming languages). The error in the original source is "(n^k)%125 = (n^(k%125)%125", which does not necessarily hold. Say, (10^127)%125 = 0 while (10^(127%125))%125 = (10^2)%125 = 100.
p-adic 16:53, 11 July 2022 (UTC)
I see. So I modified the description. 🐟 Fish fish fish ... 🐠 18:35, 11 July 2022 (UTC)
Thank you.
p-adic 22:56, 11 July 2022 (UTC)

Verifying the last digits[]

It is easy to prove that the Mega ends in a 6. Any number ending in 6 is congruent to 1 mod 5 and 0 mod 2, and for a positive integer n, 1^n = 1 and 0^n = 0 regardless of n. It is also easy to prove that the last two digits are ...56. We find that 256^256, the first step, is a number ending in ...56 raised to a power that is congruent to 1 mod 5. The last two digits of the powers of 56 repeat every 5 powers: 56, 36, 16, 96, 76. ...56^n ends in ...56 if n is 1 mod 5, ...36 if n is 2 mod 5, ...16 if n is 3 mod 5, ...96 if n is 4 mod 5, and ...76 if n is divisible by 5. (Normally, the iterated modular exponential mod \(5^d\) does not work because \(\phi(5) = 4\) and 4 does not divide 5^d, but here the "base" of the exponentiation is congruent to 1 mod 5, leaving only one possibility for ...56^n mod 5). Thus, ...56^...56 = ...56^(1 mod 5) = ...56. (Of course, we can still calculate 256^256 and see that it ends in ...56 as well, but the next step after that is already too large for direct calculation). It is is slightly more difficult to prove that Mega ends in ...656. It can be proven that the last 3 decimal digits of powers always repeat after 100 powers, because \(lcm(\phi(2^3), \phi(5^3))\) = 100. When we raise a number ending in ...X56 to the power of itself, we are multiplying by ...X56^...55. Since the base of exponentiation is again 1 mod 5, the last 3 digits will actually repeat after only 25 powers, so it is equivalent to multiplying by ...X56^5. Now, we find that 56^5, 256^5, 456^5, 656^5, and 856^5 all end in ...776, which is 26 mod 125 and 0 mod 8. Thus, for any multiple of 8 ending in ...56 (i. e. ...X56 where X is an even digit), raising to its own power is equivalent to multiplying by ...776, or 26 mod 125. We see that 56, 256, 456, 656, and 856 are respectively congruent to 56, 6, 81, 31, and 106 mod 125. Multiplying by 26 mod 125 is equivalent to adding n*25 mod 125, and multiplying all of those by 25 gives 25 mod 125. Since we are working with multiples of 8, we can use the Chinese Remainder Theorem to find that the multiple of 8 congruent to 25 mod 125 is 400. Thus each additional triangle adds 400 to the last 3 digits, so Mega = 256 + 400*256 mod 1000 = ...656. This eventually becomes very difficult, so for more digits, it is easier to prove that the digits can be computed using the following method: \(N_0 = 256\), \(N_{m+1} = (N_m \mod 10^d)^{N_m \mod 10^d} \mod 10^d\), and continue until \(N_{256}\). This can be verified by simply proving that the iterated modular exponential mod 10^d works. Allam(2^^n mod 10^6 for n >= 8) (talk) 16:02, 27 December 2023 (UTC)

Actually the problem can be reduced to the recursive calculation of 2^n. See the last source in the "Last digits" section. 🐟 Fish fish fish ... 🐠 18:46, 27 December 2023 (UTC)
Advertisement