login
A275318
A self-dissimilar sequence: each string that occurs earlier is appended with a different term than what follows the previous occurrence.
0
0, 1, 0, 0, 2, 1, 3, 2, 0, 1, 4, 3, 1, 3, 1, 2, 5, 4, 2, 4, 1, 1, 0, 6, 5, 3, 0, 5, 2, 3, 7, 6, 4, 0, 4, 8, 7, 5, 1, 9, 8, 6, 3, 6, 2, 2, 1, 2, 4, 0, 3, 5, 0, 2, 0, 0, 1, 3, 0, 4, 7, 4, 6, 1, 2, 3, 6, 1, 1, 10, 9, 7, 3, 5, 11, 10, 8, 5, 10, 7, 2, 2, 0, 12, 11
OFFSET
1,5
COMMENTS
Each successive term of this sequence is chosen by finding the longest suffix of the sequence that occurs earlier in the sequence, and subtracting 1 from the term that follows the most recent occurrence (the empty set is a suffix and a prefix of every string). If the following term is 0, then the new term is the smallest number that has not yet occurred in the sequence.
Unlike the related Ehrenfeucht-Mycielski sequence (A038219), the present sequence has some predictable structure. The first occurrence of a term a(n)=k is always followed by a(n+1)=k-1, and it appears that for large values of k, it tends to be the case that a(n+2)=k-3, a(n+3)=k-6... a(n+m)=k-T(m).
Does every finite permutation of the nonnegative integers occur in this sequence?
EXAMPLE
The initial term is 0. The largest suffix that occurs earlier is the empty set followed by 0, so the next term is 1, the smallest number that has not yet occurred. The largest suffix that occurs earlier is the empty set, followed by 1, so the next term is 1-1=0. The largest suffix that occurs earlier is 0, followed by 1, so the next term is 1-1=0.
CROSSREFS
Cf. A038219.
Sequence in context: A227860 A020779 A260721 * A190431 A325178 A333452
KEYWORD
nonn
AUTHOR
Max Barrentine, Jul 23 2016
STATUS
approved