[seqfan] Re: A method to generate sequences

[franktaw at netscape.net]

This is not really new. You are expressing each value in each 
subsequent vector as a linear combination of terms in the previous 
vector. Hence, what you are really looking at is powers of a matrix. 
There is a fair amount of this in the database. For your case with 3 
nodes, the matrix is:

1 1 0
1 1 1
0 1 1

Regardless of the topology, the resulting sequences will all have 
linear recurrences; equivalently, rational generating functions. I 
think this is also true for regular infinite graphs (where each node 
has only finitely many neighbors, of course). So the most you'll find 
for these cases is an interesting alternative representation for the 
sequence - generally not the most efficient way to calculate it.

One might get something interesting looking at non-regular infinite 
graphs. Consider the graph with nodes labeled by the positive integers, 
where two nodes are adjacent if they differ by a common factor (so 8 
and 12 are adjacent, but not 4 and 12). Starting with 1,0,0,0,..., the 
first column starts:

1,1,2,4,10,28,90,322,1278,5554,26288,134612,742654

which is not in the database. I wonder if the values remain even.

-----
Taking max+1 is always going to wind up with a sequence that just 
increments at each step. You might get something new taking binary xor 
+ 1, but I don't know that it would be interesting.

Franklin T. Adams-Watters

-----Original Message-----
From: Dmitry Kamenetsky <dmitry.kamenetsky at rsise.anu.edu.au>

Hello all,

I have been looking at cellular automata recently. In particular, I 
found a
method (perhaps new?) that generates some interesting sequences. For 
example
you begin with 3 cells (x,y,z). At each iteration every cell transforms 
to
itself plus all its neighbours. So (x,y,z) becomes (x+y, x+y+z, y+z). 
For
example if we start with (1,0,0) we obtain the following:

(1,1,0)
(2,2,1)
(4,5,3)
(9,12,8)
(21,29,20)
(50,70,49)
(120,169,119)
(289,408,288)
(697,985,696)

Numbers in the first column seem to form A171842, those in the second 
form
the Pell numbers (A000129) and the third column seem to form A048739. 
If you
start with (0,1,0) then the second column forms A001333. You can also 
use a
different number of starting cells. For example, if you start with 
(1,0,0,0)
then the columns seem to form A005207, A051450, A094292, A056014
respectively. If you have an infinite number of cells, ie (1,0,...,0) 
then
the first column generates the Motzkin numbers (A001006). Furthermore, 
we
can use any other arbitrary transformation rule, eg. each cell 
transforms to
the maximum of all its neighbours plus one. We can also use arbitrary 
cell
topologies, such as grids (with 4 or 8 neighbourhood system), triangular
lattices, hexagonal lattices and so on.

I am wondering whether this method is new? If it is new then perhaps it 
can
be used to generate new interesting sequences, or generate old sequences
more efficiently?


Sincerely,
Dmitry Kamenetsky