[seqfan] 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 12:48:49 CET 2010
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.
- - -
Source code in C:
#define CW2010_SIZE_LIM 998
/* Search for an item, return a negative result if it is not found */
long cw2010_seek(long * haystack, long size, long needle);
long cw2010_seek(long * haystack, long size, long needle)
{
long i;
for(i=0; i<size; i++) {
if(haystack[i] == needle) {
return(i);
}
}
return(-1);
}
/* Return the value of the largest element of a list */
long cw2010_largest(long * l, long size);
long cw2010_largest(long * l, long size)
{
long best, i;
best = -1;
for(i=0; i<size; i++) {
if(l[i] > best) {
best = l[i];
}
}
return(best);
}
/* Return true if there is a direct "escape route" by going up each time.
Non-recursive and a little faster than a general escape search. */
long cw2010_escdir_p(long * l, long size);
long cw2010_escdir_p(long * l, long size)
{
long largest;
long i, n;
if (size==0) {
return(1);
}
largest = cw2010_largest(l, size);
if (l[size-1] == largest) {
return(1);
}
i = size;
n = l[i-1];
while(n < largest) {
n = n + i; i = i+1;
if (cw2010_seek(l, size, n)) {
return(0);
}
}
return(1);
}
/* Return true if the "down" next term option is legal */
long cw2010_down_p(long * l, long size);
long cw2010_down_p(long * l, long size)
{
long t;
t = l[size-1] - size;
if ((t < 0) || (cw2010_seek(l, size, t) >= 0)) {
return(0);
}
return(1);
}
/* Return true if the "up" next term option is legal */
long cw2010_up_p(long * l, long size);
long cw2010_up_p(long * l, long size)
{
long t;
t = l[size-1] + size;
if (cw2010_seek(l, size, t) >= 0) {
return(0);
}
return(1);
}
/* Recursive algorithm, seeks an escape route preferring the "upper path"
at each choice in order to find an exit quickly. */
long cw2010_escape_p(long * l, long size);
long cw2010_escape_p(long * l, long size)
{
long i;
/* First try the direct route, which will save time on the recursive
backtracking */
if (cw2010_escdir_p(l, size)) {
return(1);
}
if (size >= CW2010_SIZE_LIM) {
fprintf(stderr, "cw2010_esc_p: Reached allocation limit.\n");
exit(-1);
}
if (cw2010_up_p(l, size)) {
l[size] = l[size-1] + size;
return(cw2010_escape_p(l, size+1));
}
if (cw2010_down_p(l, size)) {
l[size] = l[size-1] - size;
return(cw2010_escape_p(l, size+1));
}
return(0);
}
* Main algorithm, seeks a limited-size initial subsequence of the (presumed
unique) lexicographically earliest permutation of integers a(n) such
that |a(n+1)-a(n)|=n for all n. */
void cw2010_a(void);
void cw2010_a(void)
{
long l[CW2010_SIZE_LIM];
long i;
i = 0;
l[i] = 0;
printf("%d, ", l[i]);
while(i < CW2010_SIZE_LIM/2) {
i++;
/* First try the "down" option */
if (cw2010_down_p(l, i)) {
l[i] = l[i-1] - i;
/* Is there any way to "escape to infinity" based on this choice? */
if (cw2010_escape_p(l, i+1)) {
/* Yes, we can continue with this choice */
printf("%d, ", l[i]);
} else {
/* Down failed, so try going up */
l[i] = l[i-1] + i;
if (cw2010_escape_p(l, i+1)) {
/* Yes, up worked, so we'll go with that. */
printf("%d, ", l[i]);
} else {
/* Error! there is no solution at all */
fprintf(stderr, "cw2010_a: got stuck after %d terms.\n", i);
exit(-1);
}
}
} else if (cw2010_up_p(l, i)) {
l[i] = l[i-1] + i;
if (cw2010_escape_p(l, i+1)) {
/* Yep, up worked */
printf("%d, ", l[i]);
} else {
/* Error: there is no solution */
fprintf(stderr, "cw2010_a: stuck after %d terms.\n", i);
exit(-1);
}
} else {
/* Error: there is no solution */
fprintf(stderr, "cw2010_a: stuck after %d terms.\n", i);
exit(-1);
}
}
printf("\n");
printf("Total: %d terms.\n", i+1);
}
- - -
First 500 terms:
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, 78, 26, 79, 133, 188, 132, 189,
131, 190, 130, 191, 129, 192, 128, 193, 127, 194, 126, 195, 125, 196, 124,
197, 123, 198, 122, 199, 121, 200, 120, 201, 119, 202, 118, 203, 117, 204,
116, 205, 115, 206, 114, 207, 113, 208, 112, 209, 111, 210, 110, 211, 109,
212, 108, 213, 107, 214, 106, 215, 105, 216, 104, 217, 103, 218, 102, 219,
101, 220, 100, 221, 99, 222, 98, 223, 97, 224, 96, 225, 95, 226, 94, 227,
93, 228, 92, 229, 91, 230, 90, 231, 89, 232, 88, 233, 87, 234, 86, 235, 85,
236, 84, 237, 83, 238, 82, 239, 81, 240, 80, 241, 403, 566, 402, 567, 401,
568, 400, 569, 399, 570, 398, 571, 397, 572, 396, 573, 395, 574, 394, 575,
393, 576, 392, 577, 391, 578, 390, 579, 389, 580, 388, 581, 387, 582, 386,
583, 385, 584, 384, 585, 383, 586, 382, 587, 381, 588, 380, 589, 379, 590,
378, 591, 377, 592, 376, 593, 375, 594, 374, 595, 373, 596, 372, 597, 371,
598, 370, 599, 369, 600, 368, 601, 367, 602, 366, 603, 365, 604, 364, 605,
363, 606, 362, 607, 361, 608, 360, 609, 359, 610, 358, 611, 357, 612, 356,
613, 355, 614, 354, 615, 353, 616, 352, 617, 351, 618, 350, 619, 349, 620,
348, 621, 347, 622, 346, 623, 345, 624, 344, 625, 343, 626, 342, 627, 341,
628, 340, 629, 339, 630, 338, 631, 337, 632, 336, 633, 335, 634, 334, 635,
333, 636, 332, 637, 331, 638, 330, 639, 329, 640, 328, 641, 327, 642, 326,
643, 325, 644, 324, 645, 323, 646, 322, 647, 321, 648, 320, 649, 319, 650,
318, 651, 317, 652, 316, 653, 315, 654, 314, 655, 313, 656, 312, 657, 311,
658, 310, 659, 309, 660, 308, 661, 307, 662, 306, 663, 305, 664, 304, 665,
303, 666, 302, 667, 301, 668, 300, 669, 299, 670, 298, 671, 297, 672, 296,
673, 295, 674, 294, 675, 293, 676, 292, 677, 291, 678, 290, 679, 289, 680,
288, 681, 287, 682, 286, 683, 285, 684, 284, 685, 283, 686, 282, 687, 281,
688, 280, 689, 279, 690, 278, 691, 277, 692, 276, 693, 275, 694, 274, 695,
273, 696, 272, 697, 271, 698, 270, 699, 269, 700, 268, 701, 267, 702, 266,
703, 265, 704, 264, 705, 263, 706, 262, 707, 261, 708, 260, 709, 259, 710,
258, 711, 257, 712, 256, 713, 255, 714, 254, 715, 253, 716, 252, 717, 251,
718, 250, 719, 249, 720, 248, 721, 247, 722, 246, 723, 245, 724, 244, 725,
243, 726, 242, 727, 1213, 1700, 1212, 1701, 1211, 1702, 1210, 1703, 1209,
1704, 1208, 1705, 1207, 1706, ...
On Thu, Mar 11, 2010 at 04:21, 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
>
--
Robert Munafo -- mrob.com
More information about the SeqFan
mailing list