A272259 - OEIS

%I #18 Jul 23 2017 14:59:51

%S 1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,31,18,7,29,20,16,9,27,

%T 22,14,2,23,26,10,15,1,8,28,21,4,32,17,19,30,6,3,13,12,24,25,11,5,20,

%U 29,7,18,31,33,16,9,27,22,14,2,23,26,10,15,1,3,13,12,4,32,17,8,28,21,15,34,30,19,6,10,26,23,2,14,22,27,9,16,33,31,18,7,29,20,5,11,25,24

%N Irregular triangle read by rows: Row n>=32 gives the smallest square loop, i.e., lexicographically earliest circular permutation of length n such that any two adjacent numbers sum to a perfect square.

%C T(n) gives the smallest Hamiltonian cycle in the corresponding undirected unweighted graph with n vertices and edges satisfying the square sum condition, so this is also a solution to the Traveling Salesman Problem.

%C There are no circular solutions for n < 32.

%C T(32) = A112663(k-1), 1 <= k <= 32.

%C Row n has length n, and we start with row n = 32.

%H Martin Renner, <a href="/A272259/b272259.txt">Table of n, a(n) for n = 32..663</a>

%e Table starts with

%e n = 32: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15.

%e n = 33: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15.

%p with(GraphTheory):

%p n:=32; # Vertices from 1 to n

%p E:={}: # Edges

%p for a from 1 to n do

%p   for b from a+1 to n do

%p     if type(sqrt(a+b),integer) then E:={op(E),{a,b}}: fi:

%p   od:

%p od:

%p G:=Graph(E);

%p T||n:=TravelingSalesman(G)[2,1..n];

%Y Cf. A071984, A112663.

%K nonn,tabf

%O 32,2

%A _Martin Renner_, Apr 23 2016