A005942 -id:A005942 - cp's OEIS frontend

A366408 Starting index in the Thue-Morse sequence (A010060) of the first maximum length block in which every subword of length n is distinct.

0, 4, 0, 7, 0, 3, 14, 13, 0, 7, 6, 5, 28, 27, 26, 25, 0, 15, 14, 13, 12, 11, 10, 9, 56, 55, 54, 53, 52, 51, 50, 49, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 0, 63

Offset: 1

Kevin Ryde, Oct 10 2023

nonn

This maximum length is A365624(n).

For n=1 and n = 2^k + 1 >= 3, a(n) = 0 since in those cases A005942(n) + n-1 = A334227(n) shows the Thue-Morse sequence starts with all possible subwords of length n without duplication.

			For n=2, the Thue-Morse sequence and the block sought are
  t            = 0 1 2 3 4 5 6 7 8
  ThueMorse(t) = 0 1 1 0 1 0 0 1 1  (A010060)
                         \-------/
In the block of terms starting at t = a(2) = 4 and length A365624(2) = 5, every subword of length n=2 is distinct (10, 00, 01, 11).

Kevin Ryde, Table of n, a(n) for n = 1..8192
Kevin Ryde, PARI/GP Code

Cf. A010060, A365624, A005942, A334227.

PARI
```
\\ See links.
```

A080776 Oscillating sequence which rises to 2^(k-1) in k-th segment (k>=1) then falls back to 0.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 31, 30

Offset: 0

N. J. A. Sloane, Mar 11 2003

nonn

k-th segment has length 2^k (k>=0).

Hsien-Kuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also 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

R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Essentially the same as A053646.

G.f.: -1 + 2/(1-x) + 1/(1-x)^2 * (-1 + sum(k>=0, 2t^2(t-1), t=x^2^k)). a(n) = A005942(n+2) - 3(n+1), n>0. - Ralf Stephan, Sep 13 2003

a(0)=0, a(2n) = a(n) + a(n-1) + (n==1), a(2n+1) = 2a(n). - Ralf Stephan, Oct 20 2003

A297531 Subword complexity (number of distinct blocks) of length n occurring in the "twisted" Thue-Morse sequence.

Original entry on oeis.org

1, 2, 4, 6, 10, 13, 17, 21, 24, 26, 30, 34, 38, 42, 45, 48, 50, 52, 56, 60, 64, 68, 72, 76, 80, 84, 87, 90, 93, 96, 98, 100, 102, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 171, 174, 177, 180, 183, 186, 189, 192, 194, 196, 198, 200, 202, 204, 206, 208, 212, 216, 220, 224, 228, 232, 236, 240

Offset: 0

Jeffrey Shallit, Dec 31 2017

nonn

The "twisted" Thue-Morse sequence 00100110100... is the one given in A059448, but prefixed with 0. It is the image, under the map sending 0, 2 -> 0 and 1 -> 1 of the fixed point, starting with 0, of the morphism 0 -> 02, 1 -> 21, 2 -> 12.

This sequence has the maximum possible subword complexity over all binary overlap-free words.

			For n=3 we have a(3) = 6, corresponding to the blocks 001, 010, 100, 011, 110, 101.

Cf. A005942, which enumerates the same thing for the ordinary Thue-Morse sequence A010060.

For n >= 4 we have a(n+1) =
4n - 3*2^{i-2} for 2^i <= n <= 3*2^{i-1};
3n + 3*2^{i-2} for 3*2^{i-1} <= n <= 7*2^{i-2};
2n + 5*2^{i-1} for 7*2^{i-2} <= n <= 2^{i+1}.

A373700 Number of distinct length-n blocks in the Thue-Morse sequence (A010060), counted up to reversal.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 10, 10, 13, 12, 16, 16, 20, 20, 22, 22, 24, 24, 28, 28, 32, 32, 36, 36, 40, 40, 43, 42, 45, 44, 47, 46, 49, 48, 52, 52, 56, 56, 60, 60, 64, 64, 68, 68, 72, 72, 76, 76, 80, 80, 82, 82, 84, 84, 86, 86, 88, 88, 90, 90, 92, 92, 94, 94, 96, 96, 100

Offset: 0

Jeffrey Shallit, Jun 14 2024

By "counted up to reversal" we mean two blocks, one of which is the reversal of the other, are only counted as one.

			For n = 5, the 6 blocks are 01101, 01001, 00110, 00101, 01011, 11001, and their reversals.

Jean-Paul Allouche, John M. Campbell, Jeffrey Shallit, and Manon Stipulanti, The reflection complexity of sequences over finite alphabets, Arxiv preprint arXiv:2406:09302 [math.CO], June 13 2024.

Cf. A010060, A005942 (all blocks), A159782 (palindromes).

cp's OEIS Frontend

A366408 Starting index in the Thue-Morse sequence (A010060) of the first maximum length block in which every subword of length n is distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A080776 Oscillating sequence which rises to 2^(k-1) in k-th segment (k>=1) then falls back to 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A297531 Subword complexity (number of distinct blocks) of length n occurring in the "twisted" Thue-Morse sequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A373700 Number of distinct length-n blocks in the Thue-Morse sequence (A010060), counted up to reversal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs