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

Author

Gennady Eremin, Dec 29 2020

Keywords

• nonn
• easy
• base

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.

Examples

			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.
		

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.

Crossrefs

Subsequence of A039001.

Subsequences: A134752, A168607.

Cf. A244884.

Programs

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