[seqfan] R: Re: Knight's tours

[Mason John]

Brad
Thanks for your reply.
My idea was that my algorithm would produce ordered values without any need of sorting.
I have since realised (and your mail helped me focus on this) that the wording of my post would make that difficult.
To make my idea workable, I would certainly need to define that the first move represented by the string referred to a move made from position a1 (or coordinates (0,0)).
I don't know if that is enough, so I won't be posting anything until I'm sure.
john


-----Messaggio originale-----
Da: SeqFan <seqfan-bounces at list.seqfan.eu> Per conto di Brad Klee
Inviato: sabato 2 febbraio 2019 23:45
A: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Oggetto: [seqfan] Re: Knight's tours

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,
> 1111234545711163546147611147116555252256711611252755525585711186313555
> 478181325575346818146183245556
>
> Interesting?
>
> john
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/

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