cp's OEIS Frontend

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 +, -, *, /.

%I A071985 #12 Dec 29 2022 06:46:29
%S A071985 1,3,7,17,47,158,681,3209,17989,104289,635867
%N 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 +, -, *, /.
%C A071985 For all n>=2, A060315(n+1) > a(n) > A060315(n).
%H A071985 Gilles Bannay, <a href="https://web.archive.org/web/20061201125224/http://gilles.bannay.free.fr/jeux_us.html">Countdown Problem</a>
%H A071985 <a href="/index/Fo#4x4">Index entries for similar sequences</a>
%e A071985 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.
%o A071985 (Python)
%o A071985 def a(n):
%o A071985     R = dict() # index of each reachable subset is [card(s)-1][s]
%o A071985     for i in range(n): R[i] = dict()
%o A071985     for i in range(1, n+1): R[0][(i,)] = {i}
%o A071985     reach = set(i for i in range(1, n+1)) if n > 1 else set()
%o A071985     for j in range(1, n-1):
%o A071985         for i in range((j+1)//2):
%o A071985             for s1 in R[i]:
%o A071985                 for s2 in R[j-1-i]:
%o A071985                     if set(s1) & set(s2) == set():
%o A071985                         s12 = tuple(sorted(set(s1) | set(s2)))
%o A071985                         if s12 not in R[len(s12)-1]:
%o A071985                             R[len(s12)-1][s12] = set()
%o A071985                         for a in R[i][s1]:
%o A071985                             for b in R[j-1-i][s2]:
%o A071985                                 allowed = [a+b, a*b, a-b, b-a]
%o A071985                                 if a!=0 and b%a==0: allowed.append(b//a)
%o A071985                                 if b!=0 and a%b==0: allowed.append(a//b)
%o A071985                                 R[len(s12)-1][s12].update(allowed)
%o A071985                                 reach.update(allowed)
%o A071985     k = 1
%o A071985     while k in reach: k += 1
%o A071985     return k
%o A071985 print([a(n) for n in range(1, 6)]) # _Michael S. Branicky_, Jul 29 2022
%Y A071985 Cf. A060315.
%K A071985 hard,more,nonn
%O A071985 1,2
%A A071985 Koksal Karakus (karakusk(AT)hotmail.com), Jun 17 2002
%E A071985 a(11) from _Michael S. Branicky_, Jul 29 2022