[seqfan] Re: seqs whose |differences| are 1,2,3,4,...

[Raff, Paul]

Very interesting sequence. It seems that we can follow this heuristic
with backtracking:

1. If we've just added to our list, currently of length n, then we
first try to add LAST-n to the list if possible, otherwise we add
LAST+n, where LAST is the last element of the list.
2. If we're backtracking at the moment, then we know we have already
tried to add LAST-n, so we add LAST+n. If we can't, then we stop and
fail.

The following Mathematica code appears to do it:

GenerateSequence[{}, _, _] := {}
GenerateSequence[L_List, max_Integer, True] :=
 If[Length[L] == max, L,
  With[{n = Length[L]},
   If[Last[L] - n < 1 || MemberQ[L, Last[L] - n],
    If[MemberQ[L, Last[L] + n],
     GenerateSequence[Drop[L, -1], max, False],
     GenerateSequence[Append[L, Last[L] + n], max, True]],
    GenerateSequence[Append[L, Last[L] - n], max, True]]]]
GenerateSequence[L_List, max_Integer, False] :=
 With[{n = Length[L]},
  If[MemberQ[L, Last[L] + n],
   GenerateSequence[Drop[L, -1], max, False],
   GenerateSequence[Append[L, Last[L] + n], max, True]]]

Start if off with GenerateSequence[{1},N,True], where N is the length
of the list when you want it to stop. When looking at this sequence a,
if there is an index n such that a_n < a_{n+1} then the sequence won't
change any more for the first n+1 terms.

However - based on its progression, it won't be a permutation of the
natural numbers.


                                                 [paul]

---
Paul Raff
Postdoctoral Researcher - Cognitive Assistants as Analysts' Deputies
School of Communication and Information
Rutgers University
http://www.myraff.com
Work: (732) 932-7500 x8023
Mobile: (704) 604-2154
---



On Tue, Mar 9, 2010 at 11:39 AM, N. J. A. Sloane <njas at research.att.com> wrote:
>
> Dear Seqfans,
>
> Consider all rearrangements of the natural numbers with the property that
> the absolute values of the differences are 1,2,3,4,5,... (in that order).
>
> John Conway asks, what is the lexicographically earliest such sequence?
>
> The greedy approach leads you to A078943, which dies after 24 terms.
>
> Recaman's sequence A005132 (or rather, the version defined
> on the positive integers, A063733) is another failure, because it contains
> repeated terms.
>
> Does anyone have a candidate for the answer?
>
> Neil
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>