Problem 282: The Ackermann Function

Detailed mathematical approach

Problem Summary

For non-negative integers \(m\) and \(n\), the Ackermann function is defined by three rules, the second for \(m\gt0\) and the third for \(m\gt0\) and \(n\gt0\):

$$\begin{aligned}A(0,n)&=n+1,\\ A(m,0)&=A(m-1,1),\\ A(m,n)&=A(m-1,A(m,n-1)).\end{aligned}$$

The statement gives the examples \(A(1,0)=2\), \(A(2,2)=7\) and \(A(3,4)=125\). We must find the sum of the seven diagonal values \(A(0,0),A(1,1),\dots,A(6,6)\), given as its remainder after division by \(14^8=1475789056\). ^[1] This two-argument form, due to Rózsa Péter and Raphael Robinson, grows faster than every primitive recursive function. ^[2]

The whole solution in one sentence: the first four terms are small, the other three are towers of twos minus \(3\), and the remainder of a tower follows from the remainder of a shorter tower after division by a smaller number, so that all towers of height at least \(10\) leave the same remainder modulo \(14^8\).

Mathematical Approach

We evaluate small cases, find closed forms for the rows, write the seven terms with Knuth's arrows, and then learn to take remainders of numbers far too large to be written down.

1. Unfolding the rules

Every evaluation applies one of the three rules. For example,

$$\begin{aligned}A(1,1)&=A(0,A(1,0))\\ &=A(0,A(0,1))\\ &=A(0,2)=3.\end{aligned}$$

Continuing in the same way gives the first values, for \(n=0,1,2,3,4\) from left to right:

• row \(m=0\): \(1, 2, 3, 4, 5\);
• row \(m=1\): \(2, 3, 4, 5, 6\);
• row \(m=2\): \(3, 5, 7, 9, 11\);
• row \(m=3\): \(5, 13, 29, 61, 125\).

They contain the first four terms of our sum. Following the rules literally soon becomes hopeless: a recursive program that does so calls itself \(4\) times for \(A(1,1)\), counting the first call, \(27\) times for \(A(2,2)\), \(2432\) times for \(A(3,3)\) and \(2\,862\,984\,010\) times for \(A(4,1)=65533\). So we look for formulas.

2. The first rows in closed form

The third rule says that one step to the right in row \(m\) applies the function \(x\mapsto A(m-1,x)\) of the row above once, and the second rule gives the start \(A(m,0)=A(m-1,1)\). Hence:

• Row \(1\) starts at \(A(1,0)=A(0,1)=2\), and every step adds \(1\), so \(A(1,n)=n+2\).
• Row \(2\) starts at \(A(2,0)=A(1,1)=3\), and every step adds \(2\), so \(A(2,n)=2n+3\).
• Row \(3\) starts at \(A(3,0)=A(2,1)=5\), and every step maps \(x\) to \(2x+3\). Since \(2x+3+3=2(x+3)\), the number \(x+3\) doubles in every step, starting from \(8=2^3\), so \(A(3,n)=2^{n+3}-3\).

Each formula is a one-line induction on \(n\). For instance \(A(3,4)=2^7-3=125\), as in the statement, and \(A(3,3)=2^6-3=61\). ^[2]

3. Towers and Knuth's arrows

Row \(3\) is exponential, and the next rows repeat exponentiation. Knuth's up-arrow notation names these operations. ^[3] \(2\uparrow x=2^x\) is a power; \(2\uparrow\uparrow x\) is a tower of \(x\) twos, evaluated from the top down, with \(2\uparrow\uparrow0=1\) for the empty tower; \(2\uparrow\uparrow\uparrow x\) is a chain of \(x\) twos joined by \(\uparrow\uparrow\), evaluated from the right; and so on. In general, for \(k\ge1\) and \(x\ge2\),

$$\begin{aligned}2\uparrow^{k}x&=2\uparrow^{k-1}\bigl(2\uparrow^{k}(x-1)\bigr),\\ 2\uparrow^{k}1&=2,\end{aligned}$$

