powertower.py

# TODO: this still doesn't quite account correctly for the case where you have a
#       small exponent, which doesn't quite catch the periodic part of the
#       powers
#       e.g. the powers of 5 mod 10^5 go
#       [1, 5, 25, 125, 625, 3125, ..., 40625] (...3125)
#       so the power tower [5, 2] mod 10^5 wil incorrectly be stated as 65625.

def last_digit_of_power_tower(tower, base=10):
    """
    Find the last digit of a power tower in some base (ie reduce a power tower
    modulo that base)

    `tower` should be a list of nonnegative integers - eg 1^2^3^4 is represented
    as [1, 2, 3, 4].
    """
    if len(tower) == 0:
        raise ValueError("empty power tower not defined")
    if len(tower) == 1:
        return tower[0] % base
    cur_power = tower[0] % base
    power_sequence = [1]
    power_sequence_lookup = {1: 0}
    while cur_power not in power_sequence_lookup:
        power_sequence_lookup[cur_power] = len(power_sequence)
        power_sequence.append(cur_power)
        cur_power = (cur_power * tower[0]) % base
    periodic_start_index = power_sequence_lookup[cur_power]
    exponent_modulus = len(power_sequence) - periodic_start_index
    print("The sequence of possible powers of {} mod {} is {} (...{})"
            .format(tower[0], base, power_sequence, cur_power))
    print("So the periodicity of    powers of {} mod {} is {}"
            .format(tower[0], base, exponent_modulus))
    exponent_reduced = last_digit_of_power_tower(tower[1:], exponent_modulus)
    last_digit = power_sequence[
            (exponent_reduced - periodic_start_index) % exponent_modulus
            + periodic_start_index]
    print("So {} is {} mod {}"
            .format("^".join(map(str, tower)), last_digit, base))
    return last_digit

if __name__ == "__main__":
    last_digit_of_power_tower([5] * 5, 10 ** 5)