[seqfan] new sequences from old

[David Newman]

I'm passing along this letter from Moshe Newman describing a method of
generating new sequences from old.

this is a general method of getting new sequences from old, provided
the old sequence is a permutation of the natural numbers.

in general, if a(n) is a sequence with no repeated values, there must
exist a shift function shift(x) with the property that

shift( a(n) ) = a(n+1).   in general you can have many different such
functions, since the property that defines the shift function only
cares about its values at a(n)s.

however, if a(n) is a permutation of the natural numbers, then its
shift is unique, well defined, on the natural numbers. to be explicit,
if b(n) is the inverse permutation of
a(n), so that b(a(n)) = a(b(n)) = n, we have

shift(n) = a( b(n) + 1).

to give one explicit example, if a(n) is the greedy queens sequence:
1, 3, 5, 2, 4, 9, ...
                                         and  b(n) is the inverse
permutation         : 1, 4, 2, 5, 3, 10, ...

then the shift sequence comes out to be : 3, 4, 5, 9, 2, 8, 22, ...

you could propose this for a particular sequence, and suggest to the
sequence fans that they go about systematically adding these to the
database. if you need a motive for putting these in, point out the
obvious: if by some miracle you can compute the shift of a sequence
easily, then you can compute the sequence easily by using recursion.
you can compute a(n+1) just by knowing a(n), without even knowing what
n is.

comment: the shift function is very nearly a permutation itself,
except that the value a(1) does not appear in the image.

of course, if a nonperiodic sequence has repeated values, then it
can't have a shift function. even so, it is possible that no
consecutive pair repeats, that is to say the pair of numbers ( a(n),
a(n+1) )   is not equal to the pair of numbers  ( a(m), a(m+1) ),
unless of course m=n.  in this case there is two-variable shift
function, such that

shift ( a(n), a(n+1) ) = a(n+2).

even if the sequence has no repeated elements, you still might want a
two-variable shift function, which may be much simpler that the
one-variable shift. see eg the fibonacci sequence.

of course, you know i have a fondness for this sort of problem, having
had one spectacular success in finding shift functions. in general, to
be sure, there is nothing nice to find.