#!/usr/bin/env python3

# AS-IS.
# Work in progress.  debug code still here.

import copy
dbg = 0
class Matrix(object):
    def __init__(self, n):
        self.data = []
        for i in range(n):
            self.data.append([])
            for j in range(n):
                self.data[-1].append(False)
        global dbg
        dbg = dbg + n*n
    @classmethod
    def fromTaps(self, taps):
        n = max(taps) + 1
        result = Matrix(n)
        for i in range(n-1):
            result.data[i][i+1] = True
        for i in taps:
            result.data[-1][n-1-i] = True
        global dbg
        dbg = dbg + n + len(taps)
        return result

    def print(self):
        s = ""
        for row in self.data:
            for element in row:
                s += "%d "%(1 if element else 0)
            s += "\n"
        print(s)

    def mul(self, other):
        element = False
        n = len(self.data)
        result = Matrix(n)
        for r in range(n):
            for c in range(n):
                element = False
                for i in range(n):
                    element = (element != (self.data[r][i] and other.data[i][c]))
                result.data[r][c] = element
        global dbg
        dbg = dbg + n*n*n
        return result

    def isIdentity(self):
        n = len(self.data)
        global dbg
        dbg = dbg + n*n
        for r in range(n):
            for c in range(n):
                if ((r == c) != self.data[r][c]):
                    return False
        return True


# factors of 2**N - 1
factors = [[1], [3], [7], [3, 5], [31], [3, 7], [127], [3, 5, 17], [7, 73], [3, 11, 31],
    [23, 89], [3, 5, 7, 13], [8191], [3, 43, 127], [7, 31, 151], [3, 5, 17, 257], [131071],
    [3, 7, 19, 73], [524287], [3, 5, 11, 31, 41], [7, 127, 337], [3, 23, 89, 683], [47, 178481],
    [3, 5, 7, 13, 17, 241], [31, 601, 1801], [3, 2731, 8191], [7, 73, 262657],
    [3, 5, 29, 43, 113, 127], [233, 1103, 2089], [3, 7, 11, 31, 151, 331], [2147483647],
    [3, 5, 17, 257, 65537], [7, 23, 89, 599479], [3, 43691, 131071], [31, 71, 127, 122921],
    [3, 5, 7, 13, 19, 37, 73, 109], [223, 616318177], [3, 174763, 524287], [7, 79, 8191, 121369],
    [3, 5, 11, 17, 31, 41, 61681], [13367, 164511353], [3, 7, 43, 127, 337, 5419],
    [431, 9719, 2099863], [3, 5, 23, 89, 397, 683, 2113], [7, 31, 73, 151, 631, 23311],
    [3, 47, 178481, 2796203], [2351, 4513, 13264529], [3, 5, 7, 13, 17, 97, 241, 257, 673],
    [127, 4432676798593], [3, 11, 31, 251, 601, 1801, 4051], [7, 103, 2143, 11119, 131071],
    [3, 5, 53, 157, 1613, 2731, 8191], [6361, 69431, 20394401], [3, 7, 19, 73, 87211, 262657],
    [23, 31, 89, 881, 3191, 201961], [3, 5, 17, 29, 43, 113, 127, 15790321], [7, 32377, 524287, 1212847],
    [3, 59, 233, 1103, 2089, 3033169], [179951, 3203431780337],
    [3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321], [2305843009213693951], [3, 715827883, 2147483647],
    [7, 73, 127, 337, 92737, 649657], [3, 5, 17, 257, 641, 65537, 6700417]]

cycleTable = [[0]] # 0 indexing, but prefer to use degree.  init a 0th degree element
for i in range(len(factors)):
    v = [2**(i+1) - 1]
    if len(factors[i]) > 1:
        for j in range(len(factors[i])):
            v.append(v[0]//factors[i][j])
    cycleTable.append(v)



def checkTaps(x):
    taps = []
    if type(x) == type([]):
        taps = copy.copy(x)
    else:
        v = x
        i = 0
        while v > 0:
            if (v % 2) == 1:
                taps.append(i)
            v = v // 2
            i = i + 1

    deg = max(taps)+1
    cycles = copy.copy(cycleTable[deg])

    x = Matrix.fromTaps(taps)
    mtxs = []
    for i in range(len(cycles)):
        mtxs.append(copy.copy(x))

    xval = 1
    for exp in range(max(taps)+1):
        x = x.mul(x)
        xval = xval * 2
        for i in range(len(cycles)):
            cycles[i] = cycles[i] // 2
            if cycles[i] % 2 == 1:
                mtxs[i] = mtxs[i].mul(x)

    if not mtxs[0].isIdentity():
        return -1

    for i in range(1, len(cycles)):
        if mtxs[i].isIdentity():
            return -2
    return 1


maxlen = []
factorlen = []
weirdlen = []
if __name__ == "__main__":
    for t in range(62):
        result = checkTaps([62, t])
        if result > 0:
            print("%d, 62 maximal"%(t))
            maxlen.append("%02x"%t)
        elif result == -2:
            print("%d, 62 factors"%(t))
            factorlen.append("%02x"%t)
        elif result == -1:
            print("%d, 62 nothing"%(t))
            weirdlen.append("%02x"%t)

print(maxlen)
print(factorlen)
print(weirdlen)
print(dbg)