project euler problem 188 https projecteuler netproblem188 the hyperexponentiation of a number the hyperexponentiation or tetration of a number a by a positive integer b denoted by ab or ba is recursively defined by a1 a ak1 aak thus we have e g 32 33 27 hence 33 327 7625597484987 and 34 is roughly 103 63833464002409961012 find the last 8 digits of 17771855 references https en wikipedia orgwikitetration small helper function for modular exponentiation fast exponentiation algorithm returns the modular exponentiation that is the value of base exponent modulovalue without calculating the actual number modexpt2 4 10 6 modexpt2 1024 100 16 modexpt13 65535 7 6 returns the last 8 digits of the hyperexponentiation of base by height i e the number baseheight solutionbase3 height2 27 solutionbase3 height3 97484987 solutionbase123 height456 digits4 2547 calculate baseheight by rightassiciative repeated modular exponentiation small helper function for modular exponentiation fast exponentiation algorithm returns the modular exponentiation that is the value of base exponent modulo_value without calculating the actual number _modexpt 2 4 10 6 _modexpt 2 1024 100 16 _modexpt 13 65535 7 6 returns the last 8 digits of the hyperexponentiation of base by height i e the number base height solution base 3 height 2 27 solution base 3 height 3 97484987 solution base 123 height 456 digits 4 2547 calculate base height by right assiciative repeated modular exponentiation
def _modexpt(base: int, exponent: int, modulo_value: int) -> int:
    

    if exponent == 1:
        return base
    if exponent % 2 == 0:
        x = _modexpt(base, exponent // 2, modulo_value) % modulo_value
        return (x * x) % modulo_value
    else:
        return (base * _modexpt(base, exponent - 1, modulo_value)) % modulo_value


def solution(base: int = 1777, height: int = 1855, digits: int = 8) -> int:
    

    
    
    result = base
    for _ in range(1, height):
        result = _modexpt(base, result, 10**digits)

    return result


if __name__ == "__main__":
    print(f"{solution() = }")