A064817 - OEIS

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

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, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

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

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

a(n) = n - 1 for 25 <= n <= 500, computed by solving corresponding TSP. - Rob Pratt, Nov 07 2012

REFERENCES

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.

LINKS

Table of n, a(n) for n=1..69.

EXAMPLE

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.

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

MATHEMATICA

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 *)

CROSSREFS

Cf. A035106, A064764, A064796, A064797, A071983, A071984.

Sequence in context: A191889 A091402 A365513 * A366378 A108549 A045779

Adjacent sequences: A064814 A064815 A064816 * A064818 A064819 A064820

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Oct 23 2001

EXTENSIONS

More terms from Vladeta Jovovic, Oct 23 2001

More terms from John W. Layman and Charles K. Layman (cklayman(AT)juno.com), Nov 07 2001

More terms from David Wasserman, Aug 20 2002

More terms from Rob Pratt, Nov 07 2012

STATUS

approved