[seqfan] Re: distinct sums in a square
Rob Pratt
robert.william.pratt at gmail.com
Tue Jan 12 20:29:01 CET 2021
I confirmed via integer linear programming that a(1) = 0, a(2) = 6, a(3) =
9, a(4) = 27, and a(5) = 63. Also a(n) = 128:
0 0 0 0 1 0
4 14 9 7 15 0
2 5 3 4 5 0
0 5 4 3 10 0
0 17 3 2 12 0
0 2 0 1 0 0
4 14 9 8 16 1
20 32 33 35 28 15
11 29 25 22 34 5
7 31 18 23 30 10
17 27 26 21 24 12
2 19 6 3 13 0
On Tue, Jan 12, 2021 at 11:47 AM <hv at crypt.org> wrote:
> I'm glad you like it, Rainer. :)
>
> Be aware that there appear to be many solutions. For n = 2, 3, 4 I found
> 3, 9, 755 distinct squares respectively yielding a(n). As such it is
> possible some of the aspects that you noted are an artifact of
> the manner in which I generated them.
>
> Based on the insight from my earlier footnote that S_e + 2S_c is a relevant
> constraint on optimal solutions, my code selects elements to generate in
> this order, starting with the outer shell of the square:
> 1 5 ... 7 2
> 6 8
> ... ...
> 9 11
> 3 10 ...12 4
>
> Previously I then took the remaining inner elements in normal order,
> but I have now refined that to repeat the above pattern for successive
> inner shells. This has allowed me to improve my best candidate for n=6
> and start to generate candidates for n=7 and n=8:
>
> a(6) <= 131 (theoretical minimum 128):
> 0 0 0 0 0 0 0 4 8 12 14 1
> 0 4 8 12 14 1 5 24 26 34 32 15
> 1 12 2 0 5 0 13 27 23 22 28 6
> 0 8 1 3 9 0 10 36 19 20 35 9
> 1 15 5 7 18 0 16 30 29 33 37 18
> 0 1 1 0 3 0 2 17 7 11 21 3
>
> a(7) <= 257 (theoretical minimum 237):
> 0 0 0 0 0 0 0 0 4 11 21 14 6 1
> 0 4 11 21 14 6 1 5 26 36 51 41 35 7
> 1 11 0 5 0 14 0 12 37 34 27 42 40 15
> 0 21 7 1 9 20 0 22 54 29 23 30 61 20
> 0 15 0 1 0 18 0 16 43 38 25 44 48 18
> 1 7 15 23 16 10 0 8 39 46 55 49 47 10
> 0 1 1 0 0 3 0 2 9 17 24 19 13 3
>
> a(8) <= 411 (theoretical minimum 405):
> 0 0 0 0 0 0 0 0 0 4 11 20 22 14 6 1
> 0 4 11 20 22 14 6 1 5 26 36 59 57 42 35 7
> 1 11 1 6 1 0 14 0 12 37 32 41 53 29 43 15
> 0 20 3 13 24 0 23 0 21 58 38 48 52 51 64 23
> 0 24 1 2 14 4 27 0 24 60 33 30 46 45 72 27
> 0 15 3 0 2 0 18 0 16 49 34 31 44 40 55 18
> 1 7 15 24 28 16 10 0 8 39 50 67 70 54 47 10
> 0 1 1 0 0 0 3 0 2 9 17 25 28 19 13 3
>
> I'm astonished how close to optimal that a(8) solution is, and that
> it falls out quite quickly when running my code, whereas my best a(7)
> solution took much longer to find and is still much further from optimal:
> I wonder if this is an early signal of divergence in the behaviour of
> odd versus even n.
>
> Hugo
>
> Rainer Rosenthal <r.rosenthal at web.de> wrote:
> :Hi Hugo
> :
> :Congratulations, what a wonderful puzzle!
> :
> :Solutions seem far from any ready-made pattern and look very
> sophisticated.
> :n=3: one can get a matrix with sum 10 easily by putting 0, 1, 2, 3, 4 on
> :the 5 diagonal points.
> :At first this looks like a real champion, but then comes your solution
> :with sum 9. Astonishing.
> :n = 4: elements seem to need at least maximum size 6 in order to find
> :proper places. I was able to find a solution with max 6 and sum 34, but
> :better results exist for sure. It is another surprise that with larger
> :maximum size 7 we can get smaller sums. Your record solution with max 7
> :is beautiful, because the element-sums are exactly all the numbers from
> :0 to 15.
> :n = 5 and n = 6: fascinating to see the borders of the square filled
> :with many zeroes and one zero in the middle. Everything very irregular
> :and without symmetry - wonderful.
> :
> :Thanks for this beautiful puzzle, and a happy New Year 2021 for you all,
> :Rainer
> :
> :
> :
> :Am 11.01.2021 um 01:47 schrieb hv at crypt.org:
> :> 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/
>
More information about the SeqFan
mailing list