A348090 Place the numbers 1 to n on a square grid and sum both numbers in all created orthogonally adjacent pairs; a(n) gives the maximum possible value of the sum of all pair sums.

0, 3, 9, 20, 34, 53, 75, 101, 134, 168, 204, 247, 293, 344, 399, 456, 518, 585, 654, 725, 803, 886, 978, 1065, 1154, 1252, 1355, 1467, 1572, 1679, 1797, 1920, 2052, 2188, 2315, 2444, 2586, 2733, 2889, 3049, 3198, 3349, 3515, 3686, 3866, 4050, 4238, 4413, 4590, 4784, 4983, 5191, 5403, 5619

Offset: 1

Author

Scott R. Shannon and Zach J. Shannon, Oct 16 2021

Keywords

• nonn

Comments

On a square grid place the numbers 1 to n in any order or position. If any two numbers are orthogonally adjacent those two numbers are added, and the sum over all these pair sums is then found. The sequence gives the maximum possible value of this sum when placing numbers from 1 up to n.

Clearly, to maximize the sum all numbers should have one or more adjacent neighbors, and in general the larger numbers should be placed so that they appear in the most pairs so that their value contributes the most to the final sum. However, if two numbers have the same number of orthogonal neighbors then they can be switched since a number's contribution to the final sum is determined by the number of pairs it is in, not by the value of their pair neighbors.

Examples

			a(1) = 0 as the single number 1 has no neighbor to add to.
a(2) = 3 as the numbers 1 and 2 can be placed next to each other in one way, and the pair sum is 1+2 = 3.
a(3) = 9. The numbers 1,2,3 can be placed next to each other in six ways: 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1. The combinations with the largest pair sums are 1-3-2 and 2-3-1, the sum being (1+3)+(3+2) = 9. This is the largest sum as 3 is placed so that it is in two pairs and thus contributes twice to the sum.
a(4) = 20. The best way to arrange the numbers is in a 2 X 2 square. For example:
.
  1 2
  4 3
.
The sum is then (1+2)+(2+3)+(3+4)+(4+1) = 20. This is true for any permutation.
a(5) = 34. The best way to arrange the numbers is for 2,3,4,5 to be in a 2 X 2 square and for 1 to be placed next to 5. For example:
.
    2 3
  1 5 4
.
The sum is then (2+3)+(3+4)+(4+5)+(5+2)+(1+5) = 34.
a(6) = 53. The best way to arrange the numbers is in a 2 X 3 block where the 5 and 6 are in the middle of the long edge so that they both appear in three pairs. For example:
.
  2 6 4
  1 5 3
.
The sum is (2+6)+(6+4)+(1+5)+(5+3)+(2+1)+(6+5)+(4+3) = 53.
		

Crossrefs

Cf. A346069 (multiplication), A003056, A005408.