cp's OEIS Frontend

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.

%I A272259 #29 Jun 25 2025 01:08:04
%S A272259 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 A272259 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 A272259 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 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.
%C A272259 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 A272259 There are no circular solutions for n < 32.
%C A272259 T(32) = A112663(k-1), 1 <= k <= 32.
%C A272259 Row n has length n, and we start with row n = 32.
%H A272259 Martin Renner, <a href="/A272259/b272259.txt">Table of n, a(n) for n = 32..663</a>
%e A272259 Table starts with
%e A272259 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 A272259 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 A272259 with(GraphTheory):
%p A272259 n:=32; # Vertices from 1 to n
%p A272259 E:={}: # Edges
%p A272259 for a from 1 to n do
%p A272259   for b from a+1 to n do
%p A272259     if type(sqrt(a+b),integer) then E:={op(E),{a,b}}: fi:
%p A272259   od:
%p A272259 od:
%p A272259 G:=Graph(E);
%p A272259 T||n:=TravelingSalesman(G)[2,1..n];
%o A272259 (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] ]);
%o A272259   if (t && (step<n || t=setintersect(t, N[1])), used[path[step] = t[1]] = 1, path[step] = used[path[step-1]] = 0; step -= 2 )); path} \\ _M. F. Hasler_, Jun 24 2025
%Y A272259 Cf. A071984 (number of solutions), A112663 (row 32 repeated).
%K A272259 nonn,tabf
%O A272259 32,2
%A A272259 _Martin Renner_, Apr 23 2016