derivative of n

[Jeffrey Shallit]

> 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/