[seqfan] Re: distinct sums in a square
Rob Pratt
robert.william.pratt at gmail.com
Tue Jan 12 23:04:49 CET 2021
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/
>
More information about the SeqFan
mailing list