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.

1, 3, 10, 52

Offset: 1

Author

Matej Veselovac, Aug 21 2019

Keywords

• nonn
• hard
• more

Comments

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.

Examples

			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}.
		

Links

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

Crossrefs

Cf. A142153, A309886.

Cf. A221954.