derivative of n
Jeffrey Shallit
shallit at graceland.uwaterloo.ca
Mon Jul 13 13:19:56 CEST 1998
> But, actually, aren't these a subclass of one-dimensional cellular automata
> (some even with so-called "totalistic" rules, no less)?
>
> >The derivative of a binary sequence is obtained by adding the bits
> >in pairs: the derivative of 1 1 1 0 1 0 0 0 1 1 is
> > 0 0 1 1 1 0 0 1 0
>
> That is, approximately N XOR (N shift 1) right?
>
> >The periodic derivative includes the sum of the last bits:
> >1 1 1 0 1 0 0 0 1 0 has periodic derivative
> >0 0 1 1 1 0 0 1 1 1
>
> That is, substituting "rotate" for "shift" in the above expression, where
> the "word width" is defined by the MSB of N, right?
>
> This just inspired me to submit the even simpler
> 0, 1, 1, 3, 2, 6, 3, 7, 4, 12, 5, 13, 6, 14, 7, 15, 8, 24, 9, 25, 10, 26,...
> that is, N rotated 1 place right. I was surpised that this was missing!
> It's "dual", rotate left, is A6257 (NJAS: could you cross link this with
> the above new sequence?)
This sequence, as well as many of the ones recently discussed on this list,
have the property that they are "2-regular". That is, if (a(n))_{n >= 0}
is the sequence, then one considers the subsequences forming the "2-kernel":
(a(n))
(a(2n))
(a(2n+1))
(a(4n))
(a(4n+1))
(a(4n+2))
(a(4n+3))
...
If there is a finite set S of sequences such that each of the above
can be written as a linear combination of the members of S, then (a(n))
is said to be 2-regular. One of the simplest examples is s_2 (n), the
sum of the base-2 digits of n. This sequence satisfies
s_2 (2n) = s_2 (n)
s_2 (2n+1) = s_2 (n) +1
which means that all the sequences in the 2-kernel of (s_2(n)) can be
written as a linear combination of (s_2 (n)) and (1,1,1,1,...).
Allouche and I wrote a paper giving dozens of examples of such
sequences from the literature (Theor. Comput. Sci. 98 (1992),
163-197) in which the most interesting result is that the
class of such sequences is closed under addition, multiplication, and
convolution.
There is an evident generalization to k-regular for k >= 2.
Jeffrey Shallit, Computer Science, University of Waterloo,
Waterloo, Ontario N2L 3G1 Canada shallit at graceland.uwaterloo.ca
URL = http://math.uwaterloo.ca/~shallit/
More information about the SeqFan
mailing list