A338664 a(n) is the number of ways that n square tiles can be formed into two rectangles, such that those rectangles fit orthogonally into the minimal bounding square that can contain n such tiles, without overlap.

0, 1, 1, 1, 2, 2, 2, 1, 1, 4, 2, 4, 2, 2, 1, 2, 4, 4, 4, 4, 3, 2, 2, 1, 2, 6, 5, 6, 2, 7, 2, 3, 2, 2, 1, 3, 6, 6, 6, 5, 4, 6, 4, 2, 3, 2, 2, 1, 3, 8, 4, 10, 4, 6, 3, 9, 2, 4, 2, 3, 2, 2, 1, 4, 5, 10, 6, 6, 8, 4, 4, 9, 4, 2

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

Cf. A338671, A055507 (where a(n) is the number of ordered ways to express n+1 as a*b+c*d with 1 <= a,b,c,d <= n).

Sequence in context: A184948 A242775 A079562 * A199803 A304197 A348768

Adjacent sequences: A338661 A338662 A338663 * A338665 A338666 A338667

Keyword

nonn

Author

Thomas Oléron Evans, Apr 22 2021

Status

approved