// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (30 votes, average: 4.60 out of 5)
Loading...

Project Euler Solutions

Project Euler 188 Solution

Project Euler 188 Solution

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 = 33 = 27, hence 3↑↑3 = 327 = 7625597484987 and 3↑↑4 is roughly 103.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, 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 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 188 Solution Python 2.7 source.

Afterthoughts

Project Euler 188 Solution last updated

Discussion

No comments yet.

Post a comment