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
Keywords
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.
Comments