A396604 Lexicographically earliest sequence of distinct positive integers whose binary values, when written on a square spiral, one bit per square, high order bits first, contain no pair of 1 bits that are a knight's move apart.

1, 2, 8, 131072, 10, 3, 16, 4, 5, 6, 9, 32, 64, 256, 128, 65536, 34, 4096, 130, 11, 17, 12, 40, 42, 18, 19, 13, 24, 136, 4112, 138, 272, 2048, 512, 160, 1024, 162, 168, 132, 5120, 20, 66, 21, 25, 68, 170, 514, 528, 65, 14, 257, 258, 273, 33, 520, 522, 80, 82, 4352, 84

Offset

1,2

Comments

After a(1) = 1 when determining the next term in the sequence one must not only ensure that it contains no 1 bits that are a knight's move apart from any previous 1 bit, including the earlier 1 bits in the term itself, but also that the next square after the end of the term is not a knight's move apart from any previous 1 bit as the next term must begin with a 1 bit.

It is conjectured that the sequence contains all positive integers.

Links

Scott R. Shannon, Table of n, a(n) for n = 1..1000

Scott R. Shannon, Image of the first 1000 terms on the square spiral. The 1 bits are black while the 0 bits are light gray. The bits that comprise each term are connected by a red line.

Example

The spiral begins:
.
                                .
    1---0---0---0---0---1---1   1
    |                       |   |
    0   0---0---0---0---0   1   0
    |   |               |   |   |
    0   0   0---1---0   0   0   0
    |   |   |       |   |   |   |
    1   0   0   1---1   0   1   0
    |   |   |           |   |   |
    0   0   0---1---0---0   0   0
    |   |                   |   |
    1   0---0---0---0---0---1   0
    |                           |
    1---1---0---1---0---0---1---1
.
a(1) = 1 by definition.
a(2) = 2 as the 2nd square is not a knight's move away from the 1st square that contains a 1 bit, while the 4th square, the next square after the end of a(2) = 2, can contain a 1 bit as it is not a knight's move away from any existing 1 bit.
a(4) = 131072. This term must be 3 or more but it cannot end on the 9th, 10th, 11th, ... 23rd, 24th square as the next square to all of these is a knight's move away from a square containing a 1 bit. This leaves the 25th square are the earliest square a(4) can end on as the 26th square can contain a 1 bit as it is not a knight's move away from any other square containing a 1 bit. This leaves 131072 = 2^17 as the first number satisfying these conditions.

Crossrefs

Cf. A396603 (start at 0), A007088, A396607, A396608, A394166.

Sequence in context: A256065 A081979 A012672 * A024340 A012667 A124075

Adjacent sequences: A396601 A396602 A396603 * A396605 A396606 A396607

Keyword

nonn,base

Author

Scott R. Shannon, May 30 2026

Status

approved