# Python program and utilities for OEIS A089520. # Michael S. Branicky, Jul 06 2022 # A089520 In Conway's Game of Life, the number of steps it takes for an n X n square, in which all the cells are in the "on" state, to die out or start to cycle, or -1 if there is no cycle. data = [1, 0, 5, 4, 11, 5, 5, 6, 16, 17, 32, 9, 18, 9, 22, 11, 33, 17, 20, 12, 26, 13, 48, 15, 46, 26, 295, 45, 154, 38, 62, 309, 38, 87, 78, 53, 96, 150, 641, 69, 82, 265, 216, 70, 70, 70, 120, 401, 107, 78, 70, 351, 318, 109, 297, 95, 122, -1, -1, 85, 232, 294, 127] # utilities and helper functions # RLE CODE for initial nxn square for use at, e.g., https://conwaylife.com/ def rle(n): print(f"x = {n}, y = {n}") for i in range(n): if i and i%10 == 0: print() print(f"{n}o$", end="") print("\n") def pretty_print(board, compact=False): global N for r in range(N): for c in range(N): if board[N*r+c] == 1: char = "@" else: char = "." if compact: delim = "" else: delim = " " print(char, end=delim) if not compact: print() print() # VERSION FOR TORUS def num_neighs_torus(board,r,c): global N neighs = 0 for ro in [-1, 0, 1]: for co in [-1, 0, 1]: if ro == 0 and co == 0: continue row, col = (r+ro)%N, (c+co)%N neighs += (board[row*N+col] == 1) return neighs # VERSION FOR SQUARE def num_neighs(board, r, c): global N neighs = 0 for ro in [-1, 0, 1]: for co in [-1, 0, 1]: if ro == 0 and co == 0: continue row, col = (r+ro), (c+co) if row < 0 or row >= N: continue if col < 0 or col >= N: continue alive = board[row*N+col] == 1 if alive and (row == 0 or row == N-1 or col == 0 or col == N-1): assert False, ("increase N") neighs += (board[row*N+col] == 1) return neighs def nextgen(board): global N newboard = [0 for i in range(N*N)] for r in range(N): for c in range(N): status = board[r*N+c] neighs = num_neighs(board,r,c) if status == 1: if 2 <= neighs <= 3: newboard[r*N+c]=1 else: if neighs == 3: newboard[r*N+c]=1 return tuple(newboard) # MAIN PROGRAM from time import time from itertools import product N = 100 SIMU_LIMIT = 10000 time0 = time() def a(n): global N N = 4*n # works for a(1)-a(57) alldead = tuple(0 for _ in range(N*N)) board = [0 for _ in range(N*N)] start = N//2 - n//2 for r in range(start, start+n): for c in range(start, start+n): board[r*N+c] = 1 board = tuple(board) boardlst = [board] for gens in range(1, SIMU_LIMIT+1): nextboard = nextgen(board) if nextboard==alldead: return gens if nextboard in boardlst: return gens - (gens - boardlst.index(nextboard)) boardlst.append(nextboard) board = nextboard alst = [] for n in range(1, 58): an = a(n) alst.append(an) print(n, an, time()-time0) print(" ", alst) print(" ", data)