A384616 A(m,n) is the maximum sum of absolute differences of the labels of adjacent vertices of the grid graph P_m X P_n where the m*n labels are exactly 1, 2, ..., m*n.

0, 1, 8, 3, 23, 58, 7, 44, 115

Offset: 1

Author

Sela Fried, Jun 07 2025

Keywords

• nonn
• tabl
• more

Comments

A(m, n) ~ Theta((m*n)^2) (see link).

Examples

			Array begins (values in parentheses are conjectural):
  [1]  0
  [2]  1    8
  [3]  3   23    58
  [4]  7   44   115   (216)
  [5] 11   71  (182)  (347)  (554)
  [6] 17  104  (271)  (508)  (815) (1192)
  [7] 23  143  (370)  (699) (1118) (1639) (2250)
  [8] 31 (188) (491)  (920) (1475) (2156) (2963) (3896)
  [9] 39 (239) (622) (1171) (1874) (2743) (3766) (4955) (6298)
		

Links

• Sela Fried, On the maximal sum of absolute differences of certain labelings of the grid graph, 2025.

Crossrefs

Column 1 is A047838.

Cf. A067725.

Programs

Python

import itertools
import numpy as np
def max_difference_sum(m, n):
    nums = list(range(1, m * n + 1))
    max_sum = 0
    best_matrix = None
    for perm in itertools.permutations(nums):
        matrix = np.array(perm).reshape((m, n))
        diff_sum = np.sum(np.abs(matrix[:,1:]-matrix[:,:-1])) + np.sum(np.abs(matrix[1:,:]-matrix[:-1,:]))
        if diff_sum > max_sum:
            max_sum = diff_sum
            best_matrix = matrix.copy()
    return max_sum, best_matrix
for m in range(1, 10):
    for n in range(1, m+1):
        max_sum, best = max_difference_sum(m, n)
        print(max_sum, end=', ')

Formula

Conjecture: A(m,2) = A067725(m-1) - 1.