[seqfan] The Recaman Sequence

[Frank Adams-Watters]

This recent discussion concerning cube-free words - specifically proving that their 
exists a lexicographically minimum one - is similar to the problem(s) relating to 
Recaman's Sequence (A005132).

The essential constraints we want to have for a sequence of non-negative integers are:

1) Starting with a(0) = 0, The absolute difference between a(n-1) and a(n) is n.

2) The sequence is one-to-one; i.e., no value is repeated.

3) Every non-negative integer does occur in the sequence.

Let us call any sequence obeying all three of these properties an R-sequence.

Recaman's Sequence itself (https://oeis.org/A005132) Satisfies (1) and is 
conjectured to satisfy (3); but it does not satisfy (2). On the other hand, 
https://oeis.org/A274648 satisfies (1) and (2), but not (3). (There are a 
number of variants that satisfy (2) and (3), but have weaker conditions 
for (1); we are not interested in these here.)

Conditions (1) and (2) have the required property that if they hold for each initial 
subsequence they then hold for the sequence as a whole. (This is the condition used 
to show that there is minimal cube-free sequence.) Condition (3) is not really 
applicable to finite sequences: every finite sequence can be extended to have every 
non-negative integer.

I have conjectured that given a finite sequence obeying (1) and (2) whose last value 
is the greatest in that sequence, one can extend it to a sequence which includes the 
minimum omitted value, and also has its last value as the greatest. (The "last value 
is the greatest" condition ensures that an infinite continuation obeying (1) and (2) 
exists.) The idea is that, having gotten to a new maximum, there is infinite space 
to fool around with, which will produce (infinitely many) finite sequences which 
end with the targeted value; and at least some of these should be continuable. 
Neither part of that program has been proved.

That conjecture immediately implies the existence of an R-sequence; simply apply 
it repeatedly.

In fact, it implies a stronger result: any finite sequence that is infinitely extendable 
can be extended to an R-sequence.

Now, assuming the conjecture, and getting back to A274648, this sequence 
obeys properties (1) and (2), and is the minimal sequence that does so. If we 
have an R-sequence, it must obey (1) and (2), and thus be lexicographically 
greater than or equal to A274648. But it cannot be equal, because A274648 
does not obey rule (3). Thus this is a lower bound for R-sequences. In fact, 
it is a greatest lower bound. Given any proposed larger lower bound L, there is 
a first point at which L is first greater than A274648, and we can get a smaller 
R-sequence by taking a larger initial segment of A274648 and extending it 
to an R-sequence.

Any hypothetical least R-sequence would also be a greatest lower bound 
for R-sequences, and hence equal to A274648. So, with the specified 
conjecture, there is no minimal R-sequence.

Franklin T. Adams-Watters