mdbtxt1
mdbtxt2
Proceed to Safety

Sequence A171884: Lexicographically first injective and unbounded sequence A(n) satisfying |A(n+1)-A(n)|=n for all N    

This is a sequence starting at zero and either adding or subtracting 1, 2, 3, 4, ... but each time making sure we don't go negative, don't repeat a previous number, and when presented with a choice go with the lower option; while making sure we never get stuck with no choice at all. The requirement to not repeat a number, and to avoid "having no choice at all" makes this sequence different from Recaman's sequence A5132. That sequence doesn't worry allows repeats if you choose to add n on the nth step, and the first time this happens is when the number 42 is repeated.

The sequence, Sloane's A171884, begins similarly to OEIS[A5132}:

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

Compare to Recaman's sequence A5132:

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, ...

The italicised terms show where A5132 diverges from A171884. In A171884, the choice of 64 instead of 18 avoids the need to either go negative or to duplicate 42.

A5132 is incorporated in this logo which appears on the OEIS Foundation home page:

Only the first 14 terms are shown, but the logo is definitely meant to represent Recaman's sequence and not A171884.

A171884's entry in the OEIS has my name as "author", but that's just because I submitted it to the database.

The Problem Statement and its Interpretation

The problem statement that inspired this sequence was given by N.J.A. Sloane in the first message quoted below. Sloane wrote:

Consider all rearrangements of the natural numbers1 with the property that the absolute values of the differences are 1,2,3,4,5,... (in that order).

John Conway asks, what is the lexicographically earliest such sequence?

Depending on the reader, the phrase "natural numbers" might seem ambiguous2. I and several other seqfan readers assumed and/or guessed what was meant. As seen below, an earlier message from Paul Raff, frequently quoted, was based on the "positive integers" interpretation. The message I picked up on was from Franklin T. Adams-Watters, and uses the "nonnegative integers" interpretation.

Based on that I began considering the sequence listed below, which begins: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, ... The differences between consecutive terms are: 1, 2, 3, -4, 5, 6, 7, -8, 9, -10, ... and if you remove the signs from these, you get the positive integers 1, 2, 3, 4, 5, .... That property is the most important property of this sequence.

As was eventually discovered (and described below) it eventually became necessary to abandon the requirement that every natural number appear exactly once in the sequence. Instead, some numbers appear once, and some not at all, but we can try to include as many as possible.

The other important property is "lexicographically first". That means that there is no other way to make a sequence like this, such that it would come earlier if sorted by the method of the old Sloane Integer Sequences database. In lexicographic ordering, all negative signs are ignored, and then a set of sequences is ordered like this:

all sequences starting 0, 0, ...
all sequences starting 0, 1, ...
all sequences starting 0, 2, ...
etc.
all sequences starting 1, 0, ...
all sequences starting 1, 1, ...
etc.
all sequences starting 2, 0, ...
etc.

The terms "non-negative", "injective" and "unbounded" are all properties of the sequence, and it's redundant to use all three words in describing this sequence. For each integer N there is an Nth sequence term A(N). This can be called a "map NA(N)". The map NA(N) is an "injective" map onto the nonnegative integers, because no two terms are identical. This means that "unbounded" is redundant, because as N keeps getting bigger you have to use bigger and bigger values for A(N) in order to avoid duplication. So if we say it's non-negative and injective, then unbounded goes without saying — unless you respect your readers, which I do. (The sequence is "bounded from below" by -1 because the terms are non-negative, but it needs to be bounded in both directions to not be "unbounded".)

First Few Terms

The sequence starts with 0 and 1, which has a difference of 1; then 3 because we need a difference of 2, and 1-2 would be negative which we can't do, so instead we go with 1+2=3.

After that you could go to 3+3=6 or 3-3=0, but 0 is already in the sequence so you must go to 6.

For the 5th term we could choose either 6+4=10 or 6-4=2. Since we want the "lexicographically earliest" sequence, we take the lower option.

In a similar way, it is easy to see that it proceeds: 7, 13, 20, 12, 21... It eventually becomes apparant that if you continue in this way the "missed" values 4 and 5 are never reached.

This leads to speculation about whether or not one should choose a different option at some point (for example, using 10 instead of 2 for the 5th term) to accomplish complete coverage of the natural numbers.

Discussion and Algorithm

In the discussion thread (quoted below) it was concluded that any missed terms can be filled in later. That led to a relatively simple algorithm.

The core of the algorithm is the function escape_p. Given an initial finite subsequence (the first N terms of a proposed solution) escape_p determines if there is any way to extend the sequence by adding zero or more terms to achieve a sequence for which the final term is the largest term. The sequence can then "escape to infinity" by continuing to increase without any guesswork as to whether the needed values have already been used. It is then hypothetically possible to "wander around" or "hover" in the higher values for however long it takes to get opportunities to "fill in the holes" in the initial sequence section. (For concrete examples, see Ron Hardin's list of initial subsequences that fill in the holes for each initial range of the integers up to 1..15).

escape_p is fairly easy to implement because it only needs to find one escape route. It does not need to satisfy a lexicographically earliest or any other particular criterion. Thus it can try the increasing term first, which in practice usually leads to a solution relatively quickly.

Once we have escape_p, generating the sequence is relatively easy. After we have N terms, consider each of the two possible values for the (N+1)th term. If the lower candidate allows an escape route, then use it, otherwise pick the higher candidate. (We know that one or the other will allow an escape route, because the escape_p test was applied when choosing the Nth term.)

Results, and Redefinition

Here are the first 200 terms given by this algorithm, grouped to illustrate the subsequent description:

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

The terms have been broken up into groups to show the patterns. In each group there are 2, 4, 12, 36, 108, ... terms. Except for the first group, the number of terms in each group is 4×3k. Each group consists of 2×3k descending terms interleaved with 2×3k ascending terms. Each group ends when its next descending term would be equal to the highest ascending term of the previous group, at this point the sequence increases three times in a row and the next group starts. The groups' values do not overlap each other at all: the smallest term in each group exceeds the largest term in the preceding group.

All natural numbers are covered except for the "gaps" 4,5, 14 to 19, 44 to 61, 134 to 187, 404 to 565, 1214 to 1699, ...: The size of each gap is 2, 6, 18, 54, 162, 486, 1458, ... which is also 2×3k. The starting points of the gaps (4, 14, 44, 134, 404, ...) are probably the even-numbered terms of A181655. 3

It is easy to see that the pattern will continue, and so it is clear that there was no uniquely defined sequence satisfying both requirements of "lexicographically earliest" and "bijection" (including all natural numbers in the sequence exactly once).

There are two similar sequences in OEIS that address these issues. Both satisfy the "lexicographically earliest" criterion. A5132 ("Recaman's sequence") addresses the issue by allowing duplicate values occasionally. A118201 takes the approach of including each integer exactly once and each value of |a(n+1)-a(n)| exactly once, but neither occur completely in order.

The sequence on this page, A171884, abandons the goal of including all natural numbers. The definition of A171884 is:

The lexicographically first injective and unbounded sequence a(n) satisfying |a(n+1)-a(n)| = n

Source Code

Here is the source code for the current version of my A171884 algorithm.


Partial Message Thread

Following are key messages in the discussion that led up to this webpage.

From: "N. J. A. Sloane"

Date: Tue, 9 Mar 2010 11:39:06 -0500

To: seqfan@seqfan.eu

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

see original Dear Seqfans,    Consider all rearrangements of the natural numbers with the property that the absolute values of the differences are 1,2,3,4,5,... (in that order).    John Conway asks, what is the lexicographically earliest such sequence?    The greedy approach leads you to A078943, which dies after 24 terms.    Recaman's sequence A005132 (or rather, the version defined on the positive integers, A063733) is another failure, because it contains repeated terms.    Does anyone have a candidate for the answer?    Neil

From: Raff, Paul

Date: Tue Mar 9 18:19:42 CET 2010

see original Very interesting sequence. It seems that we can follow this heuristic with backtracking:    1. If we've just added to our list, currently of length n, then we first try to add LAST-n to the list if possible, otherwise we add LAST+n, where LAST is the last element of the list.    2. If we're backtracking at the moment, then we know we have already tried to add LAST-n, so we add LAST+n. If we can't, then we stop and fail.    The following Mathematica code appears to do it:    GenerateSequence[{}, _, _] := {} GenerateSequence[L_List, max_Integer, True] := If[Length[L] == max, L, With[{n = Length[L]}, If[Last[L] - n < 1 || MemberQ[L, Last[L] - n], If[MemberQ[L, Last[L] + n], GenerateSequence[Drop[L, -1], max, False], GenerateSequence[Append[L, Last[L] + n], max, True]], GenerateSequence[Append[L, Last[L] - n], max, True]]]] GenerateSequence[L_List, max_Integer, False] := With[{n = Length[L]}, If[MemberQ[L, Last[L] + n], GenerateSequence[Drop[L, -1], max, False], GenerateSequence[Append[L, Last[L] + n], max, True]]]    Start if off with GenerateSequence[{1},N,True], where N is the length of the list when you want it to stop. When looking at this sequence a, if there is an index n such that a_n < a_{n+1} then the sequence won't change any more for the first n+1 terms.    However - based on its progression, it won't be a permutation of the natural numbers.    [paul]

From: Robert G. Wilson

Date: Tue Mar 9 21:44:56 CET 2010

see original Dear Paul Raff,    Will you be submitting the sequence: {1, 2, 4, 7, 3, 8, 14, 21, 13, 22, 12, 23, 11, 24, 10, 25, 9, 26, 44, 63, 43, 64, 42, 65, 41, 66, 40, 67, 39, 68, 38, 69, 37, 70, 36, 71, 35, 72, 34, 73, 33, 74, 32, 75, 31, 76, 30, 77, 29, 78, 28, 79, 27, 80, 134, 189, 133, 190, 132, 191, 131, 192, 130, 193, 129, 194, 128, 195, 127, 196, 126, 197, 125, 198, 124, 199, 123, 200, 122, 201, 121, 202, 120, 203, 119, 204, 118, 205, 117, 206, 116, 207, 115, 208, 114, 209, 113, 210, 112, 211} which is the result of: GenerateSequence[{1}, 100, True] This sequence is different from A063733 beginning at a(24); as noted by others.    Or the results of any other combination or starting points?    Sincerely yours, Bob.

From: Franklin T. Adams-Watters

Date: Tue Mar 9 21:46:56 CET 2010

see original I looked at this sequence (as described by Paul Raff) some time ago, and convinced myself that it does not reach every positive integer. (Not a proof, just that it pretty clearly does not. It probably can be proved with sufficiently careful analysis.)    If this is correct, it provides a negative answer to Conway's question. Given any infinite, one-to-one sequence with the specified difference property, we can extend any initial segment to a bijection. Extend the segment to where it reaches a new maximum. Now (this is a bit vague, but is doable) futz around until you can extend to the smallest number not yet used and back to another new maximum, then do so. Repeat this for the remainder of the sequence, and you have a bijection.    However, since the sequence Raff describes is the lexicographically first one-to-one sequence with the difference property, any sequence we generate in this way can be bettered by going further with the backtracking heuristic before switching to the algorithm I describe. In other words, Raff describes a sequence which is the greatest lower bound of all sequences with the desired property. If it doesn't have the property, there is no minimum.    I've been meaning to add both the sequence Raff describes, and the one generated by using my heuristic from the beginning (choosing the fastest possible extension to the current lowest missing term and back to a new maximum each time), but I haven't gotten around to coding them, and I didn't trust hand-generated values enough to submit them.    Franklin T. Adams-Watters

From: Raff, Paul

Date: Wed Mar 10 18:31:03 CET 2010

see original Hi Bob, Franklin (and everyone else),    Yes, I think this sequence will be a good entrant for the OEIS, and a paper is in the works if we can pursue further towards the original goal.    I won't have a candidate for submission until early next week, but what should the title be? The only thought I have is "A sequence a(n) satisfying |a(n+1) -a(n)| = n". That's pretty vague, though!    I suppose people typically search for the actual numbers themselves.    I'll post the submission for comments before actually submitting.    [paul]

From: Franklin T. Adams-Watters

Date: Wed Mar 10 21:08:28 CET 2010

see original How about "The lexicographically first one-to-one sequence a(n) satisfying |a(n+1) -a(n)| = n"?    Franklin T. Adams-Watters

From: N. J. A. Sloane

Date: Thu Mar 11 04:06:39 CET 2010

see original Ron, This looks very nice!    > At the moment, this reaches all integers up to top=57 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 41 66 40 67 39 68 38 69 37 70 36 71 35 72 34 73 33 74 32 75 31 76 30 77 29 78 28 79 27 80 134 1 89 133 190 132 191 131 192 130 193 129 194 128 195 127 196 266 337 409 336 410 335 259 182 260 181 101 20 102 19 103 18 104 17 105 16 106 15 107 200 294 389 293 390 292 391 291 392 494 597 701 596 490 383 275 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 312 447 311 448 310 449 309 450 308 451 307 452 306 453 305 156 6 157 5    I am in Florida on a very slow connection so have not read all the messages.    Supose you could run your program - or Paul's - for L = 100, 1000, 10000, etc., then the initial terms would stabilize, we hope, and we will get more and more of the sequence we are looking for, which is the limiting sequence.    Can you say how many terms of the sequence in your email will be in the final answer?    That is, as you increase L, are we getting more and more of the final answer, and if so how much do we have so far. I'm not asking for proofs, just what your sense is after looking at the data!    Neil

From: Franklin T. Adams-Watters

Date: Thu Mar 11 05:37:54 CET 2010

see original Neil,    Did you miss my note? There is no lexicographically least permutation with the specified difference property. There are many permutations with the property, but the greatest lower bound of these permutations is the sequence Raff describes, and this is one-to-one but not onto.    There may be a sequence with the property such that the inverse permutation is lexicographically least. The algorithm I described is "trying" to find this, but may not actually do so.    Franklin T. Adams-Watters    P.s. The sequence from Ron cannot be continued. The next term must be 158; after that would have to be 4 or 312, both of which have already been seen.

From: N. J. A. Sloane

Date: Thu Mar 11 06:06:52 CET 2010

see original Franklin, I had seen your message, but I had not appreciated what it said!    I've read the message several times, but I admit I don't understand it.    The crucial two paragraphs are these, I believe:    (start)    If this is correct, it provides a negative answer to Conway's question. Given any infinite, one-to-one sequence with the specified difference property, we can extend any initial segment to a bijection. Extend the segment to where it reaches a new maximum. Now (this is a bit vague, but is doable) futz around until you can extend to the smallest number not yet used and back to another new maximum, then do so. Repeat this for the remainder of the sequence, and you have a bijection.    However, since the sequence Raff describes is the lexicographically first one-to-one sequence with the difference property, any sequence we generate in this way can be bettered by going further with the backtracking heuristic before switching to the algorithm I describe. In other words, Raff describes a sequence which is the greatest lower bound of all sequences with the desired property. If it doesn't have the property, there is no minimum.    (end)    I don't really follow the algorithm you give in the first of the two paragraphs. Could you possibly explain it in more detail?    I am also having trouble following the argument in the second paragraph. Since Raff's sequence is not a permutation, why should we start with it?    I can see that you are probably right, and that the sequence we are looking for does not exist, but I would like to see more details of the argument!    Best regards Neil

From: Franklin T. Adams-Watters

Date: Thu Mar 11 06:42:06 CET 2010

see original 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

From: Ron Hardin

Date: Thu Mar 11 07:53:49 CET 2010

see original 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.

From: Robert Munafo

Date: Thu Mar 11 10:21:23 CET 2010

see original 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.    [2] http://en.wikipedia.org/wiki/Axiom_of_choice    [3] from Franklin T. Adams-Watters's message of Mar 10, 2010 at 15:08.    [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.

From: Robert Munafo

Date: Thu Mar 11 12:48:49 CET 2010

Subject: Proposed solution, differs from A005132 after 23 terms

see original 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, ...

From: Raff, Paul

Date: Thu Mar 11 13:22:37 CET 2010

see original 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]

From: Robert Munafo

Date: Thu Mar 11 13:41:57 CET 2010

see original 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.

From: Robert Munafo

Date: Thu Mar 11 13:51:31 CET 2010

see original That's close to what I'm getting (see the new thread based on my specific algorithm, which may differ from the original problem)    I also get a 2*3^k "gap" size (I called them "clumps of holes", but it's the same thing) but I differ on what the actual "gaps" are. You got 15-20, I got 14-19; instead of 45-62 I got 44-61, and so on.    Also of note are the sizes of the blocks of integers included by the sequence (the "figure" to which the gaps are the "ground") which are: 8, 24, 72, 216, 648, ... or 8*3^k.

From: Robert Munafo

Date: Fri Mar 12 00:00:44 CET 2010

see original On Thu, Mar 11, 2010 at 14:54, Raff, Paul <paul at myraff.com> wrote:    > I believe Bob is starting at zero, and I am starting at one. > > [paul] >    It's Robert.    And yes, Paul, your sequence seems to be the same except that each term is one bigger. Given the existence of A005132 and A118201 and the discussion by others I believe that starting at zero is a little better.    Notice A063733 and A078943 -- those entries have related definitions, but have not been developed as far (fewer terms, fewer descriptions and references, etc). More importantly, both have a repeated 1 at the beginning which goes against the whole "bijection" idea.    NJAS's initial statement referred to "natural numbers", usage of which is ambiguous (Mathworld suggests "positive" or "nonnegative" integers).       On Thu, Mar 11, 2010 at 2:50 PM, <franktaw at netscape.net> wrote: > > From the descriptions, these sequences should be identical. I'd like > > to see both of them to see where and why they are different. > > > > Franklin T. Adams-Watters > > > > -----Original Message----- > > From: Robert Munafo <mrob27 at gmail.com> > > ... > > > > I also get a 2*3^k "gap" size (I called them "clumps of holes", but > > it's the > > same thing) but I differ on what the actual "gaps" are. You got 15-20, > > I got > > 14-19; instead of 45-62 I got 44-61, and so on. >    -- Robert Munafo -- mrob.com

From: Robert Munafo

Date: Fri Mar 12 00:11:51 CET 2010

see original All right, I have established a webpage for this sequence at http://mrob.com/pub/math/seq-a171884.html and submitted the sequence on the AT+T classic server as A171884.    Neil: Since it is not the original "rearrangement of the natural numbers" I consider it a different problem you stated. What do we do with that? You wrote:    Consider all rearrangements of the natural numbers with the property that the absolute values of the differences are 1,2,3,4,5,... (in that order).    John Conway asks, what is the lexicographically earliest such sequence?    On Thu, Mar 11, 2010 at 18:00, Robert Munafo <mrob27 at gmail.com> wrote:    > [...] Given the existence of A005132 and A118201 and the discussion by > others I believe that starting at zero is a little better. > > Notice A063733 and A078943 -- those entries have related definitions, but > have not been developed as far (fewer terms, fewer descriptions and > references, etc). More importantly, both have a repeated 1 at the beginning > which goes against the whole "bijection" idea. > > NJAS's initial statement referred to "natural numbers", usage of which is > ambiguous (Mathworld suggests "positive" or "nonnegative" integers). >    -- Robert Munafo -- mrob.com

From: N. J. A. Sloane

Date: Fri Mar 12 00:19:46 CET 2010

see original > NJAS's initial statement referred to "natural numbers"    To me the natural numbers are 1,2,3,4,5,...    The nonnegative integers are 0,1,2,3,4,5,...       Best regards Neil

