# [seqfan] Re: Recaman observation

David Wilson dwilson at gambitcomm.com
Fri Jul 17 15:40:28 CEST 2009

```Martin Fuller wrote:
> Correction for Recaman sequence and new sequence:
> [1] a(n) > 0

A005132 has a(0) = 0.

>
>> From: Martin Fuller <martin_n_fuller at btinternet.com>
>> Subject: [seqfan] Re: Recaman observation
>> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
>> Date: Thursday, 16 July, 2009, 2:40 PM
>>
>>> From: David Wilson <dwilson at gambitcomm.com>
>>> Subject: [seqfan]  Recaman observation
>>> To: "Sequence Fanatics" <seqfan at list.seqfan.eu>
>>> Date: Monday, 13 July, 2009, 2:20 PM
>> ...
>>> So Recaman satisfies
>>>
>>> [1] a(n) >= 0   *** should be a(n) > 0 ***

See above.

>>> [2] |a(n)-a(n-1)| = n
>>>
>> ...
>>> Clearly, there are injections satisfying [1] and [2],
>> e.g,
>>> a(n) = n(n+1)/2.
>>>
>>> Is there a lexicographically smallest injection
>> satisfying
>>> [1] and [2]?
>> Yes, and a simple backtracking algorithm can find any
>> number of initial terms.  The initial terms are proved
>> correct whenever the last value reaches a new maximum or
>> when there is an allowed path from the last value to a new
>> maximum (because the terms can be extended to an injection
>>
>> First 100 terms:
>> 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
>>
>> The sequence has a simple structure up to at least 10^6:
>> a(n) = a(n-1) + n iff n is odd or n=2*3^k
>> a(n) = a(n-1) - n otherwise
>> a(2*3^k + 2m) = 5*3^k - 2 - m, for 0 <= m < 2*3^k
>> a(2*3^k + 2m + 1) = 7*3^k - 1 + m, for 0 <= m <
>> 2*3^k
>> Proof anyone?
>>
>> Martin Fuller

I confirm this sequence for n <= 10^8.

For your sequence, it is easy to show that

a(n) >= 0
|a(n)-a(n-1)| = n
a is an injection

It remains only to show that a is the lexically first sequence
satisfying these criteria. This requires you to show that a(n) is the
lexically best choice for each n. For those n with a(n) = a(n-1)-n, this
is trivial. For the remaining n, specifically, n = 2*3^k or n odd, you
must show that choosing a(n) = a(n-1)-n leads to a repeat value.
Computer investigation suggest that this repeat value occurs within 5
iterations of a on n, so this proof should be tedious but not too
difficult. In other words, I am convinced that Fuller's sequence is correct.

```