[seqfan] Re: Knight's tours

[Brad Klee]

Hi John,

Sequences like these would build upon content already in OEIS, so it
seems like yes, your proposals at least meet a first criterion of interest.

However, I would be wary of starting with such complicated results.
It's much easier to doubt an ordering of 26,534,728,821,064 elements,
than say an ordering with A070030(6) = 176 elements. In the case of
A070030, for the first few terms, you can easily brute force the whole
set and then apply a sort algorithm. In the case of your Sequence 2,
probably not. So how is your algorithm proven correct?

It's possible to limit the variables even more if we go to A048116.
For each a(n), n>1, list out valid walks as 2(n-1)-digit binary numbers,
encode from binary digits to integers, and sort by less than. This
gives an irregular triangle:

1, 2;
5, 6, 9, 10;
19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44;
75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113,
                  114, 116, 139, 141, 142, 147, 149, 150, 153, 154, 156,
                  163, 165, 166,169, 170, 172, 177, 178, 180;

with row lengths from A048116. One advantage of working with shorter
runs on only two steps is that the enciphering has integers with far
fewer digits.

The proposal is also reminiscent of A163540, and if your goal is to extend
upon A246559, how about the following:

Up to term a(16^n-1), partial sums of A163540 describe a finite curve that
covers a 4^n by 4^n square subset of Z^2 . A countably-infinite set of
polyominos follows by drawing a solid boundary around each n^th
square. For example, n=3:

https://ptpb.pw/BQgi.png

These polyominos could be ordered and submitted as a subsequence of
A246559. The first few terms would be 0 for the monomino, 181 for the
T-pentomino, and 413 for the y-hexomino. In A246559, these are the
terms a(1), a(21), and a(53).

Why should we care? Given a definition of the Polyomino trees,
it becomes possible to use the ruler sequence A001511 to construct
the Hilbert curve as a limit-periodic tiling. This strengthens an analogy
with other similar substitution systems such as the chair tiling.

Cheers,

Brad


On Tue, Jan 29, 2019 at 8:49 AM Mason John <john.mason at lispa.it> wrote:
>
> Dear Seqfans
>
> A few years ago, a sequence was posted containing the representations of free polyominoes (A246559).
> Following that idea, this post concerns the representations of closed knight's tours.
> Any tour may be represented by a series of digits, between 1 and 8, such that 1 corresponds to some direction of the knight, say north-north-east, then 2 is east-north-east and so on.
>
> So possible sequences could be:
>
> Sequence 1: Lexicographically minimal sequence of 64 moves of a knight forming a closed tour on an 8 by 8 chessboard.
> 1,1,1,2,3,5,4,5,7,1,1,1,6,3,5,4,6,1,4,7,6,1,1,1,4,7,1,6,5,5,2,5,6,8,1,3,1,8,6,5,3,5,8,1,8,3,2,5,8,6,3,8,5,4,5,3,1,1,4,2,5,6,7,6
>
> Sequence 2: 64-digit representations of closed knight's tours in ascending order.
>
> 1112354571116354614761114716552568131865358183258638545311425676,
> 1112354571116354614761114716552568182416745412425685718146124556,
> 1112354571116354614761114716552568182416745412557181461245325676,
> 1112354571116354614761114716552568182416745417124588545311425676,
> 1112354571116354614761114716552568182416745425718143671245325676
>
> Sequence 3: Closed knight's tours on 2n by 2n chessboards having minimal representations, for n >= 3.
> 112546147257618235618527453218527654,
> 1112354571116354614761114716552568131865358183258638545311425676,
> 1111234545711163546147611147116555252256711611252755525585711186313555478181325575346818146183245556
>
> Interesting?
>
> john
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/