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

[franktaw at netscape.net]

I looked at this sequence (as described by Paul Raff) some time ago, 
and convinced myself that it does not reach every positive integer.  
(Not a proof, just that it pretty clearly does not.  It probably can be 
proved with sufficiently careful analysis.)

If this is correct, it provides a negative answer to Conway's question. 
  Given any infinite, one-to-one sequence with the specified difference 
property, we can extend any initial segment to a bijection.  Extend the 
segment to where it reaches a new maximum.  Now (this is a bit vague, 
but is doable) futz around until you can extend to the smallest number 
not yet used and back to another new maximum, then do so.  Repeat this 
for the remainder of the sequence, and you have a bijection.

However, since the sequence Raff describes is the lexicographically 
first one-to-one sequence with the difference property, any sequence we 
generate in this way can be bettered by going further with the 
backtracking heuristic before switching to the algorithm I describe.  
In other words, Raff describes a sequence which is the greatest lower 
bound of all sequences with the desired property.  If it doesn't have 
the property, there is no minimum.

I've been meaning to add both the sequence Raff describes, and the one 
generated by using my heuristic from the beginning (choosing the 
fastest possible extension to the current lowest missing term and back 
to a new maximum each time), but I haven't gotten around to coding 
them, and I didn't trust hand-generated values enough to submit them.

Franklin T. Adams-Watters

-----Original Message-----
From: Raff, Paul <praff at math.rutgers.edu>

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