cp's OEIS Frontend

A181957 Smallest positive integer which cannot be calculated by an expression containing n binary operators (either add or multiply) whose operands are integers between 1 and 9; parenthesis allowed.

%I A181957 #32 Oct 20 2021 08:17:55
%S A181957 10,19,92,239,829,2831,10061,38231,189311,621791,2853533,11423579
%N A181957 Smallest positive integer which cannot be calculated by an expression containing n binary operators (either add or multiply) whose operands are integers between 1 and 9; parenthesis allowed.
%H A181957 Derek M. Jones, <a href="/A181957/a181957_1.r.txt">R program for calculating values</a>
%H A181957 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A181957 a(4) = 239 because at least 4 operators are needed to calculate this value, e.g., (5*5+9)*7+1.
%o A181957 (PARI) first(n)=my(op=[(x, y)->x+y, (x, y)->x*y], v=vector(n+1), t); v[1]=[1..9]; for(k=2, #v, my(u=[]); for(i=1, (k+1)\2, my(a=v[i], b=v[k-i]); t=Set(concat(apply(f->setbinop(f, a, b), op))); u=concat(u, t)); v[k]=setminus(Set(u), [0])); t=10; for(i=1, #v, while(setsearch(v[i], t), t++); v[i]=t); v;
%o A181957 print(first(7)) \\ _Michael S. Branicky_, Oct 19 2021 after _Charles R Greathouse IV_ in A181898
%o A181957 (Python)
%o A181957 def aupton(nn):
%o A181957     alst = [10]
%o A181957     R = {0: set(range(1, 10))}   # R[n] is set reachable using n ops
%o A181957     for n in range(1, nn):
%o A181957         R[n] = set()
%o A181957         for i in range((n+1)//2):
%o A181957             for a in R[i]:
%o A181957                 for b in R[n-1-i]:
%o A181957                     R[n].update([a+b, a*b])
%o A181957         k = 10
%o A181957         while k in R[n]: k += 1  # n.b. R[n-1] <= R[n] due to * by 1
%o A181957         alst.append(k)
%o A181957     return alst
%o A181957 print(aupton(9)) # _Michael S. Branicky_, Oct 19 2021
%Y A181957 Cf. A181898, A181958, A181959, A181960.
%Y A181957 Cf. A005520 (operand literal is always 1).
%K A181957 nonn,more
%O A181957 0,1
%A A181957 _Derek M. Jones_, Apr 03 2012
%E A181957 a(5)-a(7) corrected by and a(8)-a(11) from _Michael S. Branicky_, Oct 19 2021