cp's OEIS Frontend

A071314 a(n) is the smallest number that cannot be obtained from the numbers {2^0,2^1,...,2^n} using each number at most once and the operators +, -, *, /. Parentheses are allowed, intermediate fractions are not allowed.

%I A071314 #41 Aug 20 2024 03:09:20
%S A071314 2,4,11,27,77,595,2471,9643,51787
%N A071314 a(n) is the smallest number that cannot be obtained from the numbers {2^0,2^1,...,2^n} using each number at most once and the operators +, -, *, /. Parentheses are allowed, intermediate fractions are not allowed.
%C A071314 The A309886 is a similar sequence, except: there we allow intermediate fractions, and we require all numbers to be used when building an expression. - _Matej Veselovac_, Aug 28 2019
%C A071314 For n>=2, the largest number that can be obtained in this manner is given by the following formula: (2^1 + 2^0)*(Product_{k=2..n} 2^k). This product notation is equivalent to the expression: (3/2)*2^(n*(n+1)/2). Thus, for n>=2, this sequence has an upper bound: (3/2)*2^(n*(n+1)/2) + 1. - _Alejandro J. Becerra Jr._, Apr 22 2020
%H A071314 G. Bannay, <a href="https://web.archive.org/web/20061201125224/http://gilles.bannay.free.fr/jeux_us.html">Countdown Problem</a>
%H A071314 <a href="/index/Fo#4x4">Index entries for similar sequences</a>
%F A071314 a(n) <= A309886(n+1). - _Michael S. Branicky_, Jul 15 2022
%e A071314 a(2) = 11 because using {1,2,4} and the four operations we can obtain all the numbers up to 10, for example 10=(4+1)*2, but we cannot obtain 11 in the same way.
%e A071314 a(6) <= 595 since the only way to make 595 is: (1 + 16 + 4/8)*(2 + 32), which requires the use of an intermediate fraction 4/8 in the calculation process, which is not allowed. - _Matej Veselovac_, Aug 28 2019
%e A071314 a(8) != 19351 = 1+(2+256)*(((4+16)*(128-8))/32). - _Michael S. Branicky_, Jul 15 2022
%o A071314 (Python)
%o A071314 def a(n):
%o A071314     R = dict() # index of each reachable subset is [card(s)-1][s]
%o A071314     for i in range(n+1): R[i] = dict()
%o A071314     for i in range(n+1): R[0][(2**i,)] = {2**i}
%o A071314     reach = set(2**i for i in range(n+1))
%o A071314     for j in range(1, n+1):
%o A071314         for i in range((j+1)//2):
%o A071314             for s1 in R[i]:
%o A071314                 for s2 in R[j-1-i]:
%o A071314                     if set(s1) & set(s2) == set():
%o A071314                         s12 = tuple(sorted(set(s1) | set(s2)))
%o A071314                         if s12 not in R[len(s12)-1]:
%o A071314                             R[len(s12)-1][s12] = set()
%o A071314                         for a in R[i][s1]:
%o A071314                             for b in R[j-1-i][s2]:
%o A071314                                 allowed = [a+b, a*b, a-b, b-a]
%o A071314                                 if a != 0 and b%a == 0: allowed.append(b//a)
%o A071314                                 if b != 0 and a%b == 0: allowed.append(a//b)
%o A071314                                 R[len(s12)-1][s12].update(allowed)
%o A071314                                 reach.update(allowed)
%o A071314     k = 1
%o A071314     while k in reach: k += 1
%o A071314     return k
%o A071314 print([a(n) for n in range(6)]) # _Michael S. Branicky_, Jul 15 2022
%Y A071314 Cf. A060315, A309886.
%K A071314 nonn,hard,more
%O A071314 0,1
%A A071314 Koksal Karakus (karakusk(AT)hotmail.com), Jun 11 2002
%E A071314 a(8) corrected by _Michael S. Branicky_, Jul 15 2022