cp's OEIS Frontend

A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.

%I A275202 #35 Aug 09 2022 07:05:59
%S A275202 2,3,5,6,8,10,11,12,14,16,18,20,21,22,23,24,26,28,30,32,34,36,38,40,
%T A275202 41,42,43,44,45,46,47,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,
%U A275202 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
%N A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.
%H A275202 Jinyuan Wang, <a href="/A275202/b275202.txt">Table of n, a(n) for n = 1..1000</a>
%H A275202 Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A275202 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016.
%H A275202 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%F A275202 a(n) = A005942(n+1)/2, and the latter satisfies a simple recurrence. - _N. J. A. Sloane_, Jun 04 2019
%F A275202 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
%e A275202 For n = 1 there are two words {0,1}.
%e A275202 For n = 2 there are three words {00,01,10}.
%e A275202 For n = 3 there are five words {000,001,010,100,101}.
%p A275202 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:
%p A275202 seq(a(n), n = 1..100); # _Peter Bala_, Aug 05 2022
%t A275202 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 *)
%o A275202 (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
%o A275202 (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
%Y A275202 Cf. A006165, A096268, A035263, A005942.
%K A275202 nonn,easy
%O A275202 1,1
%A A275202 _Daniel Rust_, Jul 19 2016