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

franktaw at netscape.net franktaw at netscape.net
Thu Mar 11 20:56:22 CET 2010

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

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

```