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

Author

Gandhar Joshi, Nov 08 2023

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

PARI

\\ See links.

Walnut

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).%