cp's OEIS Frontend

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.

%I A348090 #21 Oct 25 2021 11:15:38
%S A348090 0,3,9,20,34,53,75,101,134,168,204,247,293,344,399,456,518,585,654,
%T A348090 725,803,886,978,1065,1154,1252,1355,1467,1572,1679,1797,1920,2052,
%U A348090 2188,2315,2444,2586,2733,2889,3049,3198,3349,3515,3686,3866,4050,4238,4413,4590,4784,4983,5191,5403,5619
%N 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.
%C A348090 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.
%C A348090 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.
%e A348090 a(1) = 0 as the single number 1 has no neighbor to add to.
%e A348090 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.
%e A348090 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.
%e A348090 a(4) = 20. The best way to arrange the numbers is in a 2 X 2 square. For example:
%e A348090 .
%e A348090   1 2
%e A348090   4 3
%e A348090 .
%e A348090 The sum is then (1+2)+(2+3)+(3+4)+(4+1) = 20. This is true for any permutation.
%e A348090 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:
%e A348090 .
%e A348090     2 3
%e A348090   1 5 4
%e A348090 .
%e A348090 The sum is then (2+3)+(3+4)+(4+5)+(5+2)+(1+5) = 34.
%e A348090 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:
%e A348090 .
%e A348090   2 6 4
%e A348090   1 5 3
%e A348090 .
%e A348090 The sum is (2+6)+(6+4)+(1+5)+(5+3)+(2+1)+(6+5)+(4+3) = 53.
%Y A348090 Cf. A346069 (multiplication), A003056, A005408.
%K A348090 nonn
%O A348090 1,2
%A A348090 _Scott R. Shannon_ and _Zach J. Shannon_, Oct 16 2021