[seqfan] Re: Is this sequence related to A046901?

[Ali Sada]

 Hi David,
Thank you very much for your response and for the great analysis, as usual. And you are correct. The default vertical move is downward unless there is a possibility of touching the x-line.
Now, my question to the editors is: should this be a separate sequence or a comment on A046901? 
(In both cases I will need your help!)
Best,
Ali   

    On Tuesday, March 30, 2021, 10:44:31 AM GMT+1, David Seal <david.j.seal at gwynmop.com> wrote:  
 
 Hi Ali,

What you haven't told us is how the object decides whether to make its vertical steps within move N upwards or downwards. The simplest rule I can see that is compatible with your picture is that it makes them downwards if doing so will result in the y co-ordinate remaining strictly greater than zero, and otherwise it makes them upwards.

Assuming that's the intended sequence, first define a sequence d(n) = 1 if the first step in move n is vertical, or -1 if that first step is horizontal. You've told us that d(1) = 1, and it follows easily that in general, d(n) = 1 if n is 0 or 1 mod 4, or -1 if n is 2 or 3 mod 4.

Now define v(n) to be the number of vertical steps in move n. If n is even, v(n) = n/2; if n is odd, splitting into the two cases of the first move in step n being horizontal or vertical leads to the common conclusion that v(n) = (n+d(n))/2. Splitting into the four cases mod 4, we get:

v(4i) = 4i/2 = 2i
v(4i+1) = ((4i+1)+1)/2 = 2i+1
v(4i+2) = (4i+2)/2 = 2i+1
v(4i+3) = ((4i+3)-1)/2 = 2i+1

Your sequence a(n) is then defined by a(1) = 1, a(n+1) = a(n)-v(n+1) if a(n) > v(n+1), or a(n)+v(n+1) if a(n) <= v(n+1). Since the values of v(n) never decrease as n increases, that implies that a(n) never exceeds 2v(n), which in turn implies that if v(n+1) = v(n+2), then either a(n+1) = a(n)+v(n+1) and a(n+2) = a(n+1)-v(n+2) = a(n+1)-v(n+1) or a(n+1) = a(n)-v(n+1) and a(n+2) = a(n+1)+v(n+2) = a(n+1)+v(n+1), so that a(n+2) = a(n) in either case. It follows from that and the above formulae for v(n) that a(4i+2) = a(4i) and a(4i+3) = a(4i+1) for all i.

That explains the repetitions you see in your sequence, and if we restrict our attention to the terms it doesn't tell us are repeated by defining A(2i) = a(4i) and A(2i+1) = a(4i+1), we get:

A(2i) = a(4i) = a(4i-1) - v(4i) = a(4i-3) - 2i = A(2i-1) - 2i if A(2i-1) > 2i
A(2i) = a(4i) = a(4i-1) + v(4i) = a(4i-3) + 2i = A(2i-1) + 2i if A(2i-1) <= 2i

A(2i+1) = a(4i+1) = a(4i) - v(4i+1) = a(4i) - (2i+1) = A(2i) - (2i+1) if A(2i) > 2i+1
A(2i+1) = a(4i+1) = a(4i) + v(4i+1) = a(4i) + (2i+1) = A(2i) + (2i+1) if A(2i) > 2i+1

That shows that the sequence A(n) obeys the recurrence in the definition of A046901, and together with A(1) = a(1) = 1, that A(n) = A046901(n).

David


> On 18/03/2021 22:35 Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> 
>  
> Hi Everyone,
> 
> An object is moving starting from the origin while avoiding touching the x axis. Move n has n unit steps. The object starts by moving up one step. All the moves after that alternate between a horizontal step (only to the right) and vertical step (up or down but without going back). Also, the object cannot change direction within the same move. For example, in move 5, it moves up, right, up, right, up. It cannot go down. This pic might explain better
> https://imgur.com/a/bUrbchD
> 
> The sequence is the y coordinate of the last step in each move.  
> 
> 1, 2, 1, 3, 6, 3, 6, 2, 7, 2, 7, 1, 8, 1, 8, 16, 7,16, 7
> 
> Without repetition, this sequence seems like A046901. Is this a correct assumption? 
> 
> Best,
> 
> Ali
> 
> 
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/

--
Seqfan Mailing list - http://list.seqfan.eu/