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

Robert Munafo mrob27 at gmail.com
Thu Mar 11 13:41:57 CET 2010


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



More information about the SeqFan mailing list