[seqfan] new sequences from old

David Newman davidsnewman at gmail.com
Thu Jan 4 20:40:22 CET 2018

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.

More information about the SeqFan mailing list