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.
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
KEYWORD
nonn,easy,base
AUTHOR
Gennady Eremin, Dec 29 2020
STATUS
approved