Detailed mathematical approach

Problem Summary

Project Euler 282 asks for the modular sum

$\sum_{n=0}^{6} A(n,n)\pmod{14^8},$

where \(A(m,n)\) is the standard Ackermann function

$A(0,n)=n+1,$

$A(m,0)=A(m-1,1)\quad (m\ge1),$

$A(m,n)=A(m-1,A(m,n-1))\quad (m,n\ge1).$

The modulus is

$M=14^8=1475789056.$

The final residue is intentionally omitted; this page explains why the C++ solution can compute it without ever building the astronomically large raw Ackermann values.

Mathematical Approach

1) The first few Ackermann layers have closed forms

Starting from the definition, one gets the standard low-level identities:

$A(0,n)=n+1,$

$A(1,n)=n+2,$

$A(2,n)=2n+3,$

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

Therefore the diagonal values needed in the sum begin as

$A(0,0)=1,\qquad A(1,1)=3,\qquad A(2,2)=7,\qquad A(3,3)=61.$

These are exactly the constants returned by solve_n0(), solve_n1(), solve_n2(), and solve_n3().

2) From exponentials to tetration

Because

$A(3,n)=2^{n+3}-3,$

the next level satisfies

$A(4,n+1)=A(3,A(4,n))=2^{A(4,n)+3}-3.$

This is exactly the recursion of a power tower. Using Knuth's notation,

$A(4,n)=2\uparrow\uparrow(n+3)-3,$

where

$2\uparrow\uparrow1=2,\qquad 2\uparrow\uparrow(h+1)=2^{\,2\uparrow\uparrow h}.$

In particular, the \(n=4\) diagonal term is

$A(4,4)=2\uparrow\uparrow7-3.$

This is why the code computes

$\texttt{hyper\_tower\_2(7,M)}-3 \pmod M$

inside solve_n4().

3) The next Ackermann levels are even higher hyper-operators

The same pattern continues:

$A(5,n)=2\uparrow\uparrow\uparrow(n+3)-3,$

$A(6,n)=2\uparrow\uparrow\uparrow\uparrow(n+3)-3,$

and so on.

So the last two needed diagonal terms, \(A(5,5)\) and \(A(6,6)\), are not merely “very large”; they are far beyond any direct representation. The only sensible target is their residue modulo \(M\).

4) What the helper hyper_tower_2(h,m) computes

The recursive helper does not compute the actual tower \(2\uparrow\uparrow h\). It computes only its residue modulo \(m\):

$T_h(m):=2\uparrow\uparrow h \pmod m.$

For small heights the values are explicit:

$T_0(m)=1,\qquad T_1(m)=2,\qquad T_2(m)=4,\qquad T_3(m)=16,\qquad T_4(m)=65536,$

all taken modulo \(m\). These base cases are hard-coded in the function.

5) Why Euler-\(\varphi\) recursion is the right reduction

For large heights, we want

$2^{E}\pmod m,$

where \(E=2\uparrow\uparrow(h-1)\) is itself enormous. The classical coprime reduction says that modulo an odd modulus one may reduce exponents modulo \(\varphi(m)\). Here the base is \(2\), and our moduli along the recursion are not always coprime to \(2\), so one has to be careful.

The code uses the standard “lifted exponent” strategy:

1. compute the upper exponent modulo \(\varphi(m)\);

2. add one full totient period;

3. exponentiate modulo \(m\).

Formally, for the huge towers occurring in this problem, it evaluates

$2^{\,e+\varphi(m)}\pmod m,$

where

$e=T_{h-1}(\varphi(m)).$

This is exactly what the code does through

$\texttt{eff\_exponent = exponent\_val + phi}.$

6) Why the \(+\varphi(m)\) lift is safe here

This lift is not being used as a blind universal theorem for tiny exponents. It is safe here because all tower heights entering the recursive branch are already huge.

The modulus is

$M=14^8=2^8\cdot 7^8.$

For the \(2^8\) part, once the exponent is at least \(8\), we already have

$2^E\equiv 0\pmod{2^8}.$

For the odd part \(7^8\), the base \(2\) is coprime, so Euler reduction modulo

$\varphi(7^8)=6\cdot 7^7$

is valid.

Adding \(\varphi(m)\) guarantees that the reconstructed exponent is safely “large enough” for the \(2\)-power part while keeping the correct residue information for the odd part. Since the actual exponents in the problem are vastly larger than \(8\), this lifted reduction matches the true tower residue.

7) Stabilization of very tall towers modulo \(M\)

An important phenomenon is that the residues

$2\uparrow\uparrow h \pmod M$

eventually stabilize. In fact, with the recursion used by the code, the residue stops changing once the tower height is large enough. A direct check shows that the values are already constant from height \(11\) onward.

That means:

every sufficiently tall power tower of 2 has the same residue modulo \(M\).

This is the key reason the gigantic terms \(A(5,5)\) and \(A(6,6)\) become tractable.

8) Why \(A(5,5)\) and \(A(6,6)\) use the same surrogate height

We have

$A(5,5)+3=2\uparrow\uparrow\uparrow 8,$

which means “a tetration whose height is itself already enormous.” Likewise \(A(6,6)+3\) is vastly larger still.

Since tower residues modulo \(M\) have already stabilized by modest height, both of these Ackermann values land in the same stabilized residue class. Therefore the code is allowed to replace each of them by

$2\uparrow\uparrow 200 \pmod M$

as a safe surrogate. The particular choice \(200\) is not mathematically special; it is simply far beyond the stabilization threshold.

That is why solve_large_n() is called twice, once for the \(n=5\) term and once for the \(n=6\) term.

9) Final decomposition of the required sum

The problem asks for

$S=\sum_{n=0}^{6}A(n,n)\pmod M.$

The implementation splits this into:

four exact small constants for \(n=0,1,2,3\);

one genuine tetration term for \(n=4\), namely \(2\uparrow\uparrow7-3\);

two identical stabilized huge-level residues for \(n=5\) and \(n=6\).

So the entire problem is reduced to a few modular tower evaluations, not to raw Ackermann growth.

Code Logic

1) Fast modular power. power() uses binary exponentiation with 128-bit intermediate multiplication.

2) Totient computation. get_phi() factors the current modulus on the fly and returns \(\varphi(m)\).

3) Tower recursion. hyper_tower_2(height,m) evaluates \(2\uparrow\uparrow\text{height}\pmod m\) by recurring into modulus \(\varphi(m)\) and then lifting the exponent by one totient.

4) Ackermann layers. solve_n0() through solve_n3() return exact constants; solve_n4() returns the \(A(4,4)\) residue; solve_large_n() returns the stabilized residue used for both \(A(5,5)\) and \(A(6,6)\).

5) Final sum. The main function launches the seven pieces independently, collects them, and sums modulo \(M\).

Complexity Analysis

Each modular exponentiation costs \(O(\log e)\). The recursion depth is controlled by the totient chain of the modulus, and the tower height is replaced by small explicit heights or by a safe stabilized surrogate. So the runtime is tiny compared with the impossible cost of direct Ackermann evaluation, and memory usage is essentially constant.

Further Reading

1. Problem page: https://projecteuler.net/problem=282
2. Ackermann function: https://en.wikipedia.org/wiki/Ackermann_function
3. Tetration and power towers: https://en.wikipedia.org/wiki/Tetration