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

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,5

Comments

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.

Links

Kevin Ryde, Table of n, a(n) for n = 1..8192

Kevin Ryde, PARI/GP Code

Example

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.

Prog

(Walnut)
def pdfaceq "At (t<n) => 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<k & k<(i+n-N+1)) => ~$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<i) => ~$pd_longest_len_N(j, M)"; % This finds the first positions of the longest words required; must replace M with A366462(N).%
(PARI) \\ See links.

Crossrefs

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

Sequence in context: A303127 A106266 A334367 * A370915 A326327 A113103

Adjacent sequences: A367181 A367182 A367183 * A367185 A367186 A367187

Keyword

nonn,changed

Author

Gandhar Joshi, Nov 08 2023

Status

approved