

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



FORMULA

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 2n1 are of the form 0_0_..._0 or _0_0...0_. Therefore, a(2n) is twice the nsubword complexity of {c(k)}, and a(2n1) is the sum of (n1)subword complexity and nsubword complexity of {c(k)}. Note that nsubword 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(2n1) = a(n1) + 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:


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(nnnn%2)); v[1]=2; v[2]=3; for(n=2, nn\2, v[2*n1]=v[n1]+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



STATUS

approved



