|
| |
|
|
A363372
|
|
Lexicographically earliest infinite sequence of positive numbers on a square spiral such that every 3 by 3 block of numbers contains the digits 1 through 9.
|
|
1
|
|
|
|
1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 6, 7, 5, 8, 9, 7, 8, 2, 3, 9, 2, 5, 4, 3, 7, 1, 8, 4, 1, 9, 4, 6, 2, 1, 6, 3, 1, 9, 4, 1, 8, 4, 1, 3, 6, 1, 2, 6, 4, 2, 3, 9, 2, 3, 8, 2, 3, 1, 7, 3, 4, 5, 2, 4, 5, 6, 7, 5, 6, 7, 5, 6, 7, 8, 9, 7, 8, 9, 5, 8, 9, 5, 6, 7, 5, 6, 7, 5, 6, 7, 5, 8, 9, 5, 8, 9, 7, 8, 9
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The numbers are determined by a recursive backtracking search starting from a(1) = 1. Additional optimization of available candidate values is achieved by checking the undetermined squares on the spiral that will form part of the 3 x 3 block of numbers the term currently being determined lies in; these are checked for numbers that they cannot contain and comparing those with similar values in other undetermined squares in the same 3 by 3 block. If all of these squares contain the same excluded value or values then these form the list of candidate numbers the current square must contain. If no such excluded shared value exists then the current square's list of candidate values is all those numbers that are not excluded by its neighbors in any surrounded 3 by 3 block of numbers.
Although significant backtracking is required using the above algorithm one finds that the resulting numbers form a repeating pattern of three values in three rows and columns in each of the four orthogonal quadrants around the starting square; this implies the sequence is indeed infinite in the resulting pattern of rows and columns. See the attached colored image. One finds, assuming a counter-clockwise numbered spiral, that the only repeating rows or columns that cross the quadrant boundaries are the column of values 5,6,7,5,6,7,5... on the left side of the spiral relative to the starting square, and the column 5,7,6,5,7,6,5,... on the right side.
|
|
|
LINKS
|
Scott R. Shannon, Image of the first 5042 terms on the square spiral. The numbers 1 through 9 are colored white, red, orange, yellow, green, blue, indigo, violet, light gray respectively, except for the initial start square which is colored black for clarity.
|
|
|
EXAMPLE
|
a(17) = 8. This is the first term that is determined by considering the excluded values of the other undetermined squares in the current 3 by 3 block. As a(8) = 8, at coordinate (0,-1) relative to the starting square, 8 is excluded as a possible candidate for a(18), at coordinate (-2,1), and a(19), at coordinate (-2,0). Therefore a(17), at coordinate (-2,2), must equal 8 as there is no other square in the current 3 by 3 block, centered at (-1,1), that can contain it.
a(32) = 6. This is the first term that fails the above checking of excluded candidates in the current 3 by 3 block, forcing the algorithm to backtrack when determining a(35). Using that check one finds that 2 is the smallest valid choice for a(32), followed by a(33) = 6 and a(34) = 1. But these choices leave a(35) having no available candidate value as all numbers 1 through 9 are already in its surrounding 3 by 3 blocks of values. This leaves a(32) = 6 as the next smallest candidate, a value that leads to a(35) also having 6 as a valid candidate.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
