# Python program for OEIS A146971 # Number of weight-n binary n X n matrices that yield the all-ones matrix after repeatedly changing a 0 having at least two 1-neighbors to a 1. # by Michael S. Branicky, Feb 21 2021 data = [1, 2, 14, 130, 1615, 23140, 383820, 7006916, 140537609, 3035127766] from time import time time0 = time() # (Python) import numpy as np from numba import njit from itertools import combinations @njit def matok(m, n): changed = True while changed: changed = False for i, j in np.argwhere(m == 0): neighs = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)] sn = 0 for ine, jne in neighs: if 0 <= ine < n and 0 <= jne < n: if m[ine, jne] == 1: sn += 1 if sn == 2: m[i, j] = 1 changed = True break if np.all(m == 1): return True return np.all(m == 1) def a(n): s, m = 0, [0 for i in range(n*n)] for c in combinations(range(n*n), n): for i in c: m[i] = 1 s += matok(np.resize(m, (n,n)), n) for i in c: m[i] = 0 return s for n in range(1, 20): print(n, a(n)) # ~~~~ print(" ", time()-time0)