OFFSET
0,10
COMMENTS
{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.
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 = { }.
a(n) > 0 if and only if n is a term of A140612.
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.
(<==) 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.
EXAMPLE
If n = 4, then the only way is {1}, {2, 3, 4}.
If n = 8, then the only way is { }, {1, 2, 3, 4, 5, 6, 7, 8}.
If n = 9, there are 8 ways, which are shown below:
{9}, {1, 2, 3, 4, 5, 6, 7, 8}
{1, 8}, {2, 3, 4, 5, 6, 7, 9}
{2, 7}, {1, 3, 4, 5, 6, 8, 9}
{3, 6}, {1, 2, 4, 5, 7, 8, 9}
{4, 5}, {1, 2, 3, 6, 7, 8, 9}
{1, 2, 6}, {3, 4, 5, 7, 8, 9}
{1, 3, 5}, {2, 4, 6, 7, 8, 9}
{2, 3, 4}, {1, 5, 6, 7, 8, 9}
In each of the 8 cases, the sum of the elements of the subsets are 9 and 36, respectively.
If n = 25, there are 91514 ways. Some examples with sums different from each other:
{1}, {2, 3, ..., 25}, where the sums are 1^2 and 18^2, respectively.
{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, ..., 25}, where the sums are 6^2 and 17^2.
X = {6, 22, 23, 24, 25}, Y = {1, 2, ..., 25} - X, whose sums are 10^2 and 15^2.
CROSSREFS
KEYWORD
nonn
AUTHOR
Gonzalo MartÃnez, Jun 27 2024
EXTENSIONS
a(36)-a(68) from Alois P. Heinz, Jun 29 2024
STATUS
approved