cp's OEIS Frontend

A374087 a(n) is the number of ways to partition {1,2,...,n} into two sets X and Y such that the sum of the elements of each is a square.

%I A374087 #27 Jul 05 2024 03:42:07
%S A374087 1,1,0,0,1,0,0,0,1,8,0,0,0,0,0,0,365,8,0,0,0,0,0,0,0,91514,0,0,0,0,0,
%T A374087 0,0,0,0,0,104742767,0,0,0,6519062,0,0,0,0,0,0,0,0,531168463492,0,0,
%U A374087 15329991499,0,0,0,0,0,0,0,0,0,0,0,11530164811834907,0,0,0,0
%N A374087 a(n) is the number of ways to partition {1,2,...,n} into two sets X and Y such that the sum of the elements of each is a square.
%C A374087 {X, Y} satisfies the property if there exists an integer k such that n*(n+1)/2 - k^2 is a square, where k^2 is the sum of the elements of X and n*(n + 1)/2 - k^2 the sum of the elements of Y.
%C A374087 Note that k can also be zero. If n is A001108(k), i.e., if n*(n + 1)/2 is a perfect square, it suffices to take X = {1, 2, ..., n} and Y = { }.
%C A374087 a(n) > 0 if and only if n is a term of A140612.
%C A374087 Proof: (==>) If n is such that a(n) > 0, then it is possible to partition {1,2,...,n} into two sets, X and Y, whose sums of elements are b^2 and c^2, respectively, for some integers b, c. Then, n*(n + 1)/2 = b^2 + c^2, so, n*(n + 1) = 2*(b^2 + c^2) = (b + c)^2 + (b - c)^2, i.e., n*(n + 1) is a sum of two squares, whence necessarily n and (n + 1) are sums of two squares. Thus, n is in A140612.
%C A374087 (<==) If n is A140612, then n and (n + 1) are sums of two squares, whence it follows that n*(n + 1) is a sum of 2 squares and is also even. Then n*(n + 1)/2 is also a sum of two squares. Then, there exist integers k and m such that n*(n + 1)/2 = k^2 + m^2, so that n*(n + 1)/2 - k^2 = m^2. Therefore, given the set {1,2,...,n}, if we choose X such that the sum of the elements is k^2, it follows that a(n) > 0.
%e A374087 If n = 4, then the only way is {1}, {2, 3, 4}.
%e A374087 If n = 8, then the only way is { }, {1, 2, 3, 4, 5, 6, 7, 8}.
%e A374087 If n = 9, there are 8 ways, which are shown below:
%e A374087   {9},  {1, 2, 3, 4, 5, 6, 7, 8}
%e A374087   {1, 8}, {2, 3, 4, 5, 6, 7, 9}
%e A374087   {2, 7}, {1, 3, 4, 5, 6, 8, 9}
%e A374087   {3, 6}, {1, 2, 4, 5, 7, 8, 9}
%e A374087   {4, 5}, {1, 2, 3, 6, 7, 8, 9}
%e A374087   {1, 2, 6}, {3, 4, 5, 7, 8, 9}
%e A374087   {1, 3, 5}, {2, 4, 6, 7, 8, 9}
%e A374087   {2, 3, 4}, {1, 5, 6, 7, 8, 9}
%e A374087 In each of the 8 cases, the sum of the elements of the subsets are 9 and 36, respectively.
%e A374087 If n = 25, there are 91514 ways. Some examples with sums different from each other:
%e A374087   {1}, {2, 3, ..., 25}, where the sums are 1^2 and 18^2, respectively.
%e A374087   {1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, ..., 25}, where the sums are 6^2 and 17^2.
%e A374087   X = {6, 22, 23, 24, 25}, Y = {1, 2, ..., 25} - X, whose sums are 10^2 and 15^2.
%Y A374087 Cf. A000217, A000290, A002849, A140612, A001108.
%K A374087 nonn
%O A374087 0,10
%A A374087 _Gonzalo Martínez_, Jun 27 2024
%E A374087 a(36)-a(68) from _Alois P. Heinz_, Jun 29 2024