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)
12
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 (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

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

Presumably a(n) = 2*A275202(n) for n>0. - 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. A010060, A005943, A006697, 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

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 October 19 13:01 EDT 2019. Contains 328222 sequences. (Running on oeis4.)