# 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)