A288350 Lexically smallest string of n digits from 1...9, such that no formula using the single digits in the given order exists that evaluates to 0.

1, 12, 124, 1251, 12721, 169896, 8985898

Offset

1,2

Comments

The formula may use any combination of the four binary operators +, -, *, /, the unary minus and parentheses. All digits have to be used exactly once and in the given order. Concatenation of the digits is not allowed. 0/0 in the evaluation of expressions makes the result invalid.

The last term a(7)=8985898, which is the only string of 7 digits for which it is not possible to construct an expression with result 0, is conjectured to be the last sequence term, i.e. for all strings of 8 or more digits expressions with result 0 can be found.

The conjecture is almost trivially true. Since 8985898 is the only exception for strings of 7 digits, an 8 digit string containing 8985898 can only be of the form x8985898 or 8985898x. But since any of x898589 and 985898x /= 8985898 leads to a 7 digit string that can represent 0, one can always find a substring of length 7 representing 0 in a string of 8 or more digits. Therefore the sequence ends at a(7).

Links

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

IBM Research, Ponder This Challenge - June 2017, related problem for 7-digit numbers.

Example

a(3)=124: For all numbers starting with 11.. the formula can be chosen as (1-1)*..,
121: 1-2+1=0, 122: (1-2/2)=0, 123: 1+2-3=0, 124: 0 cannot by obtained by any valid formula.

Crossrefs

Cf. A000108 (number of ways to insert the parentheses), A181898, A288351, A288353, A288354, A288355, A288356.

Sequence in context: A332690 A016134 A045507 * A331396 A209041 A155595

Adjacent sequences: A288347 A288348 A288349 * A288351 A288352 A288353

Keyword

nonn,base,fini,full

Author

Hugo Pfoertner, Jun 08 2017

Status

approved