Project Euler 188: Find the last digits of a tetration calculation.

Problem Description

The hyperexponentiation or tetration of a number a by a positive integer b, denoted by a↑↑b or ^ba, is recursively defined by:

a↑↑1 = a,
a↑↑(k+1) = a^(a↑↑k).

Thus we have e.g. 3↑↑2 = 3³ = 27, hence 3↑↑3 = 3²⁷ = 7625597484987 and 3↑↑4 is roughly 10^{3.6383346400240996*10^12}.

Find the last 8 digits of 1777↑↑1855.

Analysis

Using the optional third parameter of Python’s pow(x, y [,z]) function which calculates the modulo z of x to the power y (computed more efficiently than pow(x, y) % z) we loop through the pow function b times to calculate the tetration of a↑↑b. Modding the result by some power of 10, 10⁸ in this case, we can reduce this unwieldy number to its last 8 digits.

We can exit the loop early, reducing the number of iterations, when the modded result begins to repeat.

Project Euler 188 Solution

Afterthoughts

• Note: The last eight digits remain constant by the eighth iteration regardless of the parameters of the tetration expression.
  
• See also, Project Euler 48 Solution:
  
• See also, Project Euler 97 Solution: