[seqfan] Re: Recaman observation

[Martin Fuller]

> From: David Wilson <dwilson at gambitcomm.com>
> Subject: [seqfan] Re: Recaman observation
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Date: Friday, 17 July, 2009, 2:40 PM
> Martin Fuller wrote:
> > Correction for Recaman sequence and new sequence:
> > [1] a(n) > 0
> 
> A005132 has a(0) = 0.

You are right - I should have added a(0)=0 to my calculated values.  The conjectured formulas still hold up to 10^6.

> > 
> >> 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
> >> 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
> 
> 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.
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
>