From: Ron Hardin

Date: Fri Mar 12 02:43:32 CET 2010

see original The shortest (not necessarily lexicographically smallest) such sequence containing all values 1..top for increasing values of top (and no values repeated) are    values 1..1 length=1 : 1 values 1..2 length=2 : 1 2 values 1..3 length=5 : 1 2 4 7 3 values 1..4 length=5 : 1 2 4 7 3 values 1..5 length=13 : 1 2 4 7 3 8 14 21 29 38 28 17 5 values 1..6 length=17 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 3 values 1..7 length=17 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 3 values 1..8 length=20 : 1 2 4 7 3 8 14 21 29 20 30 41 53 40 54 39 23 6 24 5 values 1..9 length=29 : 1 2 4 7 3 8 14 21 29 20 30 41 53 40 54 39 23 6 24 5 25 46 68 91 115 90 64 37 9 values 1..10 length=36 : 1 2 4 7 3 8 14 21 29 20 30 41 53 40 54 39 23 6 24 5 25 46 68 91 115 140 166 193 165 136 106 75 43 10 44 9 values 1..11 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5 values 1..12 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5 values 1..13 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5 values 1..14 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5 values 1..15 length=41 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 38 53 69 52 34 15 35 56 78 55 31 6 32 5 33 62 92 123 155 122 156 121 85 48 10 49 9    modulo program bugs. Maybe have more later.

