A275318 A self-dissimilar sequence: each string that occurs earlier is appended with a different term than what follows the previous occurrence.

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

Author

Max Barrentine, Jul 23 2016

Keywords

• nonn

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?

Examples

			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.