login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.
(Formerly M1007)
12

%I M1007

%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) = subword complexity (or factor complexity) of Thue-Morse sequence A010060 = 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 S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math., 24 (1989), 83-96. doi:10.1016/0166-218X(92)90274-E

%D De Luca, Aldo; Varricchio, Stefano; Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), no. 3, 333-348. doi:10.1016/0304-3975(89)90013-3

%D Hsien-Kuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also 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

%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>

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

%F G.f. (1+x^2)/(1-x)^2 + 2x^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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:19 EDT 2020. Contains 333104 sequences. (Running on oeis4.)