[seqfan] Re: A method to generate sequences

[Dmitry Kamenetsky]

Hello Franklin,

Thanks for clearing that up. I completely missed the matrix multiplication
representation. You are right, the only way we can get new/interesting
sequences is if we use non-regular graphs or non-linear functions. I suspect
the latter is the easiest, eg., we can use sums of squares or bitwise
functions (and, or, xor). I am not sure whether the generated sequences will
be useful, but I think it is worth investigating.


Cheers,
Dmitry
 
----------------original message-----------------
From: franktaw at netscape.net
To: seqfan at list.seqfan.eu
Date: Tue, 18 May 2010 10:52:55 -0400
-------------------------------------------------
 
 
> 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
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
>