La tour d'échecs et l'essuie-glace
Hello Math Fun,
we want this rook to visit exactly once
all terms of S, S being the lexicographically
earliest sequence of distinct nonnegative terms.
The rook starts to move Left 0 steps.
At every step we will now visit an unvisited
term of S, a bit like a windshield wiper moves:
The rook moves Right 2 steps.
Then Left 1 step.
R 5 steps
L 3
R 6
L 4
R 7 — L 8 — R 12 — L 9 — R 11 — L 10 — R 15 — L 13 — R 17 — L 16 …
The seq S = 0,
is not in the OEIS (modulo errors from the author).
Best,
É.
______________________________
math-fun mailing list -- math-fun@mailman.xmission.com
To unsubscribe send an email to math-fun-leave@mailman.xmission.com
Neil Bickford was quick to confirm the above terms, extend S and send a diagram:
I had some extra time on the train today, so I wrote a short program to
compute this sequence.
Assuming I've got everything correct, the first 101 terms of the sequence
(not counting the initial 0) are
{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,83,81,85,82,84,86,90,87,91,88,92,89,93,95,94,96,102,97,99,98,103}
and the partial sums/visited cells (including the initial 0) up to that point are
{0,2,1,6,3,9,5,12,4,16,7,18,8,23,10,27,13,29,11,33,14,35,15,40,17,43,19,47,20,50,21,53,22,57,24,60,26,63,25,67,28,71,31,75,34,79,32,78,30,85,36,87,37,90,38,95,41,97,39,101,42,105,45,109,48,113,46,112,44,118,49,121,51,126,55,128,52,131,54,134,56,139,58,143,61,145,59,149,62,153,65,157,68,161,66,160,64,166,69,168,70,173}
Here's a quick diagram showing how the rook moves over the first 50 segments:
https://neilbickford.com/files/ReversingPaths/reversePaths.png
It never quite seems to settle down into a regular pattern so far as I can tell.
Finally, here's a very basic C++ program to do depth-first search for this sequence - in case the formatting gets garbled, it's also available at https://neilbickford.com/files/ReversingPaths/main.cpp . For the above sequence, I had it compute 110 segments, then ignored the last few. Even then, I don't really have a proof that the above terms are correct, and that it won't eventually backtrack over them (...)
______________________________
Update, July 8th, on Math-Fun, by Fred Lunnon:
Angelini's Rook-Wiper Sequences
______________________________
After repeated microscopic inspection of Éric Angelini's introduction
and algorithmic illustration, some reverse engineering of Neil Bickford's
heroic C++ program, and multiple bouts of "guess-the-generator" spent staring
at its output, I hope finally to have dispelled my previous incomprehension
concerning this tantalising sequential chimaera --- I get it, and it's a peach!
(#0) Motivation:
The scenario suggesting this topic involves a rook starting from one corner
of an infinite chessboard, then leaping in alternate directions along one edge,
after the fashion of some (severely dysfunctional) vehicular screen-wiper.
No two leaps may cover the same distance; no cell may be visited more than once.
It is easily seen that the rook can continue to move indefinitely; can it in
the process also execute every size of leap, and/or eventually visit every cell?
(#1) Formal Definition:
Given some `leap' map U from |N to |N (natural numbers), denote by U'
the `cell' alternating partial sum
U'(n) = -\sum_{0 <= k <= n} (-1)^k U(k)
= - U(0) + U(1) - U(2) + ... +/- U(n) .
U has the "rook-wiper" property when both U, U' are injective; Angelini's
rook-wiper sequence S is defined as the lexicographically earliest such U
--- see #2.
(#2) Examples:
Original, S earliest ---
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
S(n) 0 2 1 5 3 6 4 7 8 12 9 11 10 15 13 17 14 16 18 22 19 21 20 25 23
S'(n) 0 2 1 6 3 9 5 12 4 16 7 18 8 23 10 27 13 29 11 33 14 35 15 40 17
Variant, T' earliest ---
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
T(n) 0 2 1 5 3 6 4 7 8 12 9 11 10 15 13 17 16 18 14 19 21 23 22 25 20
T'(n) 0 2 1 6 3 9 5 12 4 16 7 18 8 23 10 27 11 29 15 34 13 36 14 39 19
Sparse rook-wiper sequence ---
n 0 1 2 3 4 5 6 7 8 9 10 ... (2 k - 1) (2 k)
X(n) 0 4 1 8 3 16 7 32 15 64 31 ... (2 2^k) (2^k - 1)
X'(n) 0 4 3 11 8 24 17 49 34 98 67 ... (3 2^k + k - 3) (2 2^k + k - 2)
(#3) Existence & construction:
The sparse example X in #2 illustrates that infinite rook-wipers U exist;
whence it follows that the unique earliest one S also exists.
Furthermore X illustrates how for odd n , any initial segment U(0..n)
satisfying the constraints can always be continued indefinitely, via subsequent
escape to some arbitrarily large doublet U(n+1), U(n+2) of `fat' and `thin'
entries, satisfying
U(n+1) notin U(0..n) , U(n+2) notin U(0..n) ,
U'(n+1) notin U'(0..n) , U'(n+2) notin U'(0..n) ,
where
U'(n+1) - U'(n) = U(n+1) , U'(n+1) - U'(n+2) = U(n+2) .
It follows that any given odd-length segment of S can be computed finally
and directly, by selecting the earliest available doublet at each double step;
it is never necessary to backtrack from further trials at greater length.
(#4) Permutations:
Now a surprise emerges from hiding in plain sight: both S, S' appear
not merely injective but surjective, so yielding permutations of |N !
For example if n = 1000, 10000, segment S(0..n) yields an exact
permutation of interval (0..n) ; if n = 10000 the only deviation is at
S(100000) = 100003 . However S' is less strict: only about 70% of
S'(0..n) seems always to fall within (0..n) .
(#5) Asymptotics:
More specifically, I conjecture that as n -> oo , the ratios
n : min( k | k notin S(0..n) ) : max( k | k in S(0..n) )
: min( k | k notin S'(0..n) ) : max( k | k in S'(0..n) )
approach exact limits
1 : 1 : 1 : 1/sqrt2 : 1 + 1/sqrt2 ,
or approximately
1.0000 : 1.0000 : 1.0000 : 0.7071 : 1.7071 .
Any actual proof seems a distant prospect; perhaps some probabilistic argument
might assist in elucidating this remarkable behaviour?
(#6) Variations:
Don't go away, there's more to come! Contemplation of #3 suggests that
lexicographical ordering of U in the definition of S may have been perhaps
somewhat arbitrary: why not amend that, to consider instead the rook-wiper T
for which T' is lexicographically earliest? Comparing the resulting sequences
--- see #2 --- it becomes apparent that S,T seem practically indistinguishable:
equal for long stretches, sharing identical surjective and asymptotic behaviour,
and effectively highly localised deviations from the identity permutation.
Worse still, variant Q combining earliest doublet Q(2k-1),Q(2k) for k odd,
Q'(2k-1),Q'(2k) for k even, behaves similarly: eg. Q(n) = S(n) for n < 42 .
At which juncture, the well-known principle of engineer's induction makes it
inevitable to speculate that _every_ mixed strategy selecting earliest doublets
for either of U, U' delivers such a typical pair of rook-wiper permutations;
and this conjecture is supported by a computer tests involving random selection.
(#7) Permutation Questions:
More generally,
Let U, U' denote injections from |N to |N ,
and suppose that for all n in |N ,
U'(n) = - U(0) + U(1) - U(2) + ... +/- U(n) .
Is it true that U' is surjective (only) if U is?
Proofs and constructions of simple counter/examples are solicited!
(#8) Computer Program:
The final Test section of the MAGMA program source attached at
may quickly be edited to produce any of the permutation sequences above.
An adventurous user can customise dynamic doublet selection between between
earliest leap & cell, by modifying a Boolean function of the step number.
The complete program may be executed via copy-paste into a free online
calculator at
(#9) OEIS:
Surely this topic deserves at least a quartet of entries in OEIS, incorporating
sequences S,S',T,T' , a selective summary of the material above, and perhaps
Bickford's program and diagram.
Fred Lunnon, Maynooth 08/07/21
A rook as I know it moves in 4 directions, 2D, this here moves in only 2 directions, 1D, rather like a Turing machine going left and right on a 1D tape. I don't see why this is mentioning a rook... Why not a Queen, then?
RépondreSupprimer