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

0, 2, 9, 25, 54, 100, 167, 258, 377, 529, 718, 947, 1220, 1542

Offset: 1

Author

Scott R. Shannon, Oct 16 2021

Keywords

• nonn
• more

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 multiplied, and the sum over all these pair products 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 are adjacent to other large numbers so that their products contribute the most to the final sum. Unlike the addition case of A348090 the numbers in general cannot be switched, even if they have the same number of orthogonal neighbors, since the values of a number's neighbors does effect the overall contribution that each pair product has to the final sum.

Examples

			a(1) = 0 as the single number 1 has no neighbor to multiply with.
a(2) = 2 as the numbers 1 and 2 can be placed next to each other in one way, and the pair product is 1*2 = 2.
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 products are 1-3-2 and 2-3-1, the product 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 its products contributes twice to the sum.
a(4) = 25. The best way to arrange the numbers is in a 2 X 2 square where 4 is adjacent to 2 and 3:
.
  4 3
  2 1
.
The sum is then (4*3)+(4*2)+(3*1)+(2*1) = 25.
a(5) = 54. The best way to arrange the numbers is for 2,3,4,5 to be in a 2 X 2 square with 5 adjacent to 4 and 3, and for 1 to be placed next to 5:
.
  1 5 4
    3 2
.
The product sum is then (5*4)+(5*3)+(4*2)+(3*2)+(5*1) = 54.
a(6) = 100. The best way to arrange the numbers is in a 2 X 3 block where 5 and 6 are in the middle of the long edge so that they both appear in three pairs. The 2 and 4 are placed either side of the 6 while the 1 and 3 are placed either side of 5:
.
  2 6 4
  1 5 3
.
The product sum is then (2*6)+(6*4)+(1*5)+(5*3)+(2*1)+(6*5)+(4*3) = 100.
		

Crossrefs

Cf. A348090 (addition), A003991, A003056.