OFFSET
1,1
LINKS
Jinyuan Wang, Table of n, a(n) for n = 1..1000
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 the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
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
KEYWORD
nonn,easy
AUTHOR
Daniel Rust, Jul 19 2016
STATUS
approved