[seqfan] Re: Recaman observation

[Martin Fuller]

Correction for Recaman sequence and new sequence:
[1] a(n) > 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 ***
> > [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