[seqfan] Re: distinct sums in a square

[M. F. Hasler]

Very nice idea!

7 = 8-1 possibly interesting variants follow from additional conditions A
and/or B and/or C :
(A) all entries must be distinct
(B) all entries must be positive integers
(C) consider Moore neighborhood (8 directions) instead
     [That does not allow a solution for n=2.]

Also, related sequences:

b(n) = the minimal max{ a[i,j] } for solutions with minimal sum a(n)

c(n) = the minimal max{ a[i,j] } considering all nXn solutions
  (i.e., with all sums distinct but not necessarily minimum total sum)
  E.g., for n=3 there is the solution [0,0,0 ; 0,1,2 ; 2,2,3]
  with larger sum 10 but smaller max{a_ij} = 3 instead of 4.)
  For n=5 the solution given in oeis.org/A340630 has max{a_ij} = 11
  in contrast to the one given in Hugo's OP with max=13,
  but his one is lexicographically first.)
d(n) = smallest possible maximum of the distinct sums of an nXn solution
  (Up to n=4 it is n²-1 in the original "nonnegative" variant, but
  from n=5 on it is > n² ... always?)

PS: congrats to Robert for his impressive hand-made general near-minimal
solution!

- Maximilian

On Sun, Jan 10, 2021 at 8:57 PM <hv at crypt.org> wrote:

> Define a(n) as the least k such that an n x n grid of non-negative
> integers summing to k can be found, in which each element when added
> to its orthogonal neighbours yields a distinct sum.
>
> I believe the sequence starts 0, 6, 9, 27 which is not in the OEIS.
>
> I have (not necessarily minimal) candidates for a(5) and a(6), and no
> candidate for n > 6. I'd appreciate confirmation of at least a(1) .. a(4)
> before I submit to the OEIS - I have at best medium confidence in the
> correctness of the code I've written to get these values.
>
> For n > 4, I believe [1] we need a(n) >= (n^4 - n^2 + 14) / 10, giving
> a(5) > 61.4 and a(6) > 127.4, so my candidates approach but do not hit
> the theoretical optimum. The only upper bound I have is the relatively
> useless a(n) <= 2^(n^2) - 1.
>
> Examples (need fixed font!):
>
> a(1) = 0:                 element sums
>   0                       0
>
> a(2) = 6:
>   0 1                     3 4
>   2 3                     5 6
>
> a(3) = 9:
>   0 0 0                   0 1 3
>   0 1 3                   2 8 4
>   1 4 0                   5 6 7
>
> a(4) = 27:
>   0 0 0 0                  0  1  3  7
>   0 1 3 7                  4 10 14 11
>   3 6 3 1                  9 15 13 12
>   0 2 0 1                 11  8  6  2
>
> a(5) <= 63:
>   0  0  0  0  0            0  9  4 13  1
>   0  9  4 13  1           10 19 26 22 14
>   1  6  0  4  0            7 21 17 25  5
>   0  5  3  8  0            6 16 20 18  8
>   0  2  4  3  0            2 11 12 15  3
>
> a(6) <= 134:
>   0  0  0  0  0  0         0  4  6  7 12  1
>   0  4  6  7 12  1         5 23 21 26 29 13
>   1 13  4  1  9  0        14 30 24 22 33 10
>   0  8  0  1 11  0         9 37 19 25 38 11
>   0 16  6 12 17  0        16 32 34 36 43 17
>   0  2  0  0  3  0         2 18  8 15 20  3
>
>
> Ideas, constructions, better constraints or more values all welcome.
>
> Hugo
>
> ---
>
> [1] Justification of lower bound: letting S_c be the sum of the corner
> elements and S_e the sum of the non-corner edge elements, then the total
> of all the element sums is 5a(n) - S_e - 2S_c. However they are required
> to be n^2 distinct non-negative integers, which must sum to at least
> T(n^2 - 1) = n^2 (n^2 - 1) / 2.
>
> For n > 4, making the element sums at the corners distinct requires edge
> or corner elements contributing to sums of at least { 0, 1, 2, 3 }.
> The edge pieces adjacent to the corner with 0 sum must have their other
> adjacent edge differ by at least 1, so we have S_e + 2S_c >= 7.
>
> Thus a(n) >= (T(n^2 - 1) + 7) / 5 = (n^4 - n^2 + 14) / 10.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>