A340131 - OEIS

%I #73 Sep 25 2021 19:59:45

%S 0,5,11,15,29,33,44,45,50,83,87,98,99,104,116,128,132,135,140,146,150,

%T 245,249,260,261,266,278,290,294,297,302,308,312,332,344,348,377,380,

%U 384,395,396,401,405,410,416,420,434,438,449,450,455,731,735,746,747

%N 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.

%C 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.

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

%C 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.

%C 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.

%H Gennady Eremin, <a href="/A340131/b340131.txt">Table of n, a(n) for n = 1..1000</a>

%H Gennady Eremin, <a href="https://arxiv.org/abs/2012.12675">Arithmetization of well-formed parenthesis strings. Motzkin Numbers of the Second Kind</a>, arXiv:2012.12675 [math.CO], 2020.

%e 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).

%e 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,

%e S(10200[99]) = 10212[104], S(1122000[1188]) = 1122012[1193], etc.

%e In this case, the calculation of the subsequent term is reduced to simply replacing the suffix s = 00 with the subsequent suffix s'= 12.

%e 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:

%e k = 1, S(1002[29]) = 1020[33], the increment is 4*3^0 = 4;

%e k = 2, S(110022[332]) = 110202[344], the increment is 4*3^1 = 12;

%e k = 3, S(10110222[2537]) = 10112022[2573], the increment is 4*3^2 = 36;

%e k = 4, S(111102222[9800]) = 111120222[9908], the increment is 4*3^3 = 108.

%e There are 5 such group suffixes.

%o (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

%o (Python)

%o def digits(n, b):

%o   out = []

%o   while n >= b:

%o     out.append(n % b)

%o     n //= b

%o   return [n] + out[::-1]

%o def ok(n):

%o   t = digits(n, 3)

%o   if t.count(1) != t.count(2): return False

%o   return all(t[:i].count(1) >= t[:i].count(2) for i in range(1, len(t)))

%o print([n for n in range(750) if ok(n)]) # _Michael S. Branicky_, Dec 29 2020

%Y Subsequence of A039001.

%Y Subsequences: A134752, A168607.

%Y Cf. A244884.

%K nonn,easy,base

%O 1,2

%A _Gennady Eremin_, Dec 29 2020