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$".

Improve this question
$\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
    Commented Apr 6, 2015 at 8:13
  • 1
    $\begingroup$ See mathoverflow.net/a/165938 . $\endgroup$
    – Emil Jeřábek
    Commented 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$
    – Emil Jeřábek
    Commented 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$
    – Emil Jeřábek
    Commented 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$
    – Gerry Myerson
    Commented Apr 7, 2015 at 1:17

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Marco Ripà
    Commented Aug 1, 2022 at 16:10

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