OFFSET
1
COMMENTS
A cubefree word.
A generalized choral sequence c(3n+r_0)=0, c(3n+r_1)=1, c(3n+r_c)=c(n), with r_0=0, r_1=1, and r_c=2. - Joel Reyes Noche (joel.noche(AT)up.edu.ph), Jul 09 2009
From Joerg Arndt, Apr 15 2010: (Start)
Turns (by 120 degrees) of the terdragon curve which can be rendered as follows:
[Init] Set n=0 and direction=0.
[Draw] Draw a unit line (in the current direction). Turn left/right if a(n) is zero/nonzero respectively.
[Next] Set n=n+1 and goto (draw).
See fxtbook link below.
(End)
REFERENCES
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
J. R. Noche, Generalized Choral Sequences, Matimyas Matematika, 31(2008), 25-28. [From Joel Reyes Noche (joel.noche(AT)up.edu.ph), Jul 09 2009]
LINKS
Joerg Arndt Matters Computational (The Fxtbook), section 1.31.4, pp. 92-95; dragon curve picture on p. 93.
Jean Berstel, Home Page
Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, Arithmetic Self-Similarity of Infinite Sequences, arXiv preprint 1201.3786 [math.CO], 2012.
FORMULA
a(n) = (A062756(n) - A062756(n+1) + 1)/2, where A062756(n) is the number of 1's in the ternary expansion of n. From formula in A062756: g.f.: A(x) = 1/(1-x)/2 - Sum_{k>=0} x^(3^k-1)/(1+x^(3^k)+x^(2*3^k))/2. - Paul D. Hanna, Feb 24 2006
Given g.f. A(x) then B(x) = x * A(x) satisfies B(x) = x^2 / (1 - x^3) + B(x^3). - Michael Somos, Jul 29 2009
a(3*n) = 0, a(3*n + 1) = 1, a(3*n - 1) = a(n - 1). - Michael Somos, Jul 29 2009
a(n) = -1 + A060236(n). - Joerg Arndt, Jan 21 2013
EXAMPLE
Start: 0
Rules:
0 --> 010
1 --> 011
-------------
0: (#=1)
0
1: (#=3)
010
2: (#=9)
010011010
3: (#=27)
010011010010011011010011010
4: (#=81)
010011010010011011010011010010011010010011011010011011010011010010011011010011010
MAPLE
a:= proc(n) option remember; local m, r;
r:= irem(n, 3, 'm');
`if`(r<2, r, a(m))
end:
seq(a(n), n=0..1000);
MATHEMATICA
Nest[Flatten[ # /. {0 -> {0, 1, 0}, 1 -> {0, 1, 1}}] &, {0}, 5]
PROG
(PARI) {a(n)=if(n<1, 0, polcoeff(1/(1-x)/2-sum(k=0, ceil(log(n+1)/log(3)), x^(3^k-1)/(1+x^(3^k)+x^(2*3^k)+x*O(x^n)))/2, n))} \\ Paul D. Hanna, Feb 24 2006
(PARI) {a(n) = if( n<1, 0, n++; n / 3^valuation(n, 3) % 3 -1 )} /* Michael Somos, Jul 29 2009 */
(C++) /* CAT algorithm */
bool bit_dragon3_turn(ulong &x)
/* Increment the radix-3 word x and return whether
the number of ones in x is decreased. */
{
ulong s = 0;
while ( (x & 3) == 2 ) { x >>= 2; ++s; } /* scan over nines */
bool tr = ( (x & 3) != 0 ); /* incremented word will have one less 1 */
++x; /* increment next digit */
x <<= (s<<1); /* shift back */
return tr;
} /* Joerg Arndt, Apr 15 2010 */
CROSSREFS
Cf. A189628 (guide).
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Mar 29 2003
EXTENSIONS
More terms from Wouter Meeussen, Apr 01 2003
STATUS
approved