A340131 Numbers whose ternary expansions have the same number of 1's and 2's and, in each prefix (initial fragment), at least as many 1's as 2's.

0, 5, 11, 15, 29, 33, 44, 45, 50, 83, 87, 98, 99, 104, 116, 128, 132, 135, 140, 146, 150, 245, 249, 260, 261, 266, 278, 290, 294, 297, 302, 308, 312, 332, 344, 348, 377, 380, 384, 395, 396, 401, 405, 410, 416, 420, 434, 438, 449, 450, 455, 731, 735, 746, 747

Offset

1,2

Comments

For a nonzero term, the ternary code starts with 1, otherwise the balance of 1's and 2's is broken already in the one-digit prefix. Therefore 7, 19, 21, etc. (see A039001) are not terms.

As another example, for the integer 52 the balance is broken in the three-digit prefix 122 (the entire ternary code is 1221).

Each term with a ternary code of length k corresponds one-to-one to the Motzkin path of length k that starts with an up step. Therefore, the terms can be called digitized Motzkin paths.

The number of terms with a ternary code of length k is equal to A244884(k). Example: five terms 29, 33, 44, 45 and 50 have a ternary length of 4, respectively A244884(4)=5.

Links

Gennady Eremin, Table of n, a(n) for n = 1..1000

Gennady Eremin, Arithmetization of well-formed parenthesis strings. Motzkin Numbers of the Second Kind, arXiv:2012.12675 [math.CO], 2020.

Example

The first terms 0 and 5 are obvious, because the four intermediate ternary codes 1, 2, 10[3], and 11[4] are rejected due to a violation of the balance of 1's and 2's. Next, the successor function S works: for any term x, the next term is S(x).
Iterating over numbers is inefficient; code suffixes (final digits) can be processed faster. The transition from 0 to 12[5] is generalized for terms that are multiples of 9. For example,
S(10200[99]) = 10212[104], S(1122000[1188]) = 1122012[1193], etc.
In this case, the calculation of the subsequent term is reduced to simply replacing the suffix s = 00 with the subsequent suffix s'= 12.
Another common suffix is s = 02..2 = 02^k (twos are repeated at the end of the ternary code). Then the subsequent suffix is s'= 202..2 = 202^(k-1), i.e., within such a suffix, the first two digits are reversed. Here are some examples:
k = 1, S(1002[29]) = 1020[33], the increment is 4*3^0 = 4;
k = 2, S(110022[332]) = 110202[344], the increment is 4*3^1 = 12;
k = 3, S(10110222[2537]) = 10112022[2573], the increment is 4*3^2 = 36;
k = 4, S(111102222[9800]) = 111120222[9908], the increment is 4*3^3 = 108.
There are 5 such group suffixes.

Prog

(PARI) is(n) = {my(d = digits(n, 3), v = [0, 0]); for(i = 1, #d, if(d[i] > 0, v[d[i]]++); if(v[1] < v[2], return(0))); v[1] == v[2] } \\ David A. Corneth, Dec 29 2020
(Python)
def digits(n, b):
  out = []
  while n >= b:
    out.append(n % b)
    n //= b
  return [n] + out[::-1]
def ok(n):
  t = digits(n, 3)
  if t.count(1) != t.count(2): return False
  return all(t[:i].count(1) >= t[:i].count(2) for i in range(1, len(t)))
print([n for n in range(750) if ok(n)]) # Michael S. Branicky, Dec 29 2020

Crossrefs

Subsequence of A039001.

Subsequences: A134752, A168607.

Cf. A244884.

Sequence in context: A314079 A372113 A137009 * A290199 A034905 A031153

Adjacent sequences: A340128 A340129 A340130 * A340132 A340133 A340134

Keyword

nonn,easy,base

Author

Gennady Eremin, Dec 29 2020

Status

approved