[seqfan] Re: Recaman observation

[Martin Fuller]

> 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
> [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 by adding n forever).

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
Which leads to:
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