cp's OEIS Frontend

A354423 a(0)=1; a(n) is the smallest positive integer that cannot be obtained from the integers {1, ..., n} using each number at most once, and the operators addition and multiplication.

%I A354423 #37 Jun 05 2022 06:09:42
%S A354423 1,2,4,10,22,58,233,827,3359,16631,114371,708278,3975838,35724478
%N A354423 a(0)=1; a(n) is the smallest positive integer that cannot be obtained from the integers {1, ..., n} using each number at most once, and the operators addition and multiplication.
%C A354423 This is a simpler version of A060315, which uses all four arithmetic operations: addition, subtraction, multiplication, and division. The sequence is the answer to FiveThirtyEight.com's Riddler Express of June 3, 2022 (see links).
%H A354423 Zach Wissner-Gross, <a href="https://fivethirtyeight.com/features/can-you-escape-the-desert/">Can You Escape the Desert?</a>, Riddler Express, Jun 03 2022.
%F A354423 a(n) <= A060315(n+1). - _Michael S. Branicky_, Jun 04 2022
%e A354423 a(3)=10 because 1=1, 2=2, 3=3, 4=1+3, 5=2+3, 6=2*3, 7=2*3+1, 8=(3+1)*2, 9=(1+2)*3, but there is no way to make 10 using 1, 2, and 3 at most once.
%o A354423 (Python)
%o A354423 def a(n):
%o A354423     R = dict()  # R[|s|-1][s] = reachable values using subset s
%o A354423     for i in range(n+1): R[i] = dict()
%o A354423     for i in range(1, n+1): R[0][(i,)] = {i}
%o A354423     reach = set(range(1, n+1))
%o A354423     for j in range(1, n):
%o A354423         for i in range((j+1)//2):
%o A354423             for s in R[i]:
%o A354423                 for t in R[j-1-i]:
%o A354423                     if set(s) & set(t) == set():
%o A354423                         u = tuple(sorted(set(s) | set(t)))
%o A354423                         if u not in R[len(u)-1]:
%o A354423                             R[len(u)-1][u] = set()
%o A354423                         for a in R[i][s]:
%o A354423                             for b in R[j-1-i][t]:
%o A354423                                 R[len(u)-1][u].update([a+b, a*b])
%o A354423                                 reach.update([a+b, a*b])
%o A354423     k = n+1
%o A354423     while k in reach: k += 1
%o A354423     return k
%o A354423 print([a(n) for n in range(10)]) # _Michael S. Branicky_, May 30 2022
%Y A354423 Cf. A060315.
%K A354423 nonn,more
%O A354423 0,2
%A A354423 _Dean D. Ballard_, May 26 2022
%E A354423 a(10)-a(12) from _Michael S. Branicky_, May 27 2022
%E A354423 a(13) from _Michael S. Branicky_, May 30 2022
%E A354423 a(0) inserted by _Michael S. Branicky_, Jun 04 2022