login
This site is supported by donations to The OEIS 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>3.
(Formerly M1007)
11
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) = subword 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

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.

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

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

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

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

FORMULA

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

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

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

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. A010060, A005943, A006697.

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 fixed by Reinhard Zumkeller, Nov 15 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 04:37 EDT 2018. Contains 316378 sequences. (Running on oeis4.)