From: Ron Hardin

Date: Fri, Mar 12, 2010 at 19:10

see original

and revision Extended and made lexicographically smallest (using a different method, nice that they agree!) {Repaired later: duplicate lines removed and first two lines added back in -RPM}    Shortest such series starting with 1, repeating no values, and having all values in 1..top, for increasing values of top    values 1..1 length=1 : 1    values 1..2 length=2 : 1 2    values 1..3 length=5 : 1 2 4 7 3    values 1..4 length=5 : 1 2 4 7 3    values 1..5 length=13 : 1 2 4 7 3 8 14 21 29 38 28 17 5    values 1..6 length=17 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 3    values 1..7 length=17 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 3    values 1..8 length=20 : 1 2 4 7 3 8 14 21 13 22 32 43 55 68 54 39 23 6 24 5    values 1..9 length=29 : 1 2 4 7 3 8 14 21 29 20 30 41 53 40 54 39 23 6 24 5 25 46 68 91 115 90 64 37 9    values 1..10 length=36 : 1 2 4 7 3 8 14 21 29 20 30 41 53 40 54 39 23 6 24 5 25 46 68 91 115 140 166 193 165 136 106 75 43 10 44 9    values 1..11 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5    values 1..12 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5    values 1..13 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5    values 1..14 length=37 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 89 114 140 167 195 166 136 105 73 40 6 41 5    values 1..15 length=41 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 38 53 69 52 34 15 35 56 78 55 31 6 32 5 33 62 92 123 155 122 156 121 85 48 10 49 9    values 1..16 length=45 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 41 66 92 119 147 176 146 115 83 50 16 51 15 52 90 129 89 48 6 49 5    values 1..17 length=45 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 83 62 40 17 41 16 42 15 43 72 102 71 103 136 170 205 169 206 168 129 89 48 6 49 5    values 1..18 length=56 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 86 109 133 108 134 107 135 106 136 105 73 40 6 41 5 42 80 119 159 118 160 117 161 116 162 115 67 18 68 17 69 16 70 15    values 1..19 length=56 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 86 109 133 108 134 107 135 106 136 105 73 40 6 41 5 42 80 119 159 200 158 201 157 112 66 19 67 18 68 17 69 16 70 15    values 1..20 length=58 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 35 18 36 17 37 16 38 15 39 14 40 67 95 66 96 127 159 192 158 193 157 120 82 43 3 44 86 129 173 218 264 217 265 216 166 115 63 10 64 9 65 8    values 1..21 length=58 : 1 2 4 7 11 6 12 5 13 22 32 21 33 20 34 19 35 18 36 17 37 16 38 15 39 14 40 67 95 66 96 127 159 192 158 193 157 120 82 43 3 44 86 129 173 218 264 217 265 216 166 115 63 10 64 9 65 8    values 1..23 length=62 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 83 62 40 17 41 16 42 15 43 72 102 71 103 136 170 205 169 206 168 129 89 48 6 49 5 50 96 143 191 142 192 243 295 242 188 133 77 20 78 19 79 18    values 1..24 length=62 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 83 62 40 17 41 16 42 15 43 72 102 71 103 136 170 205 169 206 168 129 89 48 6 49 5 50 96 143 191 142 192 243 295 242 188 133 77 20 78 19 79 18    values 1..25 length=62 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 83 62 40 17 41 16 42 15 43 72 102 71 103 136 170 205 169 206 168 129 89 48 6 49 5 50 96 143 191 142 192 243 295 242 188 133 77 20 78 19 79 18    values 1..26 length=62 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 83 62 40 17 41 16 42 15 43 72 102 71 103 136 170 205 169 206 168 129 89 48 6 49 5 50 96 143 191 142 192 243 295 242 188 133 77 20 78 19 79 18    Runs are starting to go noticeably exponential timewise, taking about eight hours when there's no solution, so top=27 might take too long.

