[seqfan] Re: new sequences from old

[Antti Karttunen]

>
> Message: 24
> Date: Thu, 4 Jan 2018 14:40:22 -0500
> From: David Newman <davidsnewman at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] new sequences from old
> Message-ID:
>         <CAEsMqd80p8aTX4vZL-DtEVyBTyRPeQ2o-4outpC1YdaPJjo0MQ at mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> 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, ...
>
...
> comment: the shift function is very nearly a permutation itself,
> except that the value a(1) does not appear in the image.

At least if a(1) = 1, then the shift-sequence can be made a
permutation with a simple trick:
Define shift(1) = a(1) = 1, and for n > 1, shift(n) = a(b(n-1) +1).
That is, we shift the original shift-sequence by one position to the
right, to make space for the initial term copied from a.

Then we can have an inverse permutation of shift also. For how this
works with a zero-based permutation, see:

https://oeis.org/A268717 a(0) = 0, a(n) = A003188(1+A006068(n-1)),
where A003188 is binary Gray code and A006068 is its inverse.
and its inverse https://oeis.org/A268718 a(0) = 0, a(n) = 1 +
A003188(A006068(n)-1).

Originally I wasn't even thinking about such shifting operation here.
Instead, my inspiration was: "What if all the signals on the board
(e.g. FPGA) were represented always Gray coded (with its known
advantages), how would then an adder look like?"
That is, would square array
https://oeis.org/A268715 A(i,j) = A003188(A006068(i) + A006068(j))
allow reduction to a more shortcut form?


> you could propose this for a particular sequence, and suggest to the
> sequence fans that they go about systematically adding these to the
> database.

I would do this only if there is some chance for at least
semi-interesting synergy.
E.g. I just submitted A297165: Permutation of natural numbers: a(n) =
A005940(2+A156552(n)), a(0) = 1.
Here it should be noted that the domain of A156552(n) starts from 1,
and its range from 0, and its inverse is f(n) = A005940(1+n), thus we
are still following the above idea of "shift". From the definition
follows that n and A297165(n) often share the larger primes in their
prime factorization, or at least the exponents of those larger primes.

For example:

A297165(14406) = 21609 = 3*3*7*7*7*7.
A297165(21609) = 5000 = 2*2*2*5*5*5*5.
A297165(5000) = 102487 = 7*11*11*11*11.
A297165(102487) = 24010 = 2*5*7*7*7*7.
A297165(24010) = 36015 = 3*5*7*7*7*7.
A297165(36015) = 7500 = 2*2*3*5*5*5*5.
A297165(7500) = 60025 = 5*5*7*7*7*7.
A297165(60025) = 11250 = 2*3*3*5*5*5*5.


> 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.
>

I think this is a special case of a more general theme of trying to
present a sequence in a not-so-readily apparent form.
That is, instead of trying to force the sequence to a recurrence of
the form a(n) = g(a(n-1)), we could try to view it in almost any form,
with n -> n-1 replaced by some other "recursion step", for example
floor(n/2), that is A004526(n).

E.g. A048673 which ostensibly is not a recurrence of the form a(2n) =
something(a(n)), a(2n+1) = something_else(a(n)) [except that it just
happens that a(2n) = 3*a(n) - 1], can still be represented like that
with the help of https://oeis.org/A253888
As such it would be almost a tautology (or obfuscation, i.e., "Where's
the point?"), but when A048673 is composed with A163511 we get
https://oeis.org/A245612
and then this (somewhat artificial) "alternative binary tree form" of
A048673 helped me to realize that A245612 also has a binary tree form,
which does not look so artificial at all.

> 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.

Could you give some reference or A-numbers for those?


Thanks,

Antti

> in general, to
> be sure, there is nothing nice to find.
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> SeqFan mailing list
> SeqFan at list.seqfan.eu
> http://list.seqfan.eu/cgi-bin/mailman/listinfo/seqfan
>
> ------------------------------
>
> End of SeqFan Digest, Vol 112, Issue 1
> **************************************