[seqfan] Re: distinct sums in a square
hv at crypt.org
hv at crypt.org
Sat Jan 16 02:54:26 CET 2021
b(n) probably starts 0, 3, 4, 5, 8, with representative examples:
0
0 1 // 2 3
0 0 0 // 3 1 0 // 0 4 1
0 0 0 0 // 4 5 1 0 // 1 3 5 1 // 0 2 4 1
0 0 0 0 0 // 0 5 7 8 1 // 5 5 0 2 0 // 1 8 7 6 0 // 0 1 3 4 0
(The b(5) run didn't finish due to a crash, but I believe it was close.)
My expectation, conversely, is that d(n) = n^2 - 1 for nearly all n, and
probably for all but a finite selection of n (based on similar reasoning
to my conjecture that a(n) achieves the theoretical minimum in all but
finitely many cases - the number of possible grids (around C(n^2 + a(n),
a(n)), and number of minimal solutions, both grow really fast).
On the same grounds again I would expect that c(n) = b(n) for all but
a handful of small cases.
I haven't thought much about (A), (B) or (C) yet.
Hugo
"M. F. Hasler" <oeis at hasler.fr> wrote:
: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/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list