Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #18 Jun 24 2021 02:26:54
%S 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,
%T 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,
%U 6,8,4,4,9,4,2
%N 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.
%C Note that rectangles of size 0 are not accepted (i.e., the tiles may not be formed into a single rectangle).
%C Finding a(n) is equivalent to counting the positive integer solutions (x,y,z,w) of n = xy + zw such that:
%C i) x,y,z,w <= ceiling(sqrt(n))
%C ii) min(x,y) + min(w,z) <= ceiling(sqrt(n))
%C iii) x >= y,z,w
%C iv) z >= w
%C v) if x = z then y >= w
%C 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.
%C 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.
%C iii)-v) ensure that rectangles are not double counted through permuting the values of the variables.
%H Thomas Oléron Evans, <a href="/A338664/b338664.txt">Table of n, a(n) for n = 1..9999</a>
%e a(18) = 4.
%e 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:
%e 1) 4 X 3 and 3 X 2
%e 2) 4 X 4 and 2 X 1
%e 3) 5 X 2 and 4 X 2
%e 4) 5 X 3 and 3 X 1
%e Case 1 Case 2 Case 3 Case 4
%e 1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - -
%e 1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - 2
%e 1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2
%e 1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2
%e - - - 2 2 - - - - - - - - - - 1 1 1 - -
%e 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.
%o (Python)
%o import numpy as np
%o # This sets the number of terms:
%o nits = 20
%o # This list will contain the complete sequence:
%o seq_entries = []
%o # i is the index of the term to be calculated:
%o for i in range(1, nits + 1):
%o # This variable counts the rectangle pairs:
%o count = 0
%o # Calculate the side length of the minimal bounding square:
%o bd_sq_side = np.ceil(np.sqrt(i))
%o # Looking for pairs of rectangles of sizes a x b and c x d (all integers)
%o # such that both can fit orthogonally into the minimal bounding square (integer side length)
%o # WLOG suppose that:
%o # a is the greatest of a, b, c, d...
%o # c >= d
%o # if a = c then b >= d
%o # a rectangle of size 0 X 0 is not acceptable
%o # The longest side length of either rectangle:
%o for a in np.arange(1,bd_sq_side + 1):
%o # The other side length of the same rectangle:
%o for b in np.arange(1,1 + min(a,np.floor(i/a))):
%o # Find the remaining area for the other rectangle:
%o area_1 = a*b
%o rem_area = i - area_1
%o # If there is no remaining area, the first rectangle is not valid:
%o if rem_area == 0:
%o continue
%o # The shorter side of the second rectangle:
%o for d in np.arange(1,1 + min(a,np.floor(np.sqrt(rem_area)))):
%o # The longer side of the second rectangle:
%o c = rem_area / d
%o # Check that the solution is valid:
%o if b + d <= bd_sq_side and c == int(c) and c <= bd_sq_side and c <= a and ((a != c) or (b >= d)):
%o count += 1
%o # Add the entry calculated to the list
%o seq_entries.append(count)
%o for an in seq_entries:
%o print(an)
%Y 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).
%K nonn
%O 1,5
%A _Thomas Oléron Evans_, Apr 22 2021