Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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: geek, mathematics
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments