A396604 - OEIS

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.

%I #8 Jun 02 2026 12:56:10

%S 1,2,8,131072,10,3,16,4,5,6,9,32,64,256,128,65536,34,4096,130,11,17,

%T 12,40,42,18,19,13,24,136,4112,138,272,2048,512,160,1024,162,168,132,

%U 5120,20,66,21,25,68,170,514,528,65,14,257,258,273,33,520,522,80,82,4352,84

%N 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.

%C 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.

%C It is conjectured that the sequence contains all positive integers.

%H Scott R. Shannon, <a href="/A396604/b396604.txt">Table of n, a(n) for n = 1..1000</a>

%H Scott R. Shannon, <a href="/A396604/a396604.png">Image of the first 1000 terms on the square spiral</a>. The 1 bits are black while the 0 bits are light gray. The bits that comprise each term are connected by a red line.

%e The spiral begins:

%e .

%e 1---0---0---0---0---1---1 1

%e | | |

%e 0 0---0---0---0---0 1 0

%e | | | | |

%e 0 0 0---1---0 0 0 0

%e | | | | | | |

%e 1 0 0 1---1 0 1 0

%e | | | | | |

%e 0 0 0---1---0---0 0 0

%e | | | |

%e 1 0---0---0---0---0---1 0

%e | |

%e 1---1---0---1---0---0---1---1

%e .

%e a(1) = 1 by definition.

%e 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.

%e 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.

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

%K nonn,base

%O 1,2

%A _Scott R. Shannon_, May 30 2026