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

Raff, Paul paul at myraff.com
Thu Mar 11 13:22:37 CET 2010


Hi all again,

Like I said before, I should be doing other things and plan to focus
more on this problem by early next week, but I did want to add my two
cents. It's a good sequence!

The sequence from my algorithm has the following gaps (i.e. numbers
that aren't in the sequence): {5, 6}, {15, 16, 17, 18, 19, 20}, {45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62} .
. . and the pattern continues. The gaps have size 2*3^k, which
(superficially) reminds me of the Cantor Set.

It's telling that 5 and 6 are at the very end of Ron's sequence - I
imagine that an increase in Ron's parameter L will cause 5 and 6 (and
15 and 16, etc.) to be pushed farther to the back of the sequence,
where in the limit they disappear to infinity and beyond.


                                 [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 Thu, Mar 11, 2010 at 4:21 AM, Robert Munafo <mrob27 at gmail.com> wrote:
> I believe this is the crucial insight:* "**hole-filling postponed without
> limit" [1]*
>
> The difficulty in definitively selecting a "lexicographically first
> arrangement of the integers" seems similar to the difficulty in accepting
> the Axiom of Choice. [2] We are confronted, (or possibly confounded), by the
> uncountably large set of possible solutions.
>
> But if one establishes that all the holes can be filled in later, and
> further that we only need to determine some conveniently-small finite
> initial portion of the sequence, then we can see that given any finite N,
> the first N terms of the following two sequences are the same (using wording
> of [3] and changing "one-to-one" to "injective and unbounded"):
>
>  The lexicographically first one-to-one sequence a(n)
>  satisfying |a(n+1)-a(n)| = n
>
>  The lexicographically first injective and unbounded sequence b(n)
>  satisfying |b(n+1)-b(n)| = n
>
> Where "injective" is understood to mean that for any integer j, there is *at
> most* one n such that b(n)=j (see [4]) and "unbounded" means that there is a
> b(n) for all n (not quite the same as in [5], is there a better word?) or in
> other words that the sequence "has an infinite number of terms" (using the
> sloppy colloquial jargon of the 18th century).
>
> Once we accept that, then the method of FTAW [6] seems to work: Use a
> conditionally-greedy selection algorithm that does not accept any candidate
> next term until a guaranteed "escape route" is found.
>
> [1] from Ron Hardin's message of Mar 11, 2010 at 01:53, included below.
>
> [2] http://en.wikipedia.org/wiki/Axiom_of_choice
>
> [3] from Franklin T. Adams-Watters's message of Mar 10, 2010 at 15:08,
> included below.
>
> [4] http://en.wikipedia.org/wiki/Injective_function
>
> [5] http://en.wikipedia.org/wiki/Bounded_function
>
> [6] from Franklin T. Adams-Watters's message of Mar 11, 2010 at 00:42,
> included below.
>
> - - -
>
> On Thu, Mar 11, 2010 at 01:53, Ron Hardin <rhhardin at att.net> wrote:
>>
>> I didn't follow what the note meant either.
>>
>> That sequence can't be continued, right; and increasing L (the lookahead)
> can apparently raise the maximum of 1-1 terms 1..top reached.
>>
>> I'm less worried about its being lexicographically least than existing.
>>
>> The method so far however generates only finite sequences.  Is that always
> true (so there is no 1-1 sequence with the difference property at all) or
> will some patterns emerge, like  166 56 167 55 168 54 169 53 170 52 171 51
> 172 50 173 49 174 48 175 47 176 46 177 45 178, that can be strung together
> to fill in gaps with some transitional terms.
>>
>> The failure that seems most likely is that the stable beginning of the
> sequence, as L is increased, is strictly increasing, with that hole-filling
> postponed without limit.
>>
>> I might be saying the same thing but I can't tell.
>> [...]
>
>  - - -
>
> On Wed, Mar 10, 2010 at 15:08, "Franklin T. Adams-Watters" <
> franktaw at netscape.net> wrote:
>> How about "The lexicographically first one-to-one sequence a(n)
>> satisfying |a(n+1) -a(n)| = n"?
>>
>> [...]
>
>  - - -
>
> On Thu, Mar 11, 2010 at 00:42, "Franklin T. Adams-Watters" <
> franktaw at netscape.net> wrote:
>> OK, I'll see what I can do.
>>
>> First, let me note that there are two assertions here, which I can
>> clearly see are true, but I can't actually prove either of them.
>>
>> The first is that Paul's sequence is not onto.  I think a careful
>> analysis of exactly how it behaves will enable this to be proved.
>>
>> Paul's sequence is, by construction, the lexicographically first
>> one-to-one sequence with the difference property.
>>
>> The second assertion that I can't prove is that, given any one-to-one
>> finite sequence with the difference property, that ends with a new
>> maximum, it is possible to extend to a permutation.  We do this by
>> extending to a sequence which contains the minimum value not yet in the
>> sequence and ends with another new maximum.  Iterating this will
>> produce a permutation.  (Obviously, any sequence ending with a new
>> maximum can be indefinitely extended.)  So, for example, after starting
>>
>> 0,1,3,6,2,7
>>
>> we wish to extend to a one-to-one sequence including 4.  Simply trying
>> all possibilities, the shortest such is
>>
>> 0,1,3,6,2,7,13,20,28,37,27,16,4
>>
>> which can be extended by 17,31,46 to reach a new maximum.  (I have not
>> yet determined what the shortest extension from here to include 5 and
>> escape to infinity is; I think I'll have to write the program instead
>> of continuing to work on it by hand.)
>>
>> Now, any permutation with the difference property must be greater than
>> Paul's sequence.  Find the point at which Paul's sequence is smaller,
>> continue to a new maximum in the sequence, and this can be extended to
>> a permutation smaller than our original one.
>>
>> Franklin T. Adams-Watters
>
> --
>  Robert Munafo  --  mrob.com
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>




More information about the SeqFan mailing list