# Python program for OEIS A262239 # Michael S. Branicky, Dec 31 2021 # A262239 Number of (n+3)X(4+3) 0..1 arrays with each row and column divisible by 11, read as a binary number with top and left being the most significant bits. 0 data = [12, 31, 238, 1306, 10747, 77490, 778464, 4345849, 31098659, 251964601, 2327886878] # (Python) from itertools import product candrows = [bin(m)[2:].zfill(7) for m in range(0, 2**7, 11)] # hardcoded backtracking; first n-1 rows have no constraints def a(n): if n == 1: return 12 count = 0 candcols = [bin(m)[2:].zfill(n+3) for m in range(0, 2**(n+3), 11)] prefixes = set(c[:n+3-tail] for tail in range(4) for c in candcols) for arr in product(candrows, repeat=n-1): cols = list("".join(arr[i][j] for i in range(n-1)) for j in range(7)) for rowm4 in candrows: if not all(cols[j]+rowm4[j] in prefixes for j in range(7)): continue for rowm3 in candrows: if not all(cols[j]+rowm4[j]+rowm3[j] in prefixes for j in range(7)): continue for rowm2 in candrows: if not all(cols[j]+rowm4[j]+rowm3[j]+rowm2[j] in prefixes for j in range(7)): continue for rowm1 in candrows: if not all(cols[j]+rowm4[j]+rowm3[j]+rowm2[j]+rowm1[j] in prefixes for j in range(7)): continue count += 1 return count print([a(n) for n in range(1, 6)]) # ~~~~ print(data) print() from time import time time0 = time() for n in range(1, 10): an = a(n) print(n, an, an == data[n-1], time()-time0)