[seqfan] Re: 2D extension to A327474

[Zach DeStefano]

Nitai Sasson,

I wrote a program in C++ (similar to yours) to validate and extend your
sequence. It confirms your listed terms in a few seconds, and then I let it
compute up to n = 12.

It managed to compute these in just a few minutes, so I am sure I could
produce a few more terms with more compute time.

The current list of terms I have is:
[2, 14, 158, 1410, 8238, 35166, 120810, 351866, 903922, 2102066, 4511366,
9056022].

- Zach

On Sat, Jan 28, 2023 at 9:22 AM nitai.s at campus.technion.ac.il <
nitai.s at campus.technion.ac.il> wrote:

> ​> I understood it otherwise: we have the set of n² points
> > P = { (x,y) ;  1 <= x,y <= n }
> > and want to know  a(n) = card { avg(S) ; S \subset P }
> > where avg(S) is the sum of all elements of S divided by max(number of
> > elements, 1)
>
>
> Correct, this is what I meant!
>
> My Python code is smarter than a direct brute force approach, it builds
> upon previous iterations and culls duplicates. Here's what it generated
> within a few hours:
>
> [2, 14, 158, 1410, 8238, 35166, 120810, 351866, 903922]
>
> And below is the code. I'm afraid it's not that readable and not greatly
> commented, but I am not socially able to explain it further at the moment
> :) I can definitely clarify later on though
>
>
> from fractions import Fraction
> import sys
>
> # begrudgingly, empty set is allowed and has mean (0,0) (unique mean)
>
> def avg(xy_sums, divisor):
>     return (Fraction(xy_sums[0],divisor),Fraction(xy_sums[1],divisor))
>
> # initialize with n=1 data (doesn't fit code since sides would have length
> 0)
> sums = {(0,0,0),(1,1,1)}  # one square available - either used or not
> means = {avg((0,0),1),avg((1,1),1)}  # see above, mean is (0,0) or (1,1);
> avg() used to Fraction-ize it
> side_sums = {(0,0)}
> result = [len(means)]
>
> print(result)
>
> for n in range(2,14):
>     # n = square dimension
>     # for n=3:
>     #
>     # oo+
>     # oo+
>     # ++x
>     #
>     # o = combinations already accounted for in prev iteration
>     # + = sides - options for which are computed first (also based on prev
> iteration), related to A327474
>     # x = extra square, try with and without
>
>     # sides (+) are of length n-1, add the n-1'th square to options
>     side_sums |= {(sum+n-1, size+1) for (sum, size) in side_sums.copy()}
>
>     # do the loop to add all the new options
>     new_sums = set()
>     total_iters = 2 * len(side_sums) * len(side_sums)
>     i = 0
>     for extra in (0,1):
>         for (right_sum, right_count) in side_sums:
>             for (bottom_sum, bottom_count) in side_sums:
>                 i += 1
>                 sys.stdout.write('\r')
>                 sys.stdout.write("[%-20s] %d/%d" %
> ('='*(i*20//total_iters), i, total_iters))
>                 sys.stdout.flush()
>
>                 add_x = bottom_sum + n * (extra + right_count)
>                 add_y = right_sum + n * (extra + bottom_count)
>                 add_count = extra + right_count + bottom_count
>                 new_sums.update((sx + add_x, sy + add_y, sc + add_count)
> for (sx, sy, sc) in sums)
>
>     print()
>     sums |= new_sums
>     means |= {avg((x,y),d) for (x,y,d) in new_sums if d != 0}
>
>     result.append(len(means))
>     print(result)
>
>
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>