where \(\uparrow^{k}\) stands for \(k\) arrows and \(2\uparrow^{0}x=2x\) is plain multiplication. Small values: \(2\uparrow\uparrow2=4\), \(2\uparrow\uparrow3=2^4=16\), \(2\uparrow\uparrow4=2^{16}=65536\), and \(2\uparrow\uparrow5=2^{65536}\) is a number with \(19\,729\) digits. Two facts will be used below. First, \(2\uparrow^{k}2=4\) for every \(k\), because \(2\uparrow^{k}2=2\uparrow^{k-1}(2\uparrow^{k}1)=2\uparrow^{k-1}2\), and so on down to \(2\cdot2\). Second, therefore,

$$\begin{aligned}2\uparrow\uparrow\uparrow3&=2\uparrow\uparrow\bigl(2\uparrow\uparrow\uparrow2\bigr)\\ &=2\uparrow\uparrow4=65536.\end{aligned}$$

4. Every row is an arrow

Claim: for \(m\ge2\) and \(n\ge0\),

$$A(m,n)=2\uparrow^{m-2}(n+3)-3.$$

For \(m=2\) and \(m=3\) this is Section 2. To prove it in general, we shift the argument and the value by \(3\): put \(G_m(x)=A(m,x-3)+3\) for \(x\ge3\). For \(m\ge1\), the second rule and, for \(x\ge4\), the third rule become

$$\begin{aligned}G_m(3)&=G_{m-1}(4),\\ G_m(x)&=G_{m-1}\bigl(G_m(x-1)\bigr),\end{aligned}$$

because \(A(m,0)+3=A(m-1,1)+3\) and \(A(m,x-3)+3\)\({}=A(m-1,A(m,x-4))+3\). The arrows obey the same two rules: \(2\uparrow^{k}3=2\uparrow^{k-1}(2\uparrow^{k}2)=2\uparrow^{k-1}4\), and the step rule of Section 3. Section 2 gives \(G_2(x)=2x=2\uparrow^{0}x\). If \(G_{m-1}(x)=2\uparrow^{m-3}x\) for all \(x\ge3\), then \(G_m\) and \(2\uparrow^{m-2}\) agree at \(x=3\) and are built by the same step, so they agree for every \(x\ge3\) by induction on \(x\); the inner value \(G_m(x-1)\) is at least \(4\), so the assumption about \(G_{m-1}\) applies to it. Induction on \(m\) proves the claim. ^[2] For row \(4\) it gives \(A(4,0)=2\uparrow\uparrow3-3=13\), \(A(4,1)=65533\) and \(A(4,2)=2^{65536}-3\).

5. The seven terms

By Sections 1 and 4 the seven terms are \(1\), \(3\), \(7\), \(61\) and

$$\begin{aligned}A(4,4)&=2\uparrow\uparrow7-3,\\ A(5,5)&=2\uparrow\uparrow\uparrow8-3,\\ A(6,6)&=2\uparrow\uparrow\uparrow\uparrow9-3.\end{aligned}$$

None of the last three can be written down: already \(2\uparrow\uparrow6=2^{2^{65536}}\) has so many digits that the number of its digits has \(19\,728\) digits itself. The last two are towers of twos as well, only much taller. Indeed, every \(2\uparrow^{k}x\) with \(k\ge2\) is a tower: for \(k=2\) by definition, for \(x=1\) it is \(2=2\uparrow\uparrow1\), and for \(k\ge3\) and \(x\ge2\) the step rule writes it as \(2\uparrow^{k-1}y\) with \(y=2\uparrow^{k}(x-1)\), which is a tower by induction on \(k\). Explicitly,

$$A(5,5)+3=2\uparrow\uparrow\bigl(2\uparrow\uparrow\uparrow7\bigr),$$

and, with \(y=2\uparrow\uparrow\uparrow\uparrow8\ge4\),

$$\begin{aligned}A(6,6)+3&=2\uparrow\uparrow\uparrow y\\ &=2\uparrow\uparrow\bigl(2\uparrow\uparrow\uparrow(y-1)\bigr).\end{aligned}$$