From: Ron Hardin

Date: Wed Mar 17 01:28:36 CET 2010

see original Shortest such seqence starting with 1 containing all the values 1..80 without repeats    values 1..80 length=153 : 1 2 4 7 3 8 14 21 13 22 12 23 11 24 10 25 9 26 44 63 43 64 42 65 41 66 40 67 39 68 38 69 37 70 36 71 35 72 34 73 33 74 32 75 31 76 30 77 29 78 28 79 27 80 134 189 245 302 244 185 125 186 248 311 247 182 116 49 117 48 118 47 119 46 120 45 121 198 276 197 277 358 440 357 441 356 270 183 95 6 96 5 97 190 284 379 283 380 282 381 481 582 480 377 273 168 62 169 61 170 60 171 59 172 58 173 57 174 56 175 55 176 54 177 53 178 52 179 51 180 50 181 313 446 580 715 579 442 304 443 303 162 20 163 19 164 18 165 17 166 16 167 15    It's unusually efficient, so maybe has some useful structure.


Footnotes

1 : natural numbers : Usage of this term is ambiguous; see Natural number. Sloane later wrote that he intended the term to mean "1,2,3,4,5,...", that is, "positive integers".

2 : Wolfram Mathworld states:

Regrettably, there seems to be no general agreement about whether to include 0 in the set of natural numbers. In fact, Ribenboim (1996) states "Let P be a set of natural numbers; whenever convenient, it may be assumed that 0 P."

The set of natural numbers (whichever definition is adopted) is denoted N.

Due to lack of standard terminology, the following terms and notations are recommended in preference to "counting number," "natural number," and "whole number."

set name symbol
..., -2, -1, 0, 1, 2, ... integers Z
1, 2, 3, 4, ... positive integers Z-+
0, 1, 2, 3, 4, ... nonnegative integers Z-*
0, -1, -2, -3, -4, ... nonpositive integers
-1, -2, -3, -4, ... negative integers Z- -

3 : Maximilian Hasler, personal communication, 2013.



Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2018 Jun 30. s.27