A071313 - OEIS

%I #13 Dec 29 2022 06:46:21

%S 2,5,11,41,92,733,4337,28972,195098,1797746

%N a(n) is the smallest number that cannot be obtained from the numbers {1,3,...,2*n-1} using each number at most once and the operators +, -, *, /, where intermediate subexpressions must be integers.

%C If noninteger subexpressions are permitted, a(5) = 122 and not 92 since 92 = (3+7)*(9 + 1/5). - _Michael S. Branicky_, Jul 01 2022

%H Gilles Bannay, <a href="https://web.archive.org/web/20061201125224/http://gilles.bannay.free.fr/jeux_us.html">Countdown Problem</a>

%H <a href="/index/Fo#4x4">Index entries for similar sequences</a>

%e a(2)=5 because using {1,3} and the four operations we can obtain 1=1, 3-1=2, 3=3, 3+1=4 but we cannot obtain 5 in the same way.

%o (Python)

%o def a(n):

%o     R = dict() # index of each reachable subset is [card(s)-1][s]

%o     for i in range(n): R[i] = dict()

%o     for i in range(1, n+1): R[0][(2*i-1,)] = {2*i-1}

%o     reach = set(range(1, 2*n, 2))

%o     for j in range(1, n):

%o         for i in range((j+1)//2):

%o             for s1 in R[i]:

%o                 for s2 in R[j-1-i]:

%o                     if set(s1) & set(s2) == set():

%o                         s12 = tuple(sorted(set(s1) | set(s2)))

%o                         if s12 not in R[len(s12)-1]:

%o                             R[len(s12)-1][s12] = set()

%o                         for a in R[i][s1]:

%o                             for b in R[j-1-i][s2]:

%o                                 allowed = [a+b, a*b, a-b, b-a]

%o                                 if a!=0 and b%a==0: allowed.append(b//a)

%o                                 if b!=0 and a%b==0: allowed.append(a//b)

%o                                 R[len(s12)-1][s12].update(allowed)

%o                                 reach.update(allowed)

%o     k = 1

%o     while k in reach: k += 1

%o     return k

%o print([a(n) for n in range(1, 9)]) # _Michael S. Branicky_, Jul 01 2022

%Y Cf. A060315, A071848.

%K hard,more,nonn

%O 1,1

%A Koksal Karakus (karakusk(AT)hotmail.com), Jun 11 2002

%E a(10) from _Michael S. Branicky_, Jul 01 2022