A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2. (Formerly M1007)

1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56, 60, 64, 68, 72, 76, 80, 82, 84, 86, 88, 90, 92, 94, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182

Offset

0,2

Comments

a(n) is the subword complexity (or factor complexity) of Thue-Morse sequence A010060, that is, the number of factors of length n in A010060. See Allouche-Shallit (2003). - N. J. A. Sloane, Jul 10 2012

References

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003. See Problem 10, p. 335. - From N. J. A. Sloane, Jul 10 2012

J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n = 0..1000

S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.

A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333-348.

Jakub Konieczny and Clemens Müllner, Arithmetical subword complexity of automatic sequences, arXiv:2309.03180 [math.NT], 2023.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, and Alexandre P. Francisco, Approximating Optimal Bidirectional Macro Schemes, arXiv:2003.02336 [cs.DS], 2020.

Formula

a(n) = 2*(A006165(n-1) + n - 1), n > 1.

G.f. (1+x^2)/(1-x)^2 + 2*x^2/(1-x)^2 * Sum_{k>=0} (x^2^(k+1)-x^(3*2^k)). - Ralf Stephan, Jun 04 2003

For n > 2, a(n) = 3*(n-1) + A053646(n-1). - Max Alekseyev, May 15 2011

a(n) = 2*A275202(n-1) for n > 1. - N. J. A. Sloane, Jun 04 2019

Mathematica

a[0] = 1; a[1] = 2; a[2] = 4; a[3] = 6; a[n_?EvenQ] := a[n] = a[n/2] + a[n/2 + 1]; a[n_?OddQ]  := a[n] = 2*a[(n + 1)/2]; Array[a, 60, 0] (* Jean-François Alcover, Apr 11 2011 *)

Prog

(PARI) a(n)=if(n<4, 2*max(0, n)+(n==0), if(n%2, 2*a((n+1)/2), a(n/2)+a(n/2+1)))
(Haskell)
import Data.List (transpose)
a005942 n = a005942_list !! n
a005942_list = 1 : 2 : 4 : 6 : zipWith (+) (drop 6 ts) (drop 5 ts) where
   ts = concat $ transpose [a005942_list, a005942_list]
-- Reinhard Zumkeller, Nov 15 2012

Crossrefs

Cf. A005943, A006697, A010060, A275202.

Sequence in context: A178539 A072752 A036634 * A024907 A033098 A220478

Adjacent sequences: A005939 A005940 A005941 * A005943 A005944 A005945

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Jeffrey Shallit

Extensions

Typo in definition corrected by Reinhard Zumkeller, Nov 15 2012

Status

approved