(20 votes, average: 4.25 out of 5)

## Project Euler Problem 188 Solution

#### 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 little known optional third parameter of Python’s pow(x, y [,z]) function that provides x to the power y, modulo z (computed more efficiently than pow(x, y) % z) we were able to simply loop through the hyperexponentiation of a↑↑b.

This is similar to problem 97.

#### Solution

Runs < 1 second in Python.

```def hyper_exp(a, b, m): temp = 1 while b: temp = pow(a, temp, 10**m) b -= 1 return temp   print "Answer to PE188 = ",hyper_exp(1777, 1855, 8)```

Note: The last eight digits remain constant by the eighth iteration.
See problem 48 & problem 97

## Discussion

### 3 Responses to “Project Euler Problem 188 Solution”

1. I don’t see where you’ve justified that:

a**(a**(a**(a** … a mod 10**8) mod 10**8) mod 10**8) mod 10**8

is equivalent to:

a**(a**(a**(a** … a))) mod 10**8.

So… is there some principle of math that let’s you make that equivalence? Is it always true? Or: did it happen to be true (and you got lucky in this case) owing to the nature of a=1777 and it being coprime to 10**8?

(Project Euler handle: dharasty)

Posted by D Harasty | November 6, 2012, 5:51 PM