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,5

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.

Links

Table of n, a(n) for n=1..89.

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.

Example

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.

Prog

(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

Crossrefs

Cf. A082652.

Sequence in context: A380541 A230404 A378725 * A082647 A367627 A214018

Adjacent sequences: A379745 A379746 A379747 * A379749 A379751 A379752

Keyword

nonn

Author

Michael Adams, Jan 02 2025

Status

approved