OFFSET
1,5
COMMENTS
Note that rectangles of size 0 are not accepted (i.e., the tiles may not be formed into a single rectangle).
Finding a(n) is equivalent to counting the positive integer solutions (x,y,z,w) of n = xy + zw such that:
i) x,y,z,w <= ceiling(sqrt(n))
ii) min(x,y) + min(w,z) <= ceiling(sqrt(n))
iii) x >= y,z,w
iv) z >= w
v) if x = z then y >= w
Note that ceiling(sqrt(n)) is the side length of the minimal bounding square into which n unit square tiles can be orthogonally placed, without overlap.
Therefore, i) states that neither rectangle should be longer than the bounding square, while ii) states that the two rectangles must fit side by side within this square.
iii)-v) ensure that rectangles are not double counted through permuting the values of the variables.
LINKS
Thomas Oléron Evans, Table of n, a(n) for n = 1..9999
EXAMPLE
a(18) = 4.
18 unit square tiles fit orthogonally into a square of side length 5 (the minimum) without overlap. There are four possible pairs of rectangles that can be formed with the 18 tiles that can then be fit orthogonally into such a square without overlap:
1) 4 X 3 and 3 X 2
2) 4 X 4 and 2 X 1
3) 5 X 2 and 4 X 2
4) 5 X 3 and 3 X 1
Case 1 Case 2 Case 3 Case 4
1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - -
1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - 2
1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2
1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2
- - - 2 2 - - - - - - - - - - 1 1 1 - -
Note that other pairs of rectangles with total area 18, e.g., 3 X 3 and 3 X 3, or 6 X 2 and 3 X 2 are not counted, since they could not fit together into the minimal (5 X 5) bounding square.
PROG
(Python)
import numpy as np
# This sets the number of terms:
nits = 20
# This list will contain the complete sequence:
seq_entries = []
# i is the index of the term to be calculated:
for i in range(1, nits + 1):
# This variable counts the rectangle pairs:
count = 0
# Calculate the side length of the minimal bounding square:
bd_sq_side = np.ceil(np.sqrt(i))
# Looking for pairs of rectangles of sizes a x b and c x d (all integers)
# such that both can fit orthogonally into the minimal bounding square (integer side length)
# WLOG suppose that:
# a is the greatest of a, b, c, d...
# c >= d
# if a = c then b >= d
# a rectangle of size 0 X 0 is not acceptable
# The longest side length of either rectangle:
for a in np.arange(1, bd_sq_side + 1):
# The other side length of the same rectangle:
for b in np.arange(1, 1 + min(a, np.floor(i/a))):
# Find the remaining area for the other rectangle:
area_1 = a*b
rem_area = i - area_1
# If there is no remaining area, the first rectangle is not valid:
if rem_area == 0:
continue
# The shorter side of the second rectangle:
for d in np.arange(1, 1 + min(a, np.floor(np.sqrt(rem_area)))):
# The longer side of the second rectangle:
c = rem_area / d
# Check that the solution is valid:
if b + d <= bd_sq_side and c == int(c) and c <= bd_sq_side and c <= a and ((a != c) or (b >= d)):
count += 1
# Add the entry calculated to the list
seq_entries.append(count)
for an in seq_entries:
print(an)
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Oléron Evans, Apr 22 2021
STATUS
approved