cp's OEIS Frontend

A064817 Maximal number of squares among the n-1 numbers p_i + p_{i+1}, 1 <= i <= n-1, where (p_1, ..., p_n) is any permutation of (1, ..., n).

%I A064817 #29 Nov 04 2016 05:17:27
%S A064817 0,0,1,1,2,3,4,5,6,7,8,9,10,12,14,15,16,16,17,18,19,20,22,22,24,25,26,
%T A064817 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,
%U A064817 50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68
%N A064817 Maximal number of squares among the n-1 numbers p_i + p_{i+1}, 1 <= i <= n-1, where (p_1, ..., p_n) is any permutation of (1, ..., n).
%C A064817 a(n) < n by definition, but if we counted the sum p_n + p_1, we could get a(n) = n for 32 <= n <= 49 (see A071984). - _David Wasserman_, Aug 20 2002
%C A064817 Can be formulated as a traveling salesman problem on a complete graph with node set {0, 1, ..., n} and edge cost -1 if i + j is a square, 0 otherwise. - _Rob Pratt_, Nov 07 2012
%C A064817 a(n) = n - 1 for 25 <= n <= 500, computed by solving corresponding TSP. - _Rob Pratt_, Nov 07 2012
%D A064817 Bernardo Recamán Santos, Challenging Brainteasers, Sterling, NY, 2000, page 71, shows a(15) = 14 using 9,7,2,14,11,5,4,12,13,3,6,10,15,1,8.
%e A064817 n=8: take 2,7,8,1,3,6,4,5 to get 5 squares: 2+7, 8+1, 1+3, 3+6, 4+5; a(8) = 5.
%e A064817 (1,8,9,7,2,14,11,5,4,12,13,3,6,10) gives 12 squares and no permutation of (1..14) gives more, so a(14)=12.
%t A064817 a[n_] := Which[n == 1, 0, n > 30, n - 1, True, tour = FindShortestTour[Range[n], DistanceFunction -> Function[{i, j}, If[IntegerQ[Sqrt[i + j]], -1, 0]]] // Last; cnt = 0; Do[If[IntegerQ[Sqrt[tour[[i]] + tour[[i + 1]]]], cnt++], {i, 1, n}]; cnt]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 69}] (* _Jean-François Alcover_, Nov 04 2016 *)
%Y A064817 Cf. A035106, A064764, A064796, A064797, A071983, A071984.
%K A064817 nonn,nice
%O A064817 1,5
%A A064817 _N. J. A. Sloane_, Oct 23 2001
%E A064817 More terms from _Vladeta Jovovic_, Oct 23 2001
%E A064817 More terms from _John W. Layman_ and Charles K. Layman (cklayman(AT)juno.com), Nov 07 2001
%E A064817 More terms from _David Wasserman_, Aug 20 2002
%E A064817 More terms from _Rob Pratt_, Nov 07 2012