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.

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, 0, 0, 0, 0, 0, 104742767, 0, 0, 0, 6519062, 0, 0, 0, 0, 0, 0, 0, 0, 531168463492, 0, 0, 15329991499, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11530164811834907, 0, 0, 0, 0

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.

Links

Table of n, a(n) for n=0..68.

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

Cf. A000217, A000290, A002849, A140612, A001108.

Sequence in context: A306756 A340981 A079204 * A325737 A272625 A334709

Adjacent sequences: A374084 A374085 A374086 * A374088 A374089 A374090

Keyword

nonn

Author

Gonzalo Martínez, Jun 27 2024

Extensions

a(36)-a(68) from Alois P. Heinz, Jun 29 2024

Status

approved