# [seqfan] The Recaman Sequence

Sun May 21 03:31:25 CEST 2017

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