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,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

Links

Table of n, a(n) for n=1..8.

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

Cf. A071314, A309885.

Sequence in context: A316772 A123440 A071314 * A123441 A086441 A316696

Adjacent sequences: A309883 A309884 A309885 * A309887 A309888 A309889

Keyword

nonn,hard,more

Author

Matej Veselovac, Aug 21 2019

Status

approved