A379748 a(n) is the number of ways to arrange any number of unit square cells into an i X j rectangle which contains exactly n square subarrays of all sizes.

1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 3, 1, 1, 2, 2, 1, 3, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 1, 2, 1, 1, 4, 1, 1, 2, 1, 2, 3, 1, 1, 2, 2, 1, 3, 1, 1, 2, 1, 1, 3, 1, 3, 2, 1, 1, 3, 1, 1, 2, 1, 1, 4, 1, 1, 2, 1, 2, 3, 1, 1, 2

Offset: 1

Author

Michael Adams, Jan 02 2025

Keywords

• nonn

Comments

For this sequence, an i X j array and a j X i array are considered identical.

The number of different squares in an m X k array is S(m,k) = k(k+1)(3m-k+1)/6 = A082652(m,k) so that a(n) = the number of solutions to S(m,k) = n with m >= k.

a(n) has no upper bound.

It appears all natural numbers appear in the sequence. This is merely conjectured, but is provably true if there are an infinite amount of Sophie-Germain primes.

Examples

			For n=8, the a(8) = 2 rectangular arrays are
  -------------------------
  |A |B |C |D |E |F |G |H |
  -------------------------
and
  ----------
  |A |B |C |
  ----------
  |D |E |F |
  ----------
The first contains n = 8 unit squares (and none bigger).
The second contains 6 unit squares and two 2 X 2 squares (ABDE, BCEF), for S(3,2) = 8 = n squares.
		

Crossrefs

Cf. A082652.

Programs

Python

def a(n):
  output = 0
  k = 1
  while k*(k+1)*((2*k)+1) <= 6*n:
    if (n - (k*(k+1)*((2*k)+1)//6)) % (k*(k+1)//2) == 0:
      output += 1
    k += 1
  return output

Formula

a(n) = Sum_{k=1...N} [n == k(k+1)(2k+1)/6 (mod k(k+1)/2)] where [] is the Iverson bracket and N is the largest natural number such that N(N+1)(2N+1)/6 <= n.