cp's OEIS Frontend

A358075 a(1) = 1; a(n+1) is the smallest integer > 0 that cannot be obtained from the integers {a(1), ..., a(n)} using each number exactly once and the operators +, -, *, /, where intermediate subexpressions must be integers.

%I A358075 #32 Nov 10 2022 04:58:52
%S A358075 1,2,4,11,34,152,1007,6703,56837,766478
%N A358075 a(1) = 1; a(n+1) is the smallest integer > 0 that cannot be obtained from the integers {a(1), ..., a(n)} using each number exactly once and the operators +, -, *, /, where intermediate subexpressions must be integers.
%C A358075 A variation of sequence A071115: terms are used "exactly once" instead of "at most once". First difference is a(8) = 6703 < 7335 = A071115(8).
%e A358075 All positive numbers up to 151 can be computed from the first 5 terms 1, 2, 4, 11, 34; e.g., 105 = (1 + 4) * (34 - 11 - 2). All terms are used, and each term is used only once.
%e A358075 There is no such formula for 152, so a(6) = 152.
%p A358075 restart: with(combinat):
%p A358075 # generate numbers from set s
%p A358075 GEN := proc(s) option remember;
%p A358075    local erg,X,Y,x,y,i,a,b;
%p A358075    if nops(s) < 2 then
%p A358075       return s;
%p A358075    fi;
%p A358075    erg := {};
%p A358075    for i to nops(s)/2 do
%p A358075       for a in choose(s,i) do
%p A358075          b := s minus a;
%p A358075          X := procname(a);
%p A358075          Y := procname(b);
%p A358075          for x in X do
%p A358075          for y in Y do
%p A358075             erg := erg union {x+y};
%p A358075             if x < y then
%p A358075                erg := erg union {y-x};
%p A358075             elif x > y then
%p A358075                erg := erg union {x-y};
%p A358075             fi;
%p A358075             erg := erg union {x*y};
%p A358075             if type(x/y,integer) then
%p A358075                erg := erg union {x/y};
%p A358075             elif type(y/x,integer) then
%p A358075                erg := erg union {y/x};
%p A358075             fi;
%p A358075          od;
%p A358075          od;
%p A358075       od;
%p A358075    od;
%p A358075    return erg;
%p A358075 end:
%p A358075 # minimal excluded number (not in set s)
%p A358075 MEX := proc(s)
%p A358075    local i;
%p A358075    for i to infinity do
%p A358075       if not member(i,s) then
%p A358075          return i;
%p A358075       fi;
%p A358075    od;
%p A358075 end:
%p A358075 MaxIndex := 8;
%p A358075 a := array(1..MaxIndex):
%p A358075 w := {}:
%p A358075 for n to MaxIndex do
%p A358075    a[n] := MEX(GEN(w));
%p A358075    w := w union {a[n]};
%p A358075 od:
%p A358075 seq(a[n],n=1..MaxIndex);
%o A358075 (Python)
%o A358075 def a(n, v):
%o A358075     R = dict() # index of each reachable subset is [card(s)-1][s]
%o A358075     for i in range(n): R[i] = dict()
%o A358075     for i in range(n): R[0][(v[i], )] = {v[i]}
%o A358075     for j in range(1, n):
%o A358075         for i in range((j+1)//2):
%o A358075             for s1 in R[i]:
%o A358075                 for s2 in R[j-1-i]:
%o A358075                     if set(s1) & set(s2) == set():
%o A358075                         s12 = tuple(sorted(set(s1) | set(s2)))
%o A358075                         if s12 not in R[len(s12)-1]:
%o A358075                             R[len(s12)-1][s12] = set()
%o A358075                         for a in R[i][s1]:
%o A358075                             for b in R[j-1-i][s2]:
%o A358075                                 allowed = [a+b, a*b, a-b, b-a]
%o A358075                                 if a!=0 and b%a==0: allowed.append(b//a)
%o A358075                                 if b!=0 and a%b==0: allowed.append(a//b)
%o A358075                                 R[len(s12)-1][s12].update(allowed)
%o A358075     k = 1
%o A358075     while k in R[n-1][tuple(v)]: k += 1
%o A358075     return k
%o A358075 alst = [1]
%o A358075 [alst.append(a(n, alst)) for n in range(1, 8)]
%o A358075 print(alst) # _Michael S. Branicky_, Oct 30 2022
%Y A358075 Cf. A071115, A357891.
%K A358075 nonn,hard,more
%O A358075 1,2
%A A358075 _Rainer Rosenthal_, Oct 29 2022
%E A358075 a(9) from _Michael S. Branicky_, Oct 30 2022
%E A358075 a(10) from _Michael S. Branicky_, Nov 07 2022