A345967 Lexicographically first sequence of distinct positive integers such that the alternating partial sums p(n) = Sum_{k=1..n} -(-1)^k a(k), n >= 1, are distinct positive integers.

2, 1, 5, 3, 6, 4, 7, 8, 12, 9, 11, 10, 15, 13, 17, 14, 16, 18, 22, 19, 21, 20, 25, 23, 26, 24, 28, 27, 30, 29, 32, 31, 35, 33, 36, 34, 37, 38, 42, 39, 43, 40, 44, 41, 45, 47, 46, 48, 55, 49, 51, 50, 53, 52, 57, 54, 56, 58, 62, 59, 63, 60, 64, 61, 65, 67, 66, 68, 74, 69, 72, 70, 75, 71, 73, 76, 79, 77, 80, 78

Offset: 1

Author

Eric Angelini and Neil Bickford, Jun 30 2021

Keywords

• nonn

Comments

The chess rook as a windshield wiper sequence: terms with an odd index [a(1), a(3), a(5), ...] move the chess rook horizontally to the right over a(n) terms; terms with an even index [a(2), a(4), a(6), ...] move the chess rook to the left over a(n) terms; this is the lexicographically earliest sequence of positive distinct terms such that all terms of the sequence will be visited exactly once by the rook.

It turns out that both, sequence (a(n), n >= 1) and that of partial alternating sums (p(n), n >= 1), are permutations of the positive integers. - M. F. Hasler, Jul 11 2021

The inverse permutation of this sequence starts (2, 1, 4, 6, 3, 5, 7, 8, 10, 12, 11, 9, 14, 16, 13, 17, 15, 18, 20, 22, 21, ...). - M. F. Hasler, Jul 19 2021

Examples

			As a(1) = 2 has an odd index, the rook moves 2 terms to the Right on a(3) = 5;
from there the rook moves according to a(2) = 1 (1 term to the L) on a(2) = 1;
from there the rook moves according to a(3) = 5 (5 terms to the R) on a(7) = 7;
from there the rook moves according to a(4) = 3 (3 terms to the L) on a(4) = 3;
from there the rook moves according to a(5) = 6 (6 terms to the R) on a(10) = 9; etc. The rook's successive movements can be seen as the movements of a windshield wiper.
		

Links

• Eric Angelini, La tour d'échecs et l'essuie-glace, Cinquante signes, 2021.
• Eric Angelini, La tour d'échecs et l'essuie-glace, Cinquante signes, 2021. [Cached copy]
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A285471.

Programs

PARI

A345967_vec(Nmax, P=0)={ my(US=[0], UP=[P], used(x,U)= setsearch(U,x) || x<=U[1], insert(x,U)= U=setunion(U,[x]); while(#U>1&&U[2]==U[1]+1, U=U[^1]); U); vector(Nmax, n, my(s=(-1)^n); for(S=US[1]+1,oo, (used(S,US) || used(P-s*S,UP))&&next; if(s<0, my(f=1); for(PP=UP[1]+1,P+S-1, used(PP,UP) || used(P+S-PP,US) || PP==P || [f=0; break]); f && next); UP=insert(P-=s*S, UP); US=insert(s=S, US); break); s)} \\ M. F. Hasler, Jul 11 2021

Extensions

Edited and better definition from M. F. Hasler, Jul 19 2021