cp's OEIS Frontend

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

%I A275318 #13 Jul 29 2016 09:02:44
%S A275318 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,
%T A275318 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,
%U A275318 1,10,9,7,3,5,11,10,8,5,10,7,2,2,0,12,11
%N A275318 A self-dissimilar sequence: each string that occurs earlier is appended with a different term than what follows the previous occurrence.
%C A275318 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.
%C A275318 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).
%C A275318 Does every finite permutation of the nonnegative integers occur in this sequence?
%e A275318 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.
%Y A275318 Cf. A038219.
%K A275318 nonn
%O A275318 1,5
%A A275318 _Max Barrentine_, Jul 23 2016