[seqfan] Re: Proposed solution, differs from A005132 after 23 terms (was Re: seqs whose |differences| are 1, 2, 3, 4, ...

[franktaw at netscape.net]

Yes, "indefinite postponement of hole-filling" is a reasonable way to 
describe why there is no minimum permutation.

You are misusing "one-to-one".  This means only that no value is 
repeated.  The property that every number is present is called being 
"onto".  A sequence that is both one-to-one and onto is a "permutation".

Alternatively, these can be described as injections, surjections, and 
bijections, respectively.

Franklin T. Adams-Watters

-----Original Message-----
From: Robert Munafo <mrob27 at gmail.com>

I am now thinking that the original notion (a unique 
lexicographically-first
one-to-one sequence) does not exist, because:

* For certain values of N, any solution (lexicographically first
subsequence) of length greater than N leaves all the holes that were 
present
in the length-N solution, and

* For each such N, there is another higher N with the same defect, and

* If the holes are postponed indefinitely for all N, all possible 
one-to-one
sequences are eliminated.

This seems to be supported by the pattern that emerges from the 
algorithm I
posted in the previous message. There is a rather simple pattern of
consecutive "clumps" of holes; the holes are:

4,5, 14-19, 44-61, 134-187, 404-565, 1214-1699, 3644-5101, 10934-15307, 
...

with the initial hole in each clump given by i[0]=4; i[n]=3i[n-1]+2 and 
the
number of holes in each clump given by n[n]=2*3^n.

On Thu, Mar 11, 2010 at 06:48, Robert Munafo <mrob27 at gmail.com> wrote:

> Using the method I just outlined, I get:
>
> 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 
62, 42,
> 63, 41, 64, 40, 65, 39, 66, 38, 67, 37, 68, 36, 69, 35, 70, 34, 71, 
33, 72,
> 32, 73, 31, 74, 30, 75, 29, 76, 28, 77, 27, ...
>
> This differs from Recaman's sequence A005132 in that it does not 
duplicate
> any values. Another similar sequence is A118201, which avoids 
duplication by
> letting some differences |a(n+1)-a(n)| differ from n yet maintaining 
the
> requirement that each difference value occurs only once.
>
> The algorithm (source code below) centers on the "cw2010_escape_p" 
test,
> which determines if there is any way to "escape to infinity" from a 
given
> initial subsequence. The key here is realizing that for this 
algorithm, ANY
> escape route is suitable, so it can use the "highest first greedy" 
method to
> minimize search time.
>
> The main algorithm then becomes fairly simple: after determining the 
first
> N terms, there are two candidates for the next term: prefer the lower
> candidate if and only if there exists some "escape route", and in any 
event
> take a candidate only if it is non-negative and has not been seen 
before.
>
> I have added an entry to my mrob.com/pub/math/OEIS-extra.txt on the
> assumption that NJAS should be the author.
>
>  [...]
>

--
 Robert Munafo  --  mrob.com

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/