Mega is a large number defined as ② in the circle notation. Mega can be calculated recursively as \(m_{256}\) in the sequence defined by \(m_0 = 256\) and \(m_{n + 1} = m_n^{m_n}\).
Tetramur showed that mega can also be calcluated by \(256^{256^{m_{256}}}\) where \(m_0 = 0\) and \(m_{n+1} = 256^{m_n} + m_n\). I made a Python program to calculate the last digits of mega using this calculation method.
From the above recursive formula, the last d digits of mega can be obtained with a function to obtain the last d digits of \(256^n\) recursively. As \(256^n = 2^{8n}\), we need a function to obtain last d digits of \(2^n\) recursively. The algorithm for this calculation is as follows. \(2^{\varphi{(5^d)}} = 1\) (mod \(5^d\)) by Euler's theorem, where \(\varphi(5^d) = 5^d(1-1/5) = 4\cdot 5^{d-1}\). Therefore \(2^{\varphi{(5^d)} + d} = 2^d\) (mod \(10^d\)) and the last d digits of \(2^n\) can be recursively calculated as \(2^n = 2^{(n-d) \% \varphi(5^d) + d}\) (mod \(10^d\)) for \(n>d\). Note that in the recursion process \(n\%(10^d)\) is the input variable instead of n. As \(10^d\) is divisible by \(\varphi(5^d)\) for d>1, \(n\%\varphi(5^d) = (n\%(10^d))\%\varphi(5^d)\) and the recursion works. There is no problem for d=1 because \(256^n\%10\) = 6 for n>0.
\(a^b \% r \) for \(r=10^d\) is also calculated recursively by dividing b with a parameter c so that b=qc+m. Then we have \(a^b \% r= (a^c \% r)^q \% r \cdot a^m \% r\). Although c=2 has the maximum efficiency, to avoid having too much recursion depth for saving memory, the program changes the value of c with the size of b.
Here is the calculation result.
Fish published this page on 14 July, 2022.