[seqfan] Re: A method to generate sequences
franktaw at netscape.net
franktaw at netscape.net
Tue May 18 16:52:55 CEST 2010
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
More information about the SeqFan
mailing list