9
$\begingroup$

Is there some general technique to compute tetration and pentation mod some number?

$m \uparrow^2 n \pmod a$ and $m \uparrow^3 n \pmod a$

I know about Euler's theorem to compute $m \uparrow n \pmod a$, but expanding pentation would result in huge tower.

Specifically, I want to compute in reasonable time Ackermann mod-a function "$ 2 \uparrow^{m-2} n \pmod a$".

$\endgroup$
12
  • 1
    $\begingroup$ $m\uparrow^2 n\bmod p=(m\uparrow((m\uparrow^2(n-1))\bmod p))\bmod p$ if $p$ is prime. $\endgroup$
    – Turbo
    Apr 6, 2015 at 8:13
  • 1
    $\begingroup$ See mathoverflow.net/a/165938 . $\endgroup$ Apr 6, 2015 at 10:36
  • 3
    $\begingroup$ Since the linked post appears to be lost on the audience, here’s an explicit algorithm for the special case $2\uparrow^mn\bmod a$. (1) Using factorization, determine the least multiple $a'$ of $a$ such that $\phi(a')\mid a'$. (2) Compute the sequence $x_n=2\uparrow^2n\bmod a'$ by the recurrence $x_0=1$, $x_{n+1}=2^{x_n}\bmod a'$ (using repeated squaring). The sequence will become constant after a handful of iterations, say $x_k=x_{k+1}$. (3) Then $2\uparrow^2n\bmod a$ is $x_{\min(n,k)}\bmod a$, and for $m\ge3$, $2\uparrow^mn\bmod a$ is $1,2,4$ for $n=0,1,2$, and $x_k\bmod a$ for $n\ge3$. ... $\endgroup$ Apr 6, 2015 at 16:29
  • 1
    $\begingroup$ ... This holds for $a$ less than $2^{65536}$ or so. For larger $a$, but still representable with less bits than the size of the observable universe, there may be an exception for $2\uparrow^33$. $\endgroup$ Apr 6, 2015 at 16:32
  • 2
    $\begingroup$ David Moulton asked these questions at the Western Number Theory meeting in December 2011: Is there an algorithm for computing $2^{2^d}\bmod m$ in time polynomial in $\log d$ and $\log m$? Is there an algorithm to compute $2^{2^{2^d}}\bmod p$ for $p$ prime in polynomial time? $\endgroup$ Apr 7, 2015 at 1:17

1 Answer 1

2
$\begingroup$

Assume that we are interested in knowing the last $n$ digits of $a \uparrow^2 b \mod m^k$ ($m$ is not necessarily prime). A paper of mine has just been approved for publication: it gives you a formula to calculate the exact number of stable/frozen digits at height $k$ of any tetration $\mod m^k$, where $m=10$, but the same result can be generalized to any squarefree $m$ (it would be available online in a few weeks/months). Knowing this, you can use the Carmichael lambda function in order to further reduce the calculations to find the congruence class modulo $m^k$ of $a \uparrow^2 b$. Moreover, the following reference could be helpful in order to improve the chosen approach: Hittmeir, M. (2020). A Reduction of Integer Factorization to Modular Tetration, Int. J. Fund. Comp. Sc., 31(4), 461–481.

$\endgroup$
1
  • $\begingroup$ Since the online version of the above mentioned paper has just been released, I share the link here in order to let you know the rules which tell you how many stable/frozen digits there are for any natural tetration base $a \not\equiv 0 \pmod{10}$ at given height $b$. "Number of stable digits of any integer tetration" $\rightarrow$ nntdm.net/volume-28-2022/number-3/441-457 $\endgroup$ Aug 1, 2022 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.