Project Euler 188: Find the last digits of a tetration calculation.
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 = 33 = 27, hence 3↑↑3 = 327 = 7625597484987 and 3↑↑4 is roughly 103.6383346400240996*10^12.
Find the last 8 digits of 1777↑↑1855.
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, 108 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 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 188 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- 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: Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.
- See also, Project Euler 97 Solution: Find the last ten digits of the non-Mersenne prime: 28433 × 27830457 + 1.