A272259 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.

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, 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, 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

Offset: 32

Author

Martin Renner, Apr 23 2016

Keywords

• nonn
• tabf

Comments

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.

There are no circular solutions for n < 32.

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

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

Examples

			Table starts with
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.
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.
		

Links

• Martin Renner, Table of n, a(n) for n = 32..663

Crossrefs

Cf. A071984 (number of solutions), A112663 (row 32 repeated).

Programs

Maple

with(GraphTheory):
n:=32; # Vertices from 1 to n
E:={}: # Edges
for a from 1 to n do
  for b from a+1 to n do
    if type(sqrt(a+b),integer) then E:={op(E),{a,b}}: fi:
  od:
od:
G:=Graph(E);
T||n:=TravelingSalesman(G)[2,1..n];

PARI

A272259(n)={my(N=[[c^2-a | c<-[sqrtint(a)+1..sqrtint(n+a)], c^2 != 2*a] | a<-[1..n]], used=Vec(1,n), path=Vec(1,n)); for(step=2, n, my(t = [k | k<-N[path[step-1]], k > path[step] && !used[k] ]);
  if (t && (stepM. F. Hasler, Jun 24 2025