A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.
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
Offset: 1
Examples
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}.
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.
Programs
-
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 *) -
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<
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