A309886 -id:A309886 - 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.

2, 4, 11, 27, 77, 595, 2471, 9643, 51787

Offset: 0

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

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

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

			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.
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
a(8) != 19351 = 1+(2+256)*(((4+16)*(128-8))/32). - _Michael S. Branicky_, Jul 15 2022

G. Bannay, Countdown Problem
Index entries for similar sequences

Cf. A060315, A309886.

def a(n):
    R = dict() # index of each reachable subset is [card(s)-1][s]
    for i in range(n+1): R[i] = dict()
    for i in range(n+1): R[0][(2**i,)] = {2**i}
    reach = set(2**i for i in range(n+1))
    for j in range(1, n+1):
        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 and b%a == 0: allowed.append(b//a)
                                if b != 0 and a%b == 0: allowed.append(a//b)
                                R[len(s12)-1][s12].update(allowed)
                                reach.update(allowed)
    k = 1
    while k in reach: k += 1
    return k
print([a(n) for n in range(6)]) # Michael S. Branicky, Jul 15 2022

a(n) <= A309886(n+1). - Michael S. Branicky, Jul 15 2022

a(8) corrected by Michael S. Branicky, Jul 15 2022

A309885 a(n) is the largest integer k such that there exists a set of n integers from which each number in 1,...,k can be built using the basic operations +,-,*,/, with parentheses allowed, and using each element of the set exactly once.

Original entry on oeis.org

1, 3, 10, 52

Offset: 1

Matej Veselovac, Aug 21 2019

The next term, a(5), is at least 351. Is it true a(5)=351? Proving a value is a term of the sequence is hard. Extensive computations suggest a(5)=351 should be the next term.
Can we find lower bounds for a(6), a(7), ...? For example, a(6) >= 2200 which can be obtained by using the set of integers {2, 10, 13, 30, 49, 56}. Can we find better sets for n=6 ?
By "set of n integers" it is meant that a fixed set of exactly n not necessarily distinct positive integers is used for obtaining every number from 1 to a(n).
This sequence is similar to A142153, but there not all integers from the set must be used when building numbers, and here we are taking a(n) to be the "last obtainable number", instead of the "highest smallest unobtainable" number which is one more than the last obtainable number.
We can use A142153(n+1)-1 > a(n) for a upper bound, for n > 1. For a lower bound, we can use a(n) >= A309886(n)-1, where the inequality is strict for n > 3.
For a trivial, not sharp, upper bound, we can count the possible expressions that can be built with n digits and allowed operations, and find (taking into consideration +,* are commutative): A221954(n) > a(n), for n > 1.

			a(1) = 1 is trivial since binary operations *,+,-,/ are not applicable.
a(2) = 3 since we can make 1,2,3 but not 4, using the number set {1,2}.
a(3) = 10 since we can make 1,...,10 but not 11, using the number set {1,2,4}.
a(4) = 52 since we can make 1,...,52 but not 53, using the number set {2,3,4,22}.
a(5) >= 351 since we can make first 351 numbers using the number set {2,3,6,12,37}.

Math StackExchange, Largest consecutive integer using basic operations and optimal digits?

Cf. A142153, A309886.

Cf. A221954.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions