# Python program for OEIS A210109
# by Michael S. Branicky, Aug 27 2021
# dedicated to Lydia Marie Branicky on the occasion of her 7th birthday

# From the OEIS:
# "A210109		Number of 3-divided binary sequences (or words) of length n.
data = [0, 0, 0, 2, 7, 23, 54, 132, 290, 634, 1342, 2834, 5868, 12140, 24899, 50929, 103735, 210901, 427623, 865910, 1750505, 3535098, 7131321, 14374647, 28952661, 58280123, 117248217, 235770302, 473897980, 952183214, 1912535827]

# "A binary sequence (or word) W of length n is 3-divided
# if it can be written as a concatenation W = XYZ such that
# XYZ is strictly earlier in lexicographic order than any of
# the five permutations  XZY, ZYX, YXZ, YZX, ZXY."

# uses bit operations and numba for speed

from numba import njit

@njit
def is3div(k, n): # check n least significant bits of integer k
    fullmask =  (1 << n) - 1
    b = fullmask & k
    maskX = 1
    for lenX in range(1, n - 1):
        X = (b & (maskX << (n - lenX))) >> (n - lenX)
        maskY = 1
        maskZ = (1 << (n - lenX - 1)) - 1
        for j in range(lenX + 1, n):
            lenY = j - lenX
            lenZ = n - j
            Y = (b & (maskY << lenZ)) >> lenZ
            Z = b & maskZ
            all_greater = True

            # check the 5 permutations in turn: XZY, ZYX, YXZ, YZX, ZXY
            XZY = (X << (n - lenX)) + (Z << lenY) + Y
            if XZY <= b:
                all_greater = False
            ZYX = (Z << (n - lenZ)) + (Y << lenX) + X 
            if ZYX <= b:
                all_greater = False
            YXZ = (Y << (n - lenY)) + (X << lenZ) + Z 
            if YXZ <= b:
                all_greater = False
            YZX = (Y << (n - lenY)) + (Z << lenX) + X 
            if YZX <= b:
                all_greater = False
            ZXY = (Z << (n - lenZ)) + (X << lenY) + Y 
            if ZXY <= b:
                all_greater = False

            maskY <<= 1
            maskY += 1
            maskZ >>= 1
            Y = b & maskY
            Z = b & maskZ
            if all_greater:
                return True
        maskX <<= 1
        maskX += 1
    return False

@njit
def a(n):
    c = 0
    for k in range(2**n, 2**(n+1)):
        if is3div(k, n):
            c += 1
    return c

tests = [
    "0.01.1",
    "0.10.1",
    "0.001.1",
    "0.010.1",
    "0.01.10",
    "0.01.11",
    "0.100.1",
    "0.10.11",
    "0.110.1"
]
print("TESTS:")
for t in tests:
    t = t.replace(".", "")
    b = int(t, 2)
    print("   ", t, is3div(b, len(t)))
print()

from time import time
time0 = time()
alst = []
for n in range(1, 101):
    an = a(n)
    alst.append(an)
    print(n, an, time()-time0, flush=True)
    print("   ", alst, flush=True)
    print("   ", data, flush=True)
    print(flush=True)