A054247 -id:A054247 - cp's OEIS frontend

A286430 Least volume of water to surround the largest possible island in a number square.

0, 0, 0, 0, 36, 78, 136, 210, 300, 406, 528, 666, 820, 990, 1176, 1378, 1596, 1830, 2080, 2346, 2628, 2926, 3240, 3570, 3916, 4278, 4656, 5050, 5460, 5886, 6328, 6786, 7260

Offset: 0

Craig Knecht, May 09 2017

nonn

The water retention model for mathematical surfaces showed that a random two-level system will contain more water than a random 3-level system when the size of the square is > 52 X 52. It has also been the subject of Zimmermann's programming contest in 2010 and a Wikipedia page as noted below. The number square is a simple environment in which to explore the interaction of volumes, heights, and areas of lakes, ponds, islands, and spillways in the square.
A number square contains the numbers for 1 to n^2 without repeats in an n X n square.
This sequence is 4*A000217 for a(n) > 8.

			For this 5 X 5 square the numbers 1 to 25 are used without repeats. The values 1 through 8 form the moat.  The spillway value is 9.  The volume of water retained is 36 units.
( 24 23 22 21 20)
( 18  1  2  3 19)
( 17  8 25  4  9)
( 16  7  6  5 15)
( 14 13 12 11 10)

Craig Knecht, 3D graphic.
Craig Knecht, Least volume of water to surround the largest island in a number square.
Craig Knecht, Number range for each cell type.
Wikipedia, Water retention on mathematical surfaces

Cf. A054247, A201126, A268311.

Conjectures from Colin Barker, Jan 20 2018: (Start)
G.f.: 2*x^4*(18 - 15*x + 5*x^2) / (1 - x)^3.
a(n) = 28 - 30*n + 8*n^2 for n>3.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>2.
(End)

A361870 Array read by downward antidiagonals: A(n,k) is the number of nonequivalent 2-colorings of the cells of an n-dimensional hypercube with edges k cells long under action of symmetry.

Original entry on oeis.org

2, 2, 1, 2, 2, 1, 2, 3, 2, 1, 2, 6, 6, 2, 1, 2, 10, 102, 22, 2, 1, 2, 20, 8548, 2852288, 402, 2, 1, 2, 36, 4211744, 384307306807269376, 6296489398464125698304, 1228158, 2, 1

Offset: 0

Natalia L. Skirrow, May 28 2023

A(0,0) = 2 by the convention that 0^0 = 1, in spirit with A003992.
A(n,2) = A000616(n), because the Boolean functions' truth tables are n-dimensional edge-length-2 hypercubes, and are considered equivalent under action of input permutation (transposition of dimensions) and applications of NOT to inputs (reflection in dimensions) that compose for the hypercube's symmetry group.
A(n,3) is the number of transitions in an isotropic non-totalistic Life-like cellular automaton with an n-dimensional Moore neighborhood.
A(n,k) ~ 2^(k^n)/(n!*2^n) for large k where n >= 1, and large n where k >= 2, and converges from above. Proof: When computing it with the Pólya enumeration theorem (for each action, count colorings of cycles under it instead of cells, average result over actions), the asymptotic form describes the number of states contributed by the identity action. Over k, the values contributed by the other actions are at most O(2^(k^n/2)), so the proportion that they contribute may be made arbitrarily small by choosing a large enough n. Over n, there are no more than n!*2^n such non-identity actions, assuming that they are all of order 2 (as an upper bound). Each one may have no more than a hyperplane (2^k^(n-1)) of fixed points, which (if it is of order 2) will multiply its colorings by 2^(k^(n-1)/2). The ratio of the identity term to the others is at least O(2^k^n/(n!*2^n*2^(k^(n-1)/2))), and its base-2 logarithm, by Stirling's approximation, is O(k^n-n*log(n)-n-k^(n-1)/2), so the 2^(k^n) term will dominate.
A(1,k) is the only row >= 1 that is linear-recurrent over k (and has a rational generating function), all other nontrivial rows and columns grow faster than any linear-recurrent function.
A000120(A(n,k)) is eventually periodic over k if and only if n <= 2.

			n\k|0, 1,       2,                      3,                  4,       5,  6, 7, ...
