[seqfan] Re: distinct sums in a square
hv at crypt.org
hv at crypt.org
Tue Jan 12 23:34:58 CET 2021
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