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

[David Seal]

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/