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, 2, 4, 10, 22, 58, 233, 827, 3359, 16631, 114371, 708278, 3975838, 35724478

Offset: 0

Author

Dean D. Ballard, May 26 2022

Keywords

• nonn
• more

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

Examples

			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.
		

Links

• Zach Wissner-Gross, Can You Escape the Desert?, Riddler Express, Jun 03 2022.

Crossrefs

Cf. A060315.

Programs

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

Formula

a(n) <= A060315(n+1). - Michael S. Branicky, Jun 04 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