cp's OEIS Frontend

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.

%I A340131 #73 Sep 25 2021 19:59:45
%S A340131 0,5,11,15,29,33,44,45,50,83,87,98,99,104,116,128,132,135,140,146,150,
%T A340131 245,249,260,261,266,278,290,294,297,302,308,312,332,344,348,377,380,
%U A340131 384,395,396,401,405,410,416,420,434,438,449,450,455,731,735,746,747
%N 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.
%C A340131 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 A340131 As another example, for the integer 52 the balance is broken in the three-digit prefix 122 (the entire ternary code is 1221).
%C A340131 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 A340131 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 A340131 Gennady Eremin, <a href="/A340131/b340131.txt">Table of n, a(n) for n = 1..1000</a>
%H A340131 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 A340131 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 A340131 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 A340131 S(10200[99]) = 10212[104], S(1122000[1188]) = 1122012[1193], etc.
%e A340131 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 A340131 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 A340131 k = 1, S(1002[29]) = 1020[33], the increment is 4*3^0 = 4;
%e A340131 k = 2, S(110022[332]) = 110202[344], the increment is 4*3^1 = 12;
%e A340131 k = 3, S(10110222[2537]) = 10112022[2573], the increment is 4*3^2 = 36;
%e A340131 k = 4, S(111102222[9800]) = 111120222[9908], the increment is 4*3^3 = 108.
%e A340131 There are 5 such group suffixes.
%o A340131 (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 A340131 (Python)
%o A340131 def digits(n, b):
%o A340131   out = []
%o A340131   while n >= b:
%o A340131     out.append(n % b)
%o A340131     n //= b
%o A340131   return [n] + out[::-1]
%o A340131 def ok(n):
%o A340131   t = digits(n, 3)
%o A340131   if t.count(1) != t.count(2): return False
%o A340131   return all(t[:i].count(1) >= t[:i].count(2) for i in range(1, len(t)))
%o A340131 print([n for n in range(750) if ok(n)]) # _Michael S. Branicky_, Dec 29 2020
%Y A340131 Subsequence of A039001.
%Y A340131 Subsequences: A134752, A168607.
%Y A340131 Cf. A244884.
%K A340131 nonn,easy,base
%O A340131 1,2
%A A340131 _Gennady Eremin_, Dec 29 2020