# Python program for OEIS A060315 and its +, *, - version # Michael S. Branicky, May 30 2022 # A060315 a(1)=1; a(n) is the smallest positive integer that cannot be obtained from the integers {0, 1, ..., n-1} using each number at most once and the operators +, -, *, /. 19 data = [1, 2, 4, 10, 29, 76, 284, 1413, 7187, 38103, 231051, 1765186, 10539427] from fractions import Fraction test = {3, Fraction(3, 1)} print(test, len(test)) print() # (Python) from fractions import Fraction def a(n, include_division=True): R = dict() # index of each reachable subset is [card(s)-1][s] for i in range(n): R[i] = dict() for i in range(n): R[0][(i,)] = {i} reach = set(range(n)) for j in range(1, n): for i in range((j+1)//2): for s1 in R[i]: for s2 in R[j-1-i]: if set(s1) & set(s2) == set(): s12 = tuple(sorted(set(s1) | set(s2))) if s12 not in R[len(s12)-1]: R[len(s12)-1][s12] = set() for a in R[i][s1]: for b in R[j-1-i][s2]: allowed = [a+b, a*b, a-b, b-a] if include_division: if a != 0: allowed.append(Fraction(b, a)) if b != 0: allowed.append(Fraction(a, b)) R[len(s12)-1][s12].update(allowed) reach.update(allowed) k = n while k in reach: k += 1 return k print([a(n) for n in range(1, 6)]) print(data) print() # test the +, *, - version # can get a(1)..a(11) in ~1 hour; a(12) itself takes ~14 hours print([a(n, include_division=False) for n in range(1, 9)]) print(data) print() from time import time time0 = time() INCLUDE_DIVISION = True # change to False for +, *, - version alst = [] for n in range(1, 101): an = a(n, include_division=INCLUDE_DIVISION) alst.append(an) print(n, an, time()-time0) print(" ", alst) print(" ", data)