A064817 - OEIS

%I #29 Nov 04 2016 05:17:27

%S 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 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,

%U 50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68

%N 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 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 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 a(n) = n - 1 for 25 <= n <= 500, computed by solving corresponding TSP. - _Rob Pratt_, Nov 07 2012

%D 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 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 (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 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 Cf. A035106, A064764, A064796, A064797, A071983, A071984.

%K nonn,nice

%O 1,5

%A _N. J. A. Sloane_, Oct 23 2001

%E More terms from _Vladeta Jovovic_, Oct 23 2001

%E More terms from _John W. Layman_ and Charles K. Layman (cklayman(AT)juno.com), Nov 07 2001

%E More terms from _David Wasserman_, Aug 20 2002

%E More terms from _Rob Pratt_, Nov 07 2012