[seqfan] Re: distinct sums in a square
hv at crypt.org
hv at crypt.org
Thu Jan 14 06:52:12 CET 2021
Thanks for all the contributions; this is now A340630.
Hugo
I wrote:
:Super, thanks Rob for the confirmation and additional results.
:
:I have additionally 650 <= a(9) <= 653, and a(10) = 992 (which just fell
:right out):
:
:a(9) <= 653 >= 650:
: 0 0 0 0 0 0 0 0 0
: 0 4 11 20 29 22 14 6 1
: 1 11 1 0 1 0 0 14 0
: 0 20 10 19 15 23 6 23 0
: 0 30 1 18 6 19 0 31 0
: 0 24 0 17 12 31 0 27 0
: 0 15 2 6 1 6 0 18 0
: 1 7 15 24 32 28 16 10 0
: 0 1 1 0 0 0 0 3 0
:
:a(10) = 992:
: 0 0 0 0 0 0 0 0 0 0
: 0 4 11 20 29 31 22 14 6 1
: 1 11 5 0 0 0 0 0 14 0
: 0 20 11 25 24 27 29 16 23 0
: 0 30 0 33 8 10 7 0 32 0
: 0 33 0 31 0 19 20 1 36 0
: 0 24 1 25 30 14 31 0 27 0
: 0 15 2 13 0 0 11 0 18 0
: 1 7 15 24 34 37 28 16 10 0
: 0 1 1 0 0 0 0 0 3 0
:
:Neil: yes, will do, probably tomorrow.
:
:Hugo
:
:Rob Pratt <robert.william.pratt at gmail.com> wrote:
::a(7) = 237:
::
::0 0 0 0 2 0 0
::1 20 8 20 15 4 0
::0 6 0 0 0 13 0
::0 16 10 14 5 8 1
::0 14 0 2 0 9 0
::1 17 3 10 23 11 2
::0 2 0 0 0 0 0
::
::1 20 8 22 17 6 0
::21 35 48 43 41 32 4
::7 42 24 34 33 25 14
::16 46 40 31 27 36 9
::15 47 29 26 39 28 12
::18 37 30 38 44 45 13
::3 19 5 10 23 11 2
::
::On Tue, Jan 12, 2021 at 4:01 PM Neil Sloane <njasloane at gmail.com> wrote:
::
::> 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/
::> >
::>
::> --
::> Seqfan Mailing list - http://list.seqfan.eu/
::>
::
::--
::Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list