A309886 a(n) is the smallest number that cannot be obtained from the first n powers of two {2^0,2^1,...,2^(n-1)} using each power exactly once and the operations +,-,*,/. Parentheses are allowed.
2, 4, 11, 27, 77, 597, 2473, 9643
Offset: 1
Examples
a(1) = 2 since we can make 1 using {1}: 1=1 but can't make 2.
a(2) = 4 since we can make 1,2,3 using {1,2}, but can't make 4:
1 = 2 - 1
2 = 2 * 1
3 = 2 + 1
a(3) = 11 since we can make 1,...,10 using {1,2,4}, but not 11:
1 = 4 - (1 + 2)
2 = 4 - (1 * 2)
3 = (1 - 2) + 4
4 = (2 - 1) * 4
5 = 4 - (1 - 2)
6 = (1 * 2) + 4
7 = (1 + 2) + 4
8 = (1 * 2) * 4
9 = 1 + (2 * 4)
10 = (1 + 4) * 2
Programs
-
Python
from fractions import Fraction 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(n): R[0][(2**i,)] = {2**i} reach = set(2**i for i in range(n)) for j in range(1, n): 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: allowed.append(Fraction(b, a)) if b != 0: allowed.append(Fraction(a, b)) R[len(s12)-1][s12].update(allowed) reach.update(allowed) k = 1 # search the reachable set that uses all numbers while k in R[n-1][tuple(2**i for i in range(n))]: k += 1 return k print([a(n) for n in range(1, 6)]) # Michael S. Branicky, Jul 15 2022
Formula
a(n) >= A071314(n-1). - Michael S. Branicky, Jul 15 2022
Comments