login
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
2, 4, 11, 27, 77, 597, 2473, 9643
OFFSET
1,1
COMMENTS
It is known that a(n) >= 2^n for n >= 1, and a(n) >= 2^n + 2^(n-2) + 1 for n >= 3. Can we extend this to more cases of n? Can we extend this to all n and find a formula for the sequence?
This is similar to A071314, except there not all powers need to be used, and there intermediate fractions are not allowed to be used. For example, 595 = (1 + 16 + 4/8)*(2 + 32) is valid here, but not there, and that's why a(6) = 597 > A071314(6) = 595, for comparison. Similarly, we have 2471 = (64 - 2 - 4/16)*(8 + 32) + 1 being a unique solution, using intermediate fraction 4/16.
Notice a(n)-1 can be used as a lower bound for A309885(n).
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
FORMULA
a(n) >= A071314(n-1). - Michael S. Branicky, Jul 15 2022
EXAMPLE
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
PROG
(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
CROSSREFS
Sequence in context: A316772 A123440 A071314 * A123441 A086441 A316696
KEYWORD
nonn,hard,more
AUTHOR
Matej Veselovac, Aug 21 2019
STATUS
approved