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

Raff, Paul praff at math.rutgers.edu
Wed Mar 10 18:31:03 CET 2010


Hi Bob, Franklin (and everyone else),

Yes, I think this sequence will be a good entrant for the OEIS, and a
paper is in the works if we can pursue further towards the original
goal.

I won't have a candidate for submission until early next week, but
what should the title be? The only thought I have is "A sequence a(n)
satisfying |a(n+1) -a(n)| = n". That's pretty vague, though!

I suppose people typically search for the actual numbers themselves.

I'll post the submission for comments before actually submitting.


                           [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 3:46 PM,  <franktaw at netscape.net> wrote:
> 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
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>




More information about the SeqFan mailing list