|
%I M1007 #68 Sep 10 2023 01:54:25
%S 1,2,4,6,10,12,16,20,22,24,28,32,36,40,42,44,46,48,52,56,60,64,68,72,
%T 76,80,82,84,86,88,90,92,94,96,100,104,108,112,116,120,124,128,132,
%U 136,140,144,148,152,156,160,162,164,166,168,170,172,174,176,178,180,182
%N a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.
%C 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
%D 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
%D J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.
%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005942/b005942.txt">Table of n, a(n) for n = 0..1000</a>
%H S. Brlek, <a href="http://dx.doi.org/10.1016/0166-218X(92)90274-E">Enumeration of factors in the Thue-Morse word</a>, Discrete Applied Math. 24 (1989), 83-96.
%H A. de Luca and S. Varricchio, <a href="https://doi.org/10.1016/0304-3975(89)90013-3">Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups</a>, Theoret. Comput. Sci. 63 (1989), 333-348.
%H Jakub Konieczny and Clemens Müllner, <a href="https://arxiv.org/abs/2309.03180">Arithmetical subword complexity of automatic sequences</a>, arXiv:2309.03180 [math.NT], 2023.
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, and Alexandre P. Francisco, <a href="https://arxiv.org/abs/2003.02336">Approximating Optimal Bidirectional Macro Schemes</a>, arXiv:2003.02336 [cs.DS], 2020.
%F a(n) = 2*(A006165(n-1) + n - 1), n > 1.
%F 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
%F For n > 2, a(n) = 3*(n-1) + A053646(n-1). - _Max Alekseyev_, May 15 2011
%F a(n) = 2*A275202(n-1) for n > 1. - _N. J. A. Sloane_, Jun 04 2019
%t 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 *)
%o (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)))
%o (Haskell)
%o import Data.List (transpose)
%o a005942 n = a005942_list !! n
%o a005942_list = 1 : 2 : 4 : 6 : zipWith (+) (drop 6 ts) (drop 5 ts) where
%o ts = concat $ transpose [a005942_list, a005942_list]
%o -- _Reinhard Zumkeller_, Nov 15 2012
%Y Cf. A005943, A006697, A010060, A275202.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_, _Jeffrey Shallit_
%E Typo in definition corrected by _Reinhard Zumkeller_, Nov 15 2012
|
