cp's OEIS Frontend

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

%I A274640 #154 Feb 02 2025 04:29:46
%S A274640 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 A274640 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 A274640 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 A274640 Counterclockwise square spiral constructed by greedy algorithm, so that each row, column, and diagonal contains distinct numbers.
%C A274640 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 A274640 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 A274640 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 A274640 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 A274640 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 A274640 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 A274640 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 A274640 Alois P. Heinz, <a href="/A274640/b274640.txt">Table of n, a(n) for n = 0..20000</a>
%H A274640 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 A274640 Alois P. Heinz, <a href="/A274640/a274640_3.jpg">Distribution of a(n) for n <= 4010000</a>
%H A274640 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 A274640 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 A274640 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 A274640 Zak Seidov, <a href="/A274640/a274640_4.jpg">Distribution of a(n) for first 20001 terms</a>
%e A274640 The spiral begins:
%e A274640 .
%e A274640    9--16---2---4---7--14--11--12---1---5---8
%e A274640    |                                       |
%e A274640   17   8--15--14--13--12---9--10---6---7   3
%e A274640    |   |                               |   |
%e A274640    1   2   4--11--10---3---8---7---9  13  15
%e A274640    |   |   |                       |   |   |
%e A274640    8   9   7   3---5---6---1---2   4  12  11
%e A274640    |   |   |   |               |   |   |   |
%e A274640   11  12   8   1   2---4---3   6   5  10  14
%e A274640    |   |   |   |   |       |   |   |   |   |
%e A274640   15   7   6   5   3   1---2   4   8  11  12
%e A274640    |   |   |   |   |           |   |   |   |
%e A274640   14  10   3   2   4---5---6---1   7   9  13
%e A274640    |   |   |   |                   |   |   |
%e A274640    7  11   9   6---1---2---4---5---3   8  10
%e A274640    |   |   |                           |   |
%e A274640    4  13   5---7---8---9--10--11--12---6   1
%e A274640    |   |                                   |
%e A274640   12  14--10---9---6--13---5---3--15--16---7
%e A274640    |
%e A274640   10--15---1--12--16---8--14--13--11--18--17
%e A274640 .
%e A274640 The 8 spokes (A274924-A274931) begin:
%e A274640   E:  1, 2, 4,  8, 11, 12, 16,  9, 19, 24, 22, ...
%e A274640   NE: 1, 3, 2,  9,  7,  8, 12, 15, 13, 17, 20, ...
%e A274640   N:  1, 4, 6,  3, 12, 14, 15, 18, 20, 26, 25, ...
%e A274640   NW: 1, 2, 3,  4,  8,  9,  7, 11, 14, 10, 22, ...
%e A274640   W:  1, 3, 5,  6,  7, 15, 10, 17, 13, 25, 14, ...
%e A274640   SW: 1, 4, 6,  5, 14, 10, 11, 23, 16, 18, 21, ...
%e A274640   S:  1, 5, 2,  9, 13,  8,  7, 11, 10, 17, 19, ...
%e A274640   SE: 1, 6, 5, 12, 16, 17, 21, 24, 27, 13, 15, ...
%p A274640 #  Maple program from _Alois P. Heinz_, Jul 12 2016:
%p A274640 fx:= proc(n) option remember; `if`(n=1, 0, (k->
%p A274640        fx(n-1)+sin(k*Pi/2))(floor(sqrt(4*(n-2)+1)) mod 4))
%p A274640      end:
%p A274640 fy:= proc(n) option remember; `if`(n=1, 0, (k->
%p A274640        fy(n-1)-cos(k*Pi/2))(floor(sqrt(4*(n-2)+1)) mod 4))
%p A274640      end:
%p A274640 b:= proc() 0 end:
%p A274640 a:= proc(n) local x,y,s,i,t,m;
%p A274640       x, y:= fx(n+1), fy(n+1);
%p A274640       if b(x, y) > 0 then b(x, y)
%p A274640     else s:={};
%p A274640     for i do t:=b(x+i,y+i); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x-i,y-i); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x+i,y-i); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x-i,y+i); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x+i,y  ); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x-i,y  ); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x  ,y+i); if t>0 then s:=s union {t} else break fi od;
%p A274640     for i do t:=b(x  ,y-i); if t>0 then s:=s union {t} else break fi od;
%p A274640          for m while m in s do od;
%p A274640          b(x,y):= m
%p A274640       fi
%p A274640     end:
%p A274640 seq(a(n), n=0..1000);
%t A274640 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 A274640 For[i=1, True, i++, t=b[x+i, y+i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x-i, y-i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x+i, y-i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x-i, y+i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x+i, y  ]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x-i, y  ]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x  , y+i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 For[i=1, True, i++, t=b[x  , y-i]; If[t>0, s=Union[s,{t}], Break[]]];
%t A274640 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_ *)
%o A274640 (Python)
%o A274640 class Lines: # manage lines in direction d = dx + dy*1j
%o A274640     def __init__(self, d):
%o A274640         self.lines={}; self.t = d.real/d.imag if d.imag else None
%o A274640     def __call__(self, pos): # Return the line through pos in direction d
%o A274640         index = pos.imag if self.t is None else pos.real - pos.imag*self.t
%o A274640         if index not in self.lines: self.lines[index] = Values()
%o A274640         return self.lines[index]
%o A274640 class Values(set): # the set of used numbers on a given line
%o A274640     def next(self, n): # return least k >= n not on this line
%o A274640         return min(m+1 for m in self if m+1 >= n and m+1 not in self
%o A274640                    ) if n in self else n
%o A274640 def A274640(): # generator of the sequence, see below for possible usage
%o A274640     lines = [Lines(d) for d in (1, 1+1j, 1j, 1-1j)]; pos = 0
%o A274640     for side in range(9**9):
%o A274640         for _ in range(side//2 + 1):
%o A274640             n = 1; lines_here = [L(pos) for L in lines]
%o A274640             while any(n < (n := L.next(n)) for L in lines_here): pass
%o A274640             yield n; any(L.add(n) for L in lines_here); pos += 1j**side
%o A274640 [a for a,_ in zip(A274640(),range(99))] # _M. F. Hasler_, Feb 01 2025
%Y A274640 Cf. A274641 (the same spiral, but starting with 0 not 1), A174344, A274923.
%Y A274640 The 8 spokes are A274924-A274931.
%Y A274640 The East-West axis is A275877 (see also A324680), the North-South axis is A276036.
%Y A274640 Positions of 1's and 2's give A273059 and A275116.
%Y A274640 In the same spirit as the infinite Sudoku array A269526.
%Y A274640 Cf. A324481 (position of first n).
%Y A274640 Cf. A274821 (the same construction on a hexagonal tiling).
%K A274640 nonn,nice
%O A274640 0,2
%A A274640 _Zak Seidov_ and _Kerry Mitchell_, Jun 30 2016
%E A274640 Corrected and extended by _Alois P. Heinz_, Jul 12 2016