Both heights are at least \(2\uparrow\uparrow\uparrow3=65536\). The task is therefore to find the remainders of \(2\uparrow\uparrow h\) modulo \(14^8\) for \(h=7\) and for two heights \(h\ge65536\).

6. Remainders and Euler's theorem

We write \(a\bmod m\) for the remainder of \(a\) after division by \(m\), and \(a\equiv b\pmod m\) when \(a\) and \(b\) leave the same remainder. Remainders may be taken after every addition and multiplication, which is how a computer finds \(2^{E}\bmod m\) for any exponent \(E\) it can store; but \(2\uparrow\uparrow6\) cannot even be stored. Euler's totient \(\varphi(m)\) counts the numbers from \(1\) to \(m\) that have no common factor with \(m\); it satisfies \(\varphi(p^k)=p^{k-1}(p-1)\) for a prime \(p\), and \(\varphi(ab)=\varphi(a)\varphi(b)\) when \(a\) and \(b\) have no common factor, so \(\varphi(100)=2\cdot20=40\). ^[4] Euler's theorem states that \(a^{\varphi(m)}\equiv1\pmod m\) whenever \(a\) and \(m\) have no common factor, so that exponents may then be reduced modulo \(\varphi(m)\). ^[5] For example, \(\varphi(25)=20\) and \(2^{20}=1048576\equiv1\pmod{25}\).

Our base \(2\) and our modulus \(14^8\) share the factor \(2\), and then the theorem fails: \(2^{40}\equiv76\pmod{100}\), not \(1\). Reducing the exponent \(40\) modulo \(\varphi(100)=40\) would wrongly turn \(2^{40}\) into \(2^0=1\).

7. The lifted exponent rule

The repair is to keep the exponent large. Let \(m\ge1\), let \(s\) be the number of factors \(2\) in \(m\), so that \(m=2^s t\) with \(t\) odd, and let \(E\ge s\). Then

$$2^{E}\equiv2^{(E\bmod\varphi(m))+\varphi(m)}\pmod m.$$

