login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268. 5
2, 3, 5, 6, 8, 10, 11, 12, 14, 16, 18, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 161, 162, 163, 164, 165 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
LINKS
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
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.
FORMULA
a(n) = A005942(n+1)/2, and the latter satisfies a simple recurrence. - N. J. A. Sloane, Jun 04 2019
Proof: let b(n) = A096268(n) and c(n) = b(2n+1). For n >= 2, distinct blocks of length 2n are of the form 0_0_...0_ or _0_0..._0, and distinct blocks of length 2n-1 are of the form 0_0_..._0 or _0_0...0_. Therefore, a(2n) is twice the n-subword complexity of {c(k)}, and a(2n-1) is the sum of (n-1)-subword complexity and n-subword complexity of {c(k)}. Note that n-subword complexity of {c(k)} is a(n) because c(2k) = b(4k+1) = 1, c(4k+1) = b(8k+3) = b(2k) = 0 and c(4k+3) = b(8k+7) = b(2k+1) = c(k). In conclusion, a(2n) = 2a(n) and a(2n-1) = a(n-1) + a(n), with a(1) = 2 and a(2) = 3. So a(n) = A005942(n+1)/2. - Jinyuan Wang, Feb 27 2020
EXAMPLE
For n = 1 there are two words {0,1}.
For n = 2 there are three words {00,01,10}.
For n = 3 there are five words {000,001,010,100,101}.
MAPLE
a := proc(n) option remember; if n = 1 then 2 elif n = 2 then 3 else a(iquo(n, 2)) + a(iquo(n+1, 2)) end if; end proc:
seq(a(n), n = 1..100); # Peter Bala, Aug 05 2022
MATHEMATICA
t = Nest[Flatten[# /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 12]; Table[2^n - Count[SequencePosition[t, #] & /@ Tuples[{0, 1}, n], {}], {n, 16}] (* Michael De Vlieger, Jul 19 2016, Version 10.1, after Robert G. Wilson v at A096268 *)
PROG
(PARI) lista(nn) = {my(v=vector(nn-nn%2)); v[1]=2; v[2]=3; for(n=2, nn\2, v[2*n-1]=v[n-1]+v[n]; v[2*n]=2*v[n]); v; } \\ Jinyuan Wang, Feb 27 2020
(PARI) a(n) = my(k=logint(n, 2)-1); if(bittest(n, k), n + 2<<k, n<<1 - 1<<k); \\ Kevin Ryde, Aug 09 2022
CROSSREFS
Sequence in context: A024609 A167056 A131614 * A233592 A320773 A138390
KEYWORD
nonn,easy
AUTHOR
Daniel Rust, Jul 19 2016
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 02:09 EDT 2024. Contains 374575 sequences. (Running on oeis4.)