---+------------------------------------------------------------------------------
 0 |2, 2,       2,                      2,                  2,       2,  2, 2, ...
 1 |1, 2,       3,                      6,                 10,      20, 36, ...
 2 |1, 2,       6,                    102,               8548, 4211744, ...
 3 |1, 2,      22,                2852288, 384307306807269376, ...
 4 |1, 2,     402, 6296489398464125698304, ...
 5 |1, 2, 1228158, ...
 6 |1, 2, ...
 7 |1, ...
...

Natalia L. Skirrow, Table of n, a(n) for n = 0..59
Adam P. Goucher, Combinatorics I, Mathematical Olympiad Dark Arts (2005), 8-11.
LifeWiki, Isotropic non-totalistic rule, Pólya enumeration theorem.
Natalia L. Skirrow, dimensional_INT_enumerator.py (unreduced version of Python program below, that also finds equations for fixed n).

Cf. A000616, A005418, A054247, A003992.

from functools import reduce
from itertools import accumulate
from math import isqrt,lcm,factorial as fact
tap=lambda f,*i:tuple(map(f,*i))
redumulate=lambda f,l,i=None: accumulate(l,f,initial=i)
expumulate=lambda f,l: lambda i: accumulate(range(l),lambda x,i: f(x),initial=i)
factorise=lambda m: tuple(filter(lambda n: not m%n,range(1,m//2+1)))+(m,)
def cycleLengths(dims,size):
    convert=(lambda m,i,a: (lambda d,n,i: ('('*bool(i)+str(size)+'+~(')*n+a+("//"+str(size**d))*bool(d)+('%'+str(size))*(dd for d,m in p[:i]))*fact(len(p)+~i)*2**dims+2**i*n for i,(e,n) in enumerate(p)))
    matrices=sorted((tuple((j,n>>i&1) for i,j in enumerate((lambda t: tuple(reduce(lambda e,n: e+(e>=n),t[i-1::-1],e)%dims for i,e in enumerate(t)))(tuple(a[0]%(dims-i) for i,a in enumerate(redumulate(lambda m,i: divmod(m[0],i),range(dims,1,-1),(m,0))))))) for m in range(fact(dims)) for n in range(2**dims)),key=matrindex) if dims else []
    exps=tap(lambda m: tap(matrindex,expumulate(lambda i: tap(lambda j: (lambda k,l: (k,l^j[1]))(*i[j[0]]),m),lcm(4,fact(dims)))(matrices[0])),matrices)
    lambdas=tap(lambda m: eval("lambda s: ["+','.join('s['+str(eval('+'.join(map(lambda i: convert(m,i,str(j)),range(dims)))))+']' for j in range(boardCells))+']'),matrices)
    test=list(range(1,boardCells+1))
    factors=tap(lambda e: factorise(e[1:].index(0)+1),exps)
    subperiods=tuple(tuple(sum(map(int._eq_,test,lambdas[exps[i][a]](test))) for a in f) for i,f in enumerate(factors))
    return((lambda t: tap(lambda t: reduce(lambda r,t: r+((t[0],t[1]-sum(i[1] for i in r if not t[0]%i[0])),),t,()),t))(tap(lambda a,b: tuple(zip(a,b)),factors,subperiods)))
specific=(lambda cycles: int(bool(cycles) and sum(2**sum(i[1]//i[0] for i in c) for c in cycles)//len(cycles)))
line=lambda k: (1,2)[k] if k<2 else 1<>1)
A054247=lambda n: (1,2,6)[n] if n<3 else 1<>1)+3**(~n&1)<<(n**2-5>>1)|1<<(n**2-5>>2)
cube=lambda k: (2**k**3+3*2**((k+1>>1)*k**2)+9*2**((k**2+1>>1)*k)+2**(k**3+1>>1)+6*2**(k**2*(k+1)>>1)+6*2**((k**2+3)//4*k)+6*2**((k**2+1>>1)*k+1>>1)+8*2**(k*(k**2+2)//3)+8*2**(k*(k**2+2)//3+1>>1))//48
tesseract=lambda k: (2**k**4+4*2**((k+1>>1)*k**3)+30*2**((k**2+1>>1)*k**2)+16*2**((k**3+1>>1)*k)+2**(k**4+1>>1)+12*2**(k**3*(k+1)>>1)+12*2**((k**2+3>>2)*k**2)+48*2**(((k**2+1>>1)*k+1>>1)*k)+12*2**((k**2+1>>1)*k**2+1>>1)+32*2**(k**2*(k**2+2)//3)+32*2**((k+1>>1)*k*(k**2+2)//3)+32*2**((k*(k**2-1)//3+k+1>>1)*k)+32*2**(k**2*(k**2+2)//3+1>>1)+12*2**(k**2*(k**2+1)>>1)+12*2**(k**4+3>>2)+48*2**(k*(k**3+k+2)>>2)+48*2**(k**4+7>>3))//384
nonequivalents=lambda n,k: (lambda k: 2,line,A054247,cube,tesseract)[n](k) if n<5 else 2**k if k<2 else specific(cycleLengths(n,k))
A002262=(lambda n: (lambda s: (lambda o: (o,s-o))(n-s*(s+1)//2))(isqrt((n<<3)+1)-1>>1))
print(tuple(map(lambda n: nonequivalents(*A002262(n)),range(28)))) # Natalia L. Skirrow, May 29 2023

Where an expression can be simplified by dividing a power of 2's coefficient by 2 and incrementing its exponent by 1, it is left as-is, so that the 2^ can be changed to c^ for general c-colorings.
A(n,2) = A000616(n).
A(0,k) = 2.
Herein, c(x) denotes the ceiling function.
A(1,k) = A005418(k+1) = (2^k + 2^c(k/2))/2.
A(2,k) = A054247(k) = (2^k^2 + 2*2^(k*(k+1)/2) + 2*2^(c(k/2)*k) + 2^c(k^2/2) + 2*2^c(k^2/4))/8.
A(3,k) = (2^k^3 + 3*2^(c(k/2)*k^2) + 9*2^(c(k^2/2)*k) + 2^c(k^3/2) + 6*2^(k^2*(k+1)/2) + 6*2^(c(k^2/4)*k) + 6*2^c(c(k^2/2)*k/2) + 8*2^(k*(k^2+2)/3) + 8*2^c(k*(k^2+2)/6))/48.
A(4,k) = (2^k^4 + 4*2^(c(k/2)*k^3) + 30*2^(c(k^2/2)*k^2) + 16*2^(c(k^3/2)*k) + 2^c(k^4/2) + 12*2^(k^3*(k+1)/2) + 12*2^(c(k^2/4)*k^2) + 48*2^(c(c(k^2/2)*k/2)*k) + 12*2^c((c(k^2/2)*k^2)/2) + 32*2^(k^2*(k^2+2)/3) + 32*2^(c(k/2)*k*(k^2+2)/3) + 32*2^(c((k*(k^2-1)/3+k)/2)*k) + 32*2^c((k^2*(k^2+2)/3)/2) + 12*2^(k^2*(k^2+1)/2) + 12*2^c(k^4/4) + 48*2^(k*(k^3+k+2)/4) + 48*2^c(k^4/8))/384.

A275798 One half of the number of n X n square grids with squares of two colors modulo operations of the dihedral group D_4.

Original entry on oeis.org

1, 3, 51, 4274, 2105872, 4295278656, 35184441295872, 1152921514002096128, 151115727460762179076096, 79228162514269052299408048128, 166153499473114502703835144588886016, 1393796574908163946384646767619026404245504, 46768052394588893382518536034792338549485151977472

Offset: 1

Wolfdieter Lang, Oct 03 2016

See A054252(n, k) for the number of n X n square grids with squares from two colors modulo operations of the dihedral group D_4 with k colors of one sort.

One half of the row sums of A054252, starting with n=1. For the row sums starting with n=0 see A054247.

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A054252, A054247.

a(n) = (1/2)*Sum_{k=0..n^2} A054252(n, k).

a(n) = A054247(n)/2, n >= 1.

Terms a(11) and beyond from Andrew Howroyd, Apr 26 2020

A286429 Highest elevation of an island above sea level in a number square.

Original entry on oeis.org

0, 0, 0, 0, 16, 27, 40, 55, 72, 91, 112, 135, 160, 187, 216, 247, 280, 315, 352, 391, 432, 475, 520, 567, 616, 667, 720, 775, 832, 891, 952, 1015, 1080, 1147, 1216, 1287, 1360, 1435, 1512, 1591, 1672, 1755, 1840, 1927, 2016, 2107, 2200, 2295, 2392

Offset: 0

Craig Knecht, May 09 2017

nonn

The water retention model for mathematical surfaces has previously looked at lakes and ponds. This sequence looks at the maximum possible height of an island above water level in a number square.
The smallest possible water elevation will always be composed of an eight-cell lake or pond with a spillway value of nine. This moat is not centered in a(n) > 5 but has the square's edge as one of its borders.
A number square contains the numbers 1 to n^2 without repeats.
The larger terms in this sequence are a(n) = n*(n+6) or A028560.

			For the 6 X 6 number square the largest value is 36 which is assigned to the single-cell island.
I only include the pertinent moat, spillway, and island values for the 6 X 6 example.
( 1   2   3    )
( 8  36   4  9 )
( 7   6   5    )

Craig Knecht, Maximum island elevation above sea level in a number square
Wikipedia, Water retention on mathematical surfaces

Cf. A054247, A201126.

Conjectures from Colin Barker, May 09 2017: (Start)
G.f.: x^4*(16 - 21*x + 7*x^2) / (1 - x)^3.
a(n) = n^2 + 2*n - 8 for n>3.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>6.
(End)

A364794 Number of distinct binary arrays of size n X n with respect to isometric transformations.

Original entry on oeis.org

1, 2, 6, 86, 7626, 3956996, 8326366368, 69277957195904, 2287898999182608384, 301053169143557925650432, 158147142250171927345054089216, 331982638848895606930198405868158976, 2786232352655643085145552249123037486514176

Offset: 0

Johnny Sammon, Aug 08 2023

			For n = 2, the a(2) = 6 distinct binary arrays are
  OO  XO  XX  XO  XX  XX
  OO  OO  OO  OX  XO  XX
For n = 4
  OOXX                                OOXO
  OXXO  is considered equivalent to   XXXX
  OOXO                                OOOX
  OOXO                                OOOO
because we can rotate the bounding box of the Xs 90 degrees clockwise and place it back into the array as given above.

Johnny Sammon, Counting Distinct Binary Arrays With Respect To Isometric Transformations.

Cf. A054247 (without shift), A255016 (on n X n torus).

A140795 We consider how many ways there are of coloring a square grid, n X n, using just two colors, black & white say. If the resulting grid has rotational symmetry of order two only, then the number of different grids is given by this sequence. None of these counted are the images of any of the others under a reflection or a rotation of 90 degrees. If one wishes to count these as different, then each of these numbers can be multiplied by 4.

Original entry on oeis.org

0, 0, 2, 44, 1792, 64288, 8354304, 1073447424, 549738528768, 281474691514368, 576460717407862784, 1180591619583540985856, 9671406556633359531900928, 79228162514246041720191975424, 2596148429267404554864448650608640, 85070591730234614676028659138035712000

Offset: 1

Anthony C Robin, Jul 15 2008

nonn

Cf. A054247, A054407.

s=[0]; for(m=1, 15, s=concat(s, [(2^(2*m^2)-2^m^2*(2^m+2)+2^((m^2+m+2)/2))/4, 2^(2*m^2+2*m-1)-2^(m^2-1)*(2^(2*m+1)+2^m)+2^(m*(m+3)/2)])); s \\ Colin Barker, Mar 28 2014

a(2m+1) = 2^(2*m^2 + 2*m - 1) - 2^(m^2 - 1)*(2^(2*m + 1) + 2^m) + 2^(m*(m + 3)/2).

a(2m) = (2^(2*m^2) - 2^m^2*(2^m + 2) + 2^((m^2 + m + 2)/2))/4.

More terms from Colin Barker, Mar 28 2014

cp's OEIS Frontend

A286430 Least volume of water to surround the largest possible island in a number square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A361870 Array read by downward antidiagonals: A(n,k) is the number of nonequivalent 2-colorings of the cells of an n-dimensional hypercube with edges k cells long under action of symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A275798 One half of the number of n X n square grids with squares of two colors modulo operations of the dihedral group D_4.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A286429 Highest elevation of an island above sea level in a number square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A364794 Number of distinct binary arrays of size n X n with respect to isometric transformations.

Views

Author

Keywords

Examples

Links

Crossrefs

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

Extensions

A335014 Row sums of A331462.

Views

Author

Keywords

Crossrefs