Proof. Call the new exponent \(E'\); it leaves the same remainder as \(E\) modulo \(\varphi(m)\). Modulo the odd part \(t\), Euler's theorem applies, and \(\varphi(t)\) divides \(\varphi(m)=\varphi(2^s)\varphi(t)\), so \(2^{E}\equiv2^{E'}\pmod t\). Modulo \(2^s\) both powers are \(0\): \(E\ge s\) by assumption, and \(E'\ge\varphi(m)\ge\varphi(2^s)=2^{s-1}\ge s\) when \(s\ge1\). By the Chinese remainder theorem a number is determined modulo \(m\) by its remainders modulo the coprime factors \(2^s\) and \(t\), ^[7] so the two powers agree modulo \(m\). The Carmichael function \(\lambda(m)\), the smallest positive \(L\) with \(a^L\equiv1\pmod m\) for all \(a\) coprime to \(m\), divides \(\varphi(m)\) and obeys a related rule for every base: \(a^{r}\equiv a^{r+\lambda(m)}\pmod m\) for every \(r\) at least the largest exponent in the prime factorisation of \(m\). ^[6]

With \(m=100\), so that \(s=2\) and \(\varphi(m)=40\), the rule gives \(2^{0+40}\equiv76\) for \(E=40\), which is correct; and for \(E=65536\), which leaves the remainder \(16\) modulo \(40\), it gives \(2^{56}\equiv36\equiv2^{65536}\pmod{100}\). The condition \(E\ge s\) cannot be dropped: for \(E=1\) the rule would give \(2^{41}\equiv52\), but \(2^1=2\).

8. Towers modulo \(m\) and the last two digits

Write \(r_h(m)=(2\uparrow\uparrow h)\bmod m\). We have \(2\uparrow\uparrow h=2^{2\uparrow\uparrow(h-1)}\), and for \(h\ge5\) the exponent is at least \(2\uparrow\uparrow4=65536\), more than the number of factors \(2\) of any modulus below \(2^{65536}\). So, for these \(h\), Section 7 gives

$$r_h(m)=2^{\,r_{h-1}(\varphi(m))+\varphi(m)}\bmod m.$$

The remainder of a tower modulo \(m\) needs only the remainder of the tower one level lower modulo \(\varphi(m)\). Repeating this walks down the chain \(m\), \(\varphi(m)\), \(\varphi(\varphi(m))\), …, and the walk ends either at a height of at most \(4\), where the tower is a known number, or at the modulus \(1\), where every remainder is \(0\).

Worked example: the last two digits of \(2\uparrow\uparrow h\), that is \(m=100\), with the chain \(100\to40\to16\to8\to4\to2\to1\). The towers of height at most \(4\) are \(1\), \(2\), \(4\), \(16\) and \(65536\), ending in \(01\), \(02\), \(04\), \(16\) and \(36\). For \(h=5\): \(65536\bmod40=16\), so \(r_5(100)=2^{16+40}\bmod100=36\). This can be checked by hand: \(2^{56}\) is divisible by \(4\), and \(2^{56}\equiv2^{16}\equiv11\pmod{25}\) because \(2^{20}\equiv1\pmod{25}\), and \(36\) is the only number below \(100\) with these two remainders. For \(h=6\): first \(65536\bmod16=0\), so \(r_5(40)=2^{0+16}\bmod40=16\), and then \(r_6(100)=2^{16+40}\bmod100=36\) again. For every \(h\ge5\) we have \(r_{h-2}(16)=0\), because \(2\uparrow\uparrow(h-2)\) is a power of \(2\) with exponent at least \(4\); so the same two steps repeat, and every tower of height at least \(4\) ends in \(36\). In the toy version of our problem with the modulus \(100\), the three large terms all end in \(33\), and the sum \(1+3+7+61+3\cdot33=171\) leaves the remainder \(71\).

9. The totient chain of \(14^8\)

Our modulus is \(M=14^8=2^8\cdot7^8\), so \(\varphi(M)=2^7\cdot6\cdot7^7=2^8\cdot3\cdot7^7\), and for \(a,c\ge1\)

$$\begin{aligned}\varphi\bigl(2^a\cdot3\cdot7^c\bigr)&=2^{a-1}\cdot2\cdot6\cdot7^{c-1}\\ &=2^{a+1}\cdot3\cdot7^{c-1}.\end{aligned}$$

From \(\varphi(M)\) on, each step removes one factor \(7\) and adds one factor \(2\), so the modulus after \(8\) steps is \(2^{15}\cdot3\). Then \(\varphi(2^{15}\cdot3)=2^{15}\), and every further step halves: \(2^{14},2^{13},\dots,2,1\). The chain reaches \(1\) after \(24\) steps, within the general bound of \(\log_2M+1\approx31.5\) steps, ^[8] and none of its \(25\) moduli has more than \(15\) factors \(2\).

This already shows that all towers of height at least \(28\) share their remainder modulo \(M\): for such \(h\) the rule of Section 8 applies at the \(24\) heights \(h,h-1,\dots,h-23\), all at least \(5\), and the walk always ends at the modulus \(1\) with the remainder \(0\), by the same steps.

10. From height 10 on, all towers agree

A sharper look splits \(M\) into \(2^8\) and \(7^8\). Modulo \(2^8\), the tower \(2\uparrow\uparrow h\) is \(0\) as soon as its exponent reaches \(8\), that is, for \(h\ge4\). Modulo powers of \(7\), the key is \(2^3=8=1+7\). If \(x=1+7^j y\) with \(j\ge1\), the binomial theorem gives \(x^7=1+7^{j+1}y+\dots\), where every omitted term contains \(7^{j+2}\) or a higher power, so \(x^7\equiv1\pmod{7^{j+1}}\). Starting from \(2^3\equiv1\pmod7\), this gives \(2^{3\cdot7^{k-1}}\equiv1\pmod{7^k}\): modulo \(7^k\), the power \(2^E\) depends only on \(E\) modulo \(3\cdot7^{k-1}\).

Claim: the remainder of \(2\uparrow\uparrow h\) modulo \(7^k\) is the same for all \(h\ge k+2\). Write \(E=2\uparrow\uparrow(h-1)\). For \(h\ge3\), \(E\) is \(2\) raised to an even power, that is, a power of \(4\), so \(E\equiv1\pmod3\). For \(k=1\) this fixes \(2^E\bmod7\) for all \(h\ge3\). For \(k\ge2\), assume the claim for \(k-1\); then \(E\bmod7^{k-1}\) is fixed for \(h-1\ge k+1\). Together with \(E\bmod3\), the Chinese remainder theorem fixes \(E\bmod3\cdot7^{k-1}\) for all \(h\ge k+2\), and with it \(2^E\bmod7^k\). For \(k=8\), together with the factor \(2^8\), all towers of height at least \(10\) have the same remainder modulo \(M\).

The bound \(10\) is sharp: the remainders of \(2\uparrow\uparrow h\) modulo \(M\) for \(h=0,1,\dots,9\) are ten different numbers, all different from the common remainder of the taller towers. In particular \(A(4,4)\), whose tower has height \(7\), must be computed on its own, while \(A(5,5)\) and \(A(6,6)\) share the stable remainder. Decimal digits show the same effect: for every \(k\le12\), a computation carried past the height from which the argument of Section 9 rules out any change shows that the towers agree modulo \(10^k\) exactly from height \(k+2\) on. The last six digits of \(2\uparrow\uparrow h\) for \(h=4,\dots,9\) are \(065536\), \(156736\), \(428736\), \(748736\), \(948736\) and \(948736\), each level from \(h=5\) on freezing one more digit. So \(A(4,4)\) ends in \(748733\), while \(A(5,5)\) and \(A(6,6)\) end in \(948733\), and the toy sum modulo \(10^6\) is \(646271\).

11. Assembling the sum

With \(r_h=r_h(M)\) and \(72=1+3+7+61\), the requested remainder is the remainder of

$$72+(r_7-3)+2(r_{10}-3)$$

after division by \(M\), where \(r_{10}\) may be replaced by \(r_h\) for any \(h\ge10\), for example \(h=200\). Only two tower remainders are needed, and each costs a short walk down the chain of Section 9.

How the Code Works

The C++ program ^[10] implements Section 11 in main; in Python and Java the entry point calls solve, which does the same. The helpers carry the C++ names, except that Java writes getPhi, hyperTower2, solveN0 to solveN4 and solveLargeN, and that Python has no power function. The constant MOD_MAIN is \(M=14^8=1475789056\). power(base, exp, mod) is binary exponentiation: it reads the exponent bit by bit from the lowest bit, squares the base in every round and multiplies it into the result where the bit is \(1\). ^[9] get_phi(n) computes \(\varphi(n)\) by trial division: whenever \(i\) divides what is left of \(n\), it removes all factors \(i\) and replaces result by result - result / i, which applies the product formula \(\varphi(n)=n\prod(1-1/p)\) one prime at a time; ^[4] the loop stops when \(i^2\) exceeds what is left, and a remaining factor above \(1\) is the last prime.

hyper_tower_2(height, m) returns \(r_h(m)\) for \(h=\)height and checks three cases in this order. For \(m=1\) it returns \(0\). For heights \(0\) to \(4\) it returns the exact towers \(1\), \(2\), \(4\), \(16\) and \(65536\), reduced modulo \(m\). Otherwise it computes \(\varphi(m)\), calls itself with height - 1 and \(\varphi(m)\), adds \(\varphi(m)\) to the result and returns \(2\) to this power modulo \(m\): the rule of Section 8. The exact cases up to height \(4\) make the lift of Section 7 legitimate in every recursive step, since the true exponent there is at least \(2\uparrow\uparrow4=65536\), while the moduli of Section 9 have at most \(15\) factors \(2\); the example \(E=1\) of Section 7 shows that the lift may fail for small exponents. A call with height \(7\) ends three levels down with the exact value \(65536\) modulo \(\varphi(\varphi(\varphi(M)))\); a call with height \(200\) reaches the modulus \(1\) at height \(176\).

solve_n0 to solve_n3 return the constants \(1\), \(3\), \(7\) and \(61\) of Section 1. solve_n4 returns the remainder of \(A(4,4)=2\uparrow\uparrow7-3\), computed as hyper_tower_2(7, MOD_MAIN) minus \(3\) plus \(M\), reduced modulo \(M\). Adding \(M\) keeps the value non-negative even when the tower leaves a remainder below \(3\), because in C++ and Java the result of % takes the sign of the dividend. solve_large_n does the same with height \(200\) and serves both \(A(5,5)\) and \(A(6,6)\): by Section 10 every height from \(10\) on gives the remainder of the real towers, whose heights exceed \(65536\). The height \(200\) is a generous margin: it takes \(25\) calls instead of the \(7\) of height \(10\), and no height takes more, because the walk stops at the modulus \(1\) after \(24\) steps. main in C++ and solve in Python and Java collect the seven values, add them and reduce the sum modulo \(M\). The unreduced sum is below \(7M\lt2^{34}\) and fits into a 64-bit integer.

The languages differ only in arithmetic details. C++ uses long long and Java long for heights, moduli and remainders. The C++ power casts each product to __int128 before reducing it, Java computes each product with BigInteger, and Python uses its built-in three-argument pow and unbounded integers. All three are more careful than necessary: every modulus is at most \(M\lt2^{31}\), so a product of two remainders is below \(2^{62}\) and fits into a signed 64-bit integer. Python raises its recursion limit to \(2000\) with sys.setrecursionlimit, while the deepest recursion has only \(25\) nested calls.

Complexity and Verification

A call with \(m=1\) or with a height of at most \(4\) returns at once; every other call computes one totient and one power. Modulo \(M\), the heights \(7\), \(10\) and \(200\) take \(4\), \(7\) and \(25\) calls, and every height from \(28\) on follows all \(24\) links of the chain, so taller towers cost no more. All moduli of the chain have the form \(2^a3^b7^c\), so the outer loop of the trial division tests at most the six divisors \(2,3,\dots,7\), and its inner loop runs once for every prime factor it removes; the exponent passed to power is below \(2\varphi(m)\le2\varphi(M)\lt2^{31}\), so power needs at most \(31\) rounds. For the program's three tower evaluations, one of height \(7\) and two of height \(200\), the C++ and Java versions run \(136\) rounds of the outer and \(570\) rounds of the inner trial-division loop and \(739\) rounds of binary exponentiation, \(1445\) in all; Python runs the same trial divisions and leaves the powers to its built-in pow. Memory is needed for at most \(25\) nested calls. For a general modulus \(m\) there are at most \(\log_2m+1\) levels, ^[8] each with at most about \(\sqrt m\) trial divisions and \(O(\log m)\) further operations, so the cost is \(O(\sqrt m\,\log m)\) arithmetic operations.

The published programs contain no tests of their own; they print the result. For this article the following checks were run separately:

• A direct evaluation of the three rules with an explicit stack reproduces \(A(1,0)=2\), \(A(2,2)=7\) and \(A(3,4)=125\), the values and call counts of Section 1, the closed forms of Section 2 for every \(n\le12\), and \(A(4,0)=13\).
• The lifted rule of Section 7 holds for every \(m\le3000\) and every exponent \(E\lt400\) with \(E\ge s\), and fails in every one of the \(2993\) cases with \(E\lt s\).
• For every \(m\le2000\) and for \(M\), \(\varphi(M)\), \(10^6\) and \(10^9\), hyper_tower_2 returns the exact remainder of \(2\uparrow\uparrow h\) for every \(h\le6\); for \(h=6\) the comparison uses the exact exponent \(2\uparrow\uparrow5=2^{65536}\).
• The C++ and Python versions of hyper_tower_2 agree modulo \(M\) for every \(h\le60\), and so do two methods without the totient chain: one uses only the period \(3\cdot7^{k-1}\) of Section 10, the remainders modulo \(3\) and \(2^8\) and the Chinese remainder theorem; the other reduces exponents modulo the Carmichael function \(\lambda(m)\) instead of \(\varphi(m)\), lifted by a multiple of \(\lambda(m)\) above \(s\); its chain from \(M\) has only \(10\) steps. ^[6]
• Modulo \(M\), the remainders for \(h=0,\dots,9\) are pairwise different, and all heights from \(10\) to \(400\) give the same remainder; the same check gives the stabilisation heights \(k+2\) modulo \(7^k\) for \(k\le8\).
• The C++, Python and Java programs print the same number, and the sum assembled with the period method of the fourth item gives it too.

Footnotes and References

The references below supply the background facts used above. The closed forms of the rows, the lifted exponent rule, the totient chain of \(14^8\) and the stabilisation from height \(10\) on are derived explicitly in this article.

1. Project Euler 282 — The Ackermann Function. The official statement defines A(m, n) by the rules A(0, n) = n + 1, A(m, 0) = A(m − 1, 1) and A(m, n) = A(m − 1, A(m, n − 1)), gives A(1, 0) = 2, A(2, 2) = 7 and A(3, 4) = 125, and asks for the sum of A(n, n) for n = 0, 1, …, 6, modulo 14⁸.
2. Wikipedia — Ackermann function. The article defines the two-argument Ackermann–Péter function, developed by Rózsa Péter and Raphael Robinson, by the same three rules, and shows that it grows faster than any primitive recursive function. It lists A(1, n) = n + 2, A(2, n) = 2n + 3 and A(3, n) = 2ⁿ⁺³ − 3, writes A(m, n) = 2↑ᵐ⁻²(n + 3) − 3 in Knuth's notation, and notes that A(4, 2) = 2⁶⁵⁵³⁶ − 3 has 19,729 decimal digits.
3. Wikipedia — Knuth's up-arrow notation. The notation, introduced by Donald Knuth in 1976, writes a↑b for exponentiation, a↑↑b for a tower of b copies of a and a↑↑↑b for iterated towers; the operators are evaluated from right to left, the general rule is a↑ⁿb = a↑ⁿ⁻¹(a↑ⁿ(b − 1)), and 2↑↑4 = 65,536.
4. Wikipedia — Euler's totient function. φ(n) counts the integers from 1 to n that are coprime to n; φ(pᵏ) = pᵏ⁻¹(p − 1) for a prime p, φ(mn) = φ(m)φ(n) for coprime m and n, and φ(n) = n ∏(1 − 1/p) over the distinct primes p dividing n, the formula that get_phi applies.
5. Wikipedia — Euler's theorem. If a and n are coprime, then a^φ(n) ≡ 1 (mod n), so exponents can be reduced modulo φ(n); the article finds the last digit of 7²²² in this way.
6. Wikipedia — Carmichael function. λ(n) is the smallest positive integer m with aᵐ ≡ 1 (mod n) for every a coprime to n, and it divides φ(n); the section on the exponential cycle length states that for every a, including a not coprime to n, and every r at least the largest exponent in the prime factorisation of n, a^r ≡ a^(λ(n) + r) (mod n).
7. Wikipedia — Chinese remainder theorem. If the moduli are pairwise coprime, the remainders of an integer modulo each of them determine its remainder modulo their product uniquely.
8. OEIS A003434 — Number of iterations of phi(x) at n needed to reach 1. The entry gives Pillai's bounds log(n/2)/log 3 + 1 ≤ a(n) ≤ log n/log 2 + 1 for this number of steps; for n = 14⁸ the chain of Section 9 has 24 steps.
9. Wikipedia — Modular exponentiation. The right-to-left binary method processes the bits of the exponent from the least significant one and squares the base in every step; its running time is O(log exponent).
10. C++ — Euler282.cpp. The linked immutable C++ revision contains power, get_phi, hyper_tower_2, solve_n4 and solve_large_n. It is the implementation record for this article.