sumregex.py

import re
from random import randint

dfa = re.compile('((000|011|101)*(110(010|100|111)*001)*)*$')

def issum(A, B, C):
    """Return True iff non-negative integers A+B == C"""
    strings = [bin(n)[:1:-1] for n in [A,B,C]]
    maxlen = max(len(s) for s in strings)
    padded = (s+'0'*(maxlen-len(s)) for s in strings)
    interleaved = (''.join(zipped) for zipped in zip(*padded))
    string = ''.join(interleaved)

    return bool(dfa.match(string))

if __name__ == '__main__':
    N = 10000
    max_bits = 1000
    for _ in range(N//10):
        A = randint(0, 2**randint(0, max_bits)-1)
        B = randint(0, 2**randint(0, max_bits)-1)
        C = A+B
        assert issum(A, B, C)
        for _ in range(10):
            D = randint(0, 2**randint(0, max_bits)-1)
            assert D == C or not issum(A, B, D)
    print('👍')