[seqfan] Re: 2D extension to A327474

[nitai.s at campus.technion.ac.il]

​> 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)