A275202 -id:A275202 - cp's OEIS frontend

A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.

1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56, 60, 64, 68, 72, 76, 80, 82, 84, 86, 88, 90, 92, 94, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

a(n) is the subword complexity (or factor complexity) of Thue-Morse sequence A010060, that is, the number of factors of length n in A010060. See Allouche-Shallit (2003). - N. J. A. Sloane, Jul 10 2012

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003. See Problem 10, p. 335. - From N. J. A. Sloane, Jul 10 2012
J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.
A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333-348.
Jakub Konieczny and Clemens Müllner, Arithmetical subword complexity of automatic sequences, arXiv:2309.03180 [math.NT], 2023.
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.
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, and Alexandre P. Francisco, Approximating Optimal Bidirectional Macro Schemes, arXiv:2003.02336 [cs.DS], 2020.

Cf. A005943, A006697, A010060, A275202.

import Data.List (transpose)
a005942 n = a005942_list !! n
a005942_list = 1 : 2 : 4 : 6 : zipWith (+) (drop 6 ts) (drop 5 ts) where
   ts = concat $ transpose [a005942_list, a005942_list]
-- Reinhard Zumkeller, Nov 15 2012

a[0] = 1; a[1] = 2; a[2] = 4; a[3] = 6; a[n_?EvenQ] := a[n] = a[n/2] + a[n/2 + 1]; a[n_?OddQ]  := a[n] = 2*a[(n + 1)/2]; Array[a,60,0] (* Jean-François Alcover, Apr 11 2011 *)

a(n)=if(n<4,2*max(0,n)+(n==0),if(n%2,2*a((n+1)/2),a(n/2)+a(n/2+1)))

a(n) = 2*(A006165(n-1) + n - 1), n > 1.
G.f. (1+x^2)/(1-x)^2 + 2*x^2/(1-x)^2 * Sum_{k>=0} (x^2^(k+1)-x^(3*2^k)). - Ralf Stephan, Jun 04 2003
For n > 2, a(n) = 3*(n-1) + A053646(n-1). - Max Alekseyev, May 15 2011
a(n) = 2*A275202(n-1) for n > 1. - N. J. A. Sloane, Jun 04 2019

Typo in definition corrected by Reinhard Zumkeller, Nov 15 2012

A366462 a(n) is the length of the longest word w in the Period-doubling sequence (A096268) in which every length-n factor of w is unique.

Original entry on oeis.org

2, 4, 7, 9, 11, 15, 17, 19, 21, 23, 25, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161

Offset: 1

Gandhar Joshi, Oct 24 2023

nonn

So far, all the values in the list except the first two are odd numbers.

			For n=3, the length of the longest word in the Period-doubling sequence that admits only unique length-3 factors is a(3) = 7 (attained by word 1000101 and its reversal).

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

Cf. A096268, A275202 (subword complexity).

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

def pdfactoreq "At (t PD[i+t]=PD[j+t]"; % Check if two length-n factors of Period-doubling sequence at positions i and j are equal; PD is predefined in Walnut as the DFA that recognises the Period-doubling sequence. %
def PD_w_len_N_unique_factors "Ei (Aj, k (i<=j & j<(i+n-N) & j ~$pdfactoreq(j, k, N))": % Find lengths of words with length-N unique factors; must replace N with a constant %
def longest_len_N "$PD_w_len_N_unique_factors(n) & Am (m>n) => ~$PD_w_len_N_unique_factors(m)"; % Check the longest of the lengths found in previous line; must replace N with the same constant %

A367184 Starting index in the Period doubling sequence (A096268) of the first maximum length word in which every subword of length n is distinct.

Original entry on oeis.org

0, 0, 1, 0, 5, 2, 1, 0, 11, 10, 9, 4, 3, 2, 1, 0, 23, 22, 21, 20, 19, 18, 17, 8, 7, 6, 5, 4, 3, 2, 1, 0, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80

Offset: 1

Gandhar Joshi, Nov 08 2023

nonn

a(2^m)=0; i.e. for all nonnegative integers m, the longest words w with no length-(2^m) subwords of w repeated are the prefixes of length A366462(2^m) of the Period doubling sequence.

			For n=3, the first instance of one of the longest words w in A096268 with no repeated subwords of length 3 is w=1000101 which begins at index 1, so a(3)=1. The length of w is A366462(3) = 7.

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

Cf. A096268, A366462 (length of the longest word), A275202 (subword complexity).

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

def pdfaceq "At (t PD[i+t]=PD[j+t]"; % Check if two length-n factors of Period doubling sequence at positions i and j are equal; PD is predefined in Walnut as the DFA that recognises the Period doubling sequence. %
def pd_w_len_N_unique_factors "Aj, k (i<=j & j<(i+n-N) & j ~$pdfaceq(j, k, N)": % Find lengths and positions of words with length-N unique factors; must replace N with a constant %
def pd_longest_len_N "$pd_w_len_N_unique_factors(i,n) & Am (m>n) => ~$pd_w_len_N_unique_factors(i,m)"; % Check the longest of the lengths of words defined in the line above; must replace N with the same constant %
def pd_longest_len_N_fpos "$pd_longest_len_N(i,M) & Aj (j ~$pd_longest_len_N(j,M)"; % This finds the first positions of the longest words required; must replace M with A366462(N).%

A318134 Number of periodic sequences of period 3n generated by the random period doubling substitution 0 --> {01, 10}, 1 --> {00}.

Original entry on oeis.org

3, 15, 21, 375, 108, 2427, 402, 176391, 1533, 216030, 10992, 19375935, 24612, 13106514

Offset: 1

Daniel Rust, Aug 18 2018

From an initial seed letter 0, the random substitution iteratively acts on words and outputs all possible outcomes from applying all combinations of the allowed substitution rules independently to each letter in a word. So we have:
0 -->
{01, 10} -->
{0100, 1000, 0001, 0010} -->
{01000101, 01000110, 01001001, 01001010, 10000101, 10000110, 10001001, 10001010, 00010101, 00010110, 00011001, 00011010, 00100101, 00100110, 00101001, 00101010, 01010100, 01011000, 01100100, 01101000, 10010100, 10011000, 10100100, 10101000, 01010001, 01010010, 01100001, 01100010, 10010001, 10010010, 10100001, 10100010} --> ...
An infinite sequence is generated by the random substitution if all subwords of the sequence appear as subwords of some word appearing in the infinite list generated above. Some of these infinite sequences will be periodic and so we can enumerate them.
All periodic sequences have period a multiple of 3.

			The periodic sequences of length 3 generated by the random period doubling substitution have periodic blocks 001, 010, 100.
The periodic sequences of length 6 generated by the random period doubling substitution have periodic blocks 010100, 101000, 010001, 100010, 000101, 001010, 011000, 110000, 100001, 000011, 000110, 001100, 100100, 001001, 010010.

D. Rust, Periodic points in random substitution subshifts, (2018).

Cf. A096268, A275202.

cp's OEIS Frontend

A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A366462 a(n) is the length of the longest word w in the Period-doubling sequence (A096268) in which every length-n factor of w is unique.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Walnut

A367184 Starting index in the Period doubling sequence (A096268) of the first maximum length word in which every subword of length n is distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Walnut

A318134 Number of periodic sequences of period 3n generated by the random period doubling substitution 0 --> {01, 10}, 1 --> {00}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs