login
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.
1
1, 2, 4, 10, 22, 58, 233, 827, 3359, 16631, 114371, 708278, 3975838, 35724478
OFFSET
0,2
COMMENTS
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).
LINKS
Zach Wissner-Gross, Can You Escape the Desert?, Riddler Express, Jun 03 2022.
FORMULA
a(n) <= A060315(n+1). - Michael S. Branicky, Jun 04 2022
EXAMPLE
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.
PROG
(Python)
def a(n):
R = dict() # R[|s|-1][s] = reachable values using subset s
for i in range(n+1): R[i] = dict()
for i in range(1, n+1): R[0][(i, )] = {i}
reach = set(range(1, n+1))
for j in range(1, n):
for i in range((j+1)//2):
for s in R[i]:
for t in R[j-1-i]:
if set(s) & set(t) == set():
u = tuple(sorted(set(s) | set(t)))
if u not in R[len(u)-1]:
R[len(u)-1][u] = set()
for a in R[i][s]:
for b in R[j-1-i][t]:
R[len(u)-1][u].update([a+b, a*b])
reach.update([a+b, a*b])
k = n+1
while k in reach: k += 1
return k
print([a(n) for n in range(10)]) # Michael S. Branicky, May 30 2022
CROSSREFS
Cf. A060315.
Sequence in context: A030234 A205490 A221839 * A205499 A148086 A005962
KEYWORD
nonn,more
AUTHOR
Dean D. Ballard, May 26 2022
EXTENSIONS
a(10)-a(12) from Michael S. Branicky, May 27 2022
a(13) from Michael S. Branicky, May 30 2022
a(0) inserted by Michael S. Branicky, Jun 04 2022
STATUS
approved