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

Links

Table of n, a(n) for n=1..85.

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

Adjacent sequences: A275315 A275316 A275317 * A275319 A275320 A275321

Keyword

nonn

Author

Max Barrentine, Jul 23 2016

Status

approved