[seqfan] Re: distinct sums in a square
Rob Pratt
robert.william.pratt at gmail.com
Tue Jan 12 20:29:32 CET 2021
I meant a(6) = 128.
On Tue, Jan 12, 2021 at 2:29 PM Rob Pratt <robert.william.pratt at gmail.com>
wrote:
> 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