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

franktaw at netscape.net franktaw at netscape.net
Tue Mar 9 21:46:56 CET 2010

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

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

```