login
Counterclockwise square spiral constructed by greedy algorithm, so that each row, column, and diagonal contains distinct numbers.
52

%I #147 Sep 13 2020 02:22:19

%S 1,2,3,4,2,3,4,5,6,1,4,6,2,1,6,5,3,1,5,2,6,1,2,4,5,3,7,8,5,4,9,7,8,3,

%T 10,11,4,7,8,6,3,9,5,7,8,9,10,11,12,6,8,9,11,10,12,13,7,6,10,9,12,13,

%U 14,15,8,2,9,12,7,10,11,13,14,10,9,6,13,5,3,15,16,7,1,10,13,12,14,11,15,3,8,5,1,12,11,14,7,4,2,16,9,17,1,8,11

%N Counterclockwise square spiral constructed by greedy algorithm, so that each row, column, and diagonal contains distinct numbers.

%C Presumably every row, column, and diagonal is a permutation of the natural numbers, but is there a proof? - _N. J. A. Sloane_, Jul 10 2016

%C The n-th cell in the spiral has coordinates x = A174344(n+1), y = A274923(n+1). - _N. J. A. Sloane_, Jul 11 2016

%C From _Robert G. Wilson v_, Dec 25 2016: (Start) [Memo: all these numbers need to decreased by 1, since the offset here is 0. See A324481. - _N. J. A. Sloane_, Jul 23 2017. Furthermore, the numbers don't seem correct, even after subtracting 1. - _N. J. A. Sloane_, Jul 04 2019]

%C Index of first appearance of k = 1,2,3,...: 1, 2, 3, 7, 8, 15, 17, 25, 35, 41, 47, 61, 62, 89, 98, 99, 121, 129, 130, 143, 197, 208, 225, 239, 271, ..., .

%C 1 appears at: 1, 4, 12, 19, 22, 33, 42, 68, 79, 120, 179, 194, 302, 311, 445, 489, 511, 558, 630, 708, 847, 877, 907, ..., .

%C 2 appears at: 2, 5, 9, 16, 48, 52, 70, 73, 88, 95, 110, 146, 280, 291, 309, 327, 488, 605, 656, 681, 735, 778, 1000, ..., .

%C 3 appears at: 3, 6, 10, 23, 29, 36, 56, 76, 97, 105, 153, 168, 184, 252, 338, 437, 457, 670, 818, 906, 953, 967, ..., . (End).

%H Alois P. Heinz, <a href="/A274640/b274640.txt">Table of n, a(n) for n = 0..20000</a>

%H F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p52/8039">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.

%H Alois P. Heinz, <a href="/A274640/a274640_3.jpg">Distribution of a(n) for n <= 4010000</a>

%H Kerry Mitchell, <a href="/A274640/a274640.jpg">Color-coded version of spiral, (1): the colors represent the values, from black (small) to white (large)</a> (jpg file, low resolution)

%H Kerry Mitchell, <a href="/A274640/a274640_1.tiff">Color-coded version of spiral, (1a): the colors represent the values, from black (small) to white (large)</a> (tiff file, much higher resolution)

%H Kerry Mitchell, <a href="/A274640/a274640_1.jpg">Color-coded version of spiral, (2): values <= 100 are black and those > 100 are white.</a>

%H Zak Seidov, <a href="/A274640/a274640_4.jpg">Distribution of a(n) for first 20001 terms</a>

%e The spiral begins:

%e .

%e 9--16---2---4---7--14--11--12---1---5---8

%e | |

%e 17 8--15--14--13--12---9--10---6---7 3

%e | | | |

%e 1 2 4--11--10---3---8---7---9 13 15

%e | | | | | |

%e 8 9 7 3---5---6---1---2 4 12 11

%e | | | | | | | |

%e 11 12 8 1 2---4---3 6 5 10 14

%e | | | | | | | | | |

%e 15 7 6 5 3 1---2 4 8 11 12

%e | | | | | | | | |

%e 14 10 3 2 4---5---6---1 7 9 13

%e | | | | | | |

%e 7 11 9 6---1---2---4---5---3 8 10

%e | | | | |

%e 4 13 5---7---8---9--10--11--12---6 1

%e | | |

%e 12 14--10---9---6--13---5---3--15--16---7

%e |

%e 10--15---1--12--16---8--14--13--11--18--17

%e .

%e The 8 spokes (A274924-A274931) begin:

%e E: 1, 2, 4, 8, 11, 12, 16, 9, 19, 24, 22, ...

%e NE: 1, 3, 2, 9, 7, 8, 12, 15, 13, 17, 20, ...

%e N: 1, 4, 6, 3, 12, 14, 15, 18, 20, 26, 25, ...

%e NW: 1, 2, 3, 4, 8, 9, 7, 11, 14, 10, 22, ...

%e W: 1, 3, 5, 6, 7, 15, 10, 17, 13, 25, 14, ...

%e SW: 1, 4, 6, 5, 14, 10, 11, 23, 16, 18, 21, ...

%e S: 1, 5, 2, 9, 13, 8, 7, 11, 10, 17, 19, ...

%e SE: 1, 6, 5, 12, 16, 17, 21, 24, 27, 13, 15, ...

%p # Maple program from _Alois P. Heinz_, Jul 12 2016:

%p fx:= proc(n) option remember; `if`(n=1, 0, (k->

%p fx(n-1)+sin(k*Pi/2))(floor(sqrt(4*(n-2)+1)) mod 4))

%p end:

%p fy:= proc(n) option remember; `if`(n=1, 0, (k->

%p fy(n-1)-cos(k*Pi/2))(floor(sqrt(4*(n-2)+1)) mod 4))

%p end:

%p b:= proc() 0 end:

%p a:= proc(n) local x,y,s,i,t,m;

%p x, y:= fx(n+1), fy(n+1);

%p if b(x, y) > 0 then b(x, y)

%p else s:={};

%p for i do t:=b(x+i,y+i); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x-i,y-i); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x+i,y-i); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x-i,y+i); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x+i,y ); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x-i,y ); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x ,y+i); if t>0 then s:=s union {t} else break fi od;

%p for i do t:=b(x ,y-i); if t>0 then s:=s union {t} else break fi od;

%p for m while m in s do od;

%p b(x,y):= m

%p fi

%p end:

%p seq(a(n), n=0..1000);

%t fx[n_] := fx[n] = If[n == 1, 0, Function[k, fx[n-1] + Sin[k*Pi/2]][Mod[Floor[Sqrt[4*(n-2)+1]], 4]]]; fy[n_] := fy[n] = If[n == 1, 0, Function[k, fy[n-1] - Cos[k*Pi/2]][Mod[Floor[Sqrt[4*(n-2)+1]], 4]]]; Clear[b]; b[_, _] = 0; a[n_] := Module[{x, y, s, i, t, m}, {x, y} = {fx[n+1], fy[n+1]}; If[b[x, y] > 0, b[x, y], s = {};

%t For[i=1, True, i++, t=b[x+i, y+i]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x-i, y-i]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x+i, y-i]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x-i, y+i]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x+i, y ]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x-i, y ]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x , y+i]; If[t>0, s=Union[s,{t}], Break[]]];

%t For[i=1, True, i++, t=b[x , y-i]; If[t>0, s=Union[s,{t}], Break[]]];

%t m = 1; While[MemberQ[s, m], m++]; b[x, y] = m]]; Table[a[n], {n, 0, 1000}] (* _Jean-François Alcover_, Nov 14 2016, after _Alois P. Heinz_ *)

%Y Cf. A274641 (the same spiral, but starting with 0 not 1), A174344, A274923.

%Y The 8 spokes are A274924-A274931.

%Y The East-West axis is A275877 (see also A324680), the North-South axis is A276036.

%Y Positions of 1's and 2's give A273059 and A275116.

%Y In the same spirit as the infinite Sudoku array A269526.

%Y Cf. A324481 (position of first n).

%Y Cf. A274821 (the same construction on a hexagonal tiling).

%K nonn,nice

%O 0,2

%A _Zak Seidov_ and _Kerry Mitchell_, Jun 30 2016

%E Corrected and extended by _Alois P. Heinz_, Jul 12 2016