roll.py

# There is a simple connection between natural numbers and DFAs on a singleton
# alphabet. The importance of this connection is easily illustrated in modular
# arithmetic.

# Def: A roll is a pair of natural numbers, the second one of which is nonzero.

# (Thus a roll is a fraction, but we won't make this connection.)

# To every roll [p, q] we associate a DFA which goes through p states and then
# goes into a loop of length q. Addition and multiplication of rolls, as well
# as of their states, is easily defined. The states of this DFA are
# conventionally taken to be the natural range [0, p+q).

# Good picture: https://pixabay.com/p-147631/?no_redirect

# (Actually, the theory of rolls should require no prior theory of natural
# numbers if a roll is defined more like a DFA directly, but that's a more
# beautiful story.)

# Here's some arithmetic aided by rolls.

""" Compute what state the DFA of b will be in after natural input a. """
def nat_mod_roll(a, b):
    flat, loop = b
    return a if a < flat else (a - flat) % loop + flat

"""
Compute the smallest roll whose DFA states can index the states that the DFA
of b ends up in after any input a^i.
"""
def roll_of_powers(a, b):
    powers = [1]
    while True:
        c = nat_mod_roll(a*powers[-1], b)
        if c in powers:
            return powers.index(c), len(powers) - powers.index(c)
        powers.append(c)

""" Compute what state the DFA of b will be in after tower input a. """
def tower_mod_roll(a, b):
    if len(a) == 0:
        return nat_mod_roll(1, b)
    return nat_mod_roll(a[0]**tower_mod_roll(a[1:], roll_of_powers(a[0], b)), b)

def mod(a, b):
    if isinstance(a, int): a = a,
    if isinstance(b, int): b = 0, b
    return tower_mod_roll(a, b)

def test():
    arg_a = [2, 10], [100, 1000, 10000], [104, 2], [2, 3]
    arg_b = 100, 100000, 5, 112
    expect = 24, 0, 1, 8
    for a, b, good in zip(arg_a, arg_b, expect):
        c = mod(a, b)
        print("mod({}, {}) = {} -- ".format(a, b, c), end="")
        print("OK" if c == good else "FAIL (expected {})".format(good))

if __name__ == "__main__":
    test()