A396608 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 diagonally adjacent.

1, 8, 16, 2, 3, 10, 4, 5, 6, 128, 32, 256, 17, 9, 18, 7, 24, 11, 12, 26, 33, 130, 512, 4096, 34, 144, 14, 20, 13, 22, 19, 15, 21, 64, 66, 288, 32768, 4608, 65, 28, 72, 129, 36, 25, 23, 30, 132, 27, 35, 640, 74, 37, 96, 524288, 68, 32800, 67, 48, 40, 384, 42, 29, 38

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 diagonally adjacent to 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 diagonally adjacent to 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:
.
                                .
    0---1---0---0---0---0---0   1
    |                       |   |
    0   1---0---1---1---1   0   1
    |   |               |   |   |
    0   0   0---0---0   0   0   0
    |   |   |       |   |   |   |
    0   1   1   1---1   1   1   0
    |   |   |           |   |   |
    0   0   0---0---0---0   0   0
    |   |                   |   |
    1   0---1---0---1---1---1   1
    |                           |
    0---0---0---0---0---0---0---0
.
a(1) = 1 by definition.
a(2) = 8. As the second number must start with a 1, and as the first number is 1, the 3rd, 4th and 5th squares cannot be 1 else they would be diagonally adjacent to one of the first two 1 bits. The 6th bit can be 1, which is the first bit that can start the third term, so a(2) = 8 = 1000 as it has 0 bits in the 3rd, 4th and 5th squares while allowing a 1 bit in the 6th square.
a(3) = 16. Similar to a(2) = 8, the 7th, 8th, 9th, and 10th square cannot be 1 while the 11th square can be, giving 16 as the earliest term satisfying these conditions.

Crossrefs

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

Sequence in context: A028585 A387555 A073926 * A392530 A073925 A053321

Adjacent sequences: A396605 A396606 A396607 * A396609 A396610 A396611

Keyword

nonn,base

Author

Scott R. Shannon, May 31 2026

Status

approved