[seqfan] Re: distinct sums in a square
Neil Sloane
njasloane at gmail.com
Tue Jan 12 22:01:35 CET 2021
Very nice work! Will one of you please submit it (and tell me the A-number)
Hugo, you should probably do it, this is your baby!
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
On Tue, Jan 12, 2021 at 2:29 PM Rob Pratt <robert.william.pratt at gmail.com>
wrote:
> 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/
> >>
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list