# Neighborly Sequences

In an arithmetic sequence --- for example, 1, 4, 7, 10, 13, 16, 19 ... --- each number is the arithmetic mean of its neighbors. (In fact, it is the arithmetic mean of all of its N predecessors and N successors.)

In a geometric sequence (1, 4, 16, 64, 256, ...) each number is the geometric mean of its neighbors. And again this can be expanded to the N closest neighbors.

What other "aggregate" functions can produce sequences of this sort? For example, "max()" and "min()" produce only the constant sequences.

The "mex" function (minimum excluded number) produces a cyclic sequence, but cannot be expanded from one neighbor to multiple neighbors. For example,

mex( 0 ) = 1
mex( 0, 1 ) = 2
mex( 1, 2 ) = 0

produces the sequence 0, 1, 2, 0, 1, 2, .... Taking two neighbors produces the same sequence, a promising start!

mex( 0, 1, 0, 1 ) = 2
mex( 1, 2, 1, 2 ) = 0
mex( 2, 0, 2, 0 ) = 1

But mex( 0, 1, 2, 1, 2, 0 ) = 3. In fact I think we could show that 0, 1, 2 repeating and 0, 2, 1 repeating are the only possible mex-based sequences.

How about 'median'? Or '90th percentile'? Median works fine for any increasing sequence, if you include the number itself.

In general, what conditions on F: 2N -> N are necessary and sufficient so that a sequence s0, s1, s2, s3, ... exists with F( sn-k, sn-k+1, ..., sn, sn+1, ..., sn+k ) = sn? What if we require the sequence to be nonrepeating?
Tags:
• Post a new comment

#### Error

default userpic