cp's OEIS Frontend

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.

%I A379748 #41 Jan 15 2025 08:35:44
%S A379748 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,
%T A379748 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,
%U A379748 1,3,2,1,1,3,1,1,2,1,1,4,1,1,2,1,2,3,1,1,2
%N 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.
%C A379748 For this sequence, an i X j array and a j X i array are considered identical.
%C A379748 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.
%C A379748 a(n) has no upper bound.
%C A379748 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.
%F A379748 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.
%e A379748 For n=8, the a(8) = 2 rectangular arrays are
%e A379748   -------------------------
%e A379748   |A |B |C |D |E |F |G |H |
%e A379748   -------------------------
%e A379748 and
%e A379748   ----------
%e A379748   |A |B |C |
%e A379748   ----------
%e A379748   |D |E |F |
%e A379748   ----------
%e A379748 The first contains n = 8 unit squares (and none bigger).
%e A379748 The second contains 6 unit squares and two 2 X 2 squares (ABDE, BCEF), for S(3,2) = 8 = n squares.
%o A379748 (Python)
%o A379748 def a(n):
%o A379748   output = 0
%o A379748   k = 1
%o A379748   while k*(k+1)*((2*k)+1) <= 6*n:
%o A379748     if (n - (k*(k+1)*((2*k)+1)//6)) % (k*(k+1)//2) == 0:
%o A379748       output += 1
%o A379748     k += 1
%o A379748   return output
%Y A379748 Cf. A082652.
%K A379748 nonn
%O A379748 1,5
%A A379748 _Michael Adams_, Jan 02 2025