A071985 a(n) is the smallest positive integer that cannot be obtained using at most n-1 of the integers {1, 2, ..., n} using each number at most once and the operators +, -, *, /.

1, 3, 7, 17, 47, 158, 681, 3209, 17989, 104289, 635867

Offset: 1

Author

Koksal Karakus (karakusk(AT)hotmail.com), Jun 17 2002

Keywords

• hard
• more
• nonn

Comments

For all n>=2, A060315(n+1) > a(n) > A060315(n).

Examples

			a(3)=7 because using two of the numbers {1,2,3} with the four operations we can obtain 1=1, 2=2, 3=3, 3+1=4, 3+2=5, 3*2=6 but we cannot obtain 7 in the same way.
		

Links

• Gilles Bannay, Countdown Problem
• Index entries for similar sequences

Crossrefs

Cf. A060315.

Programs

Python

def a(n):
    R = dict() # index of each reachable subset is [card(s)-1][s]
    for i in range(n): R[i] = dict()
    for i in range(1, n+1): R[0][(i,)] = {i}
    reach = set(i for i in range(1, n+1)) if n > 1 else set()
    for j in range(1, n-1):
        for i in range((j+1)//2):
            for s1 in R[i]:
                for s2 in R[j-1-i]:
                    if set(s1) & set(s2) == set():
                        s12 = tuple(sorted(set(s1) | set(s2)))
                        if s12 not in R[len(s12)-1]:
                            R[len(s12)-1][s12] = set()
                        for a in R[i][s1]:
                            for b in R[j-1-i][s2]:
                                allowed = [a+b, a*b, a-b, b-a]
                                if a!=0 and b%a==0: allowed.append(b//a)
                                if b!=0 and a%b==0: allowed.append(a//b)
                                R[len(s12)-1][s12].update(allowed)
                                reach.update(allowed)
    k = 1
    while k in reach: k += 1
    return k
print([a(n) for n in range(1, 6)]) # Michael S. Branicky, Jul 29 2022

Extensions

a(11) from Michael S. Branicky, Jul 29 2022