A278329 -id:A278329 - cp's OEIS frontend

A278339 Number of set partitions of [n] into subsets whose element sums are distinct squares.

1, 1, 0, 0, 1, 0, 1, 0, 1, 23, 9, 41, 248, 277, 1556, 2854, 5233, 20701, 145137, 1626890, 4118910, 9963276, 9260756, 64027363, 365237571, 1002679107, 21594036300, 24465529531, 144914973347, 1921444799766

Offset: 0

Alois P. Heinz, Nov 18 2016

nonn

			a(0) = 1: {}.
a(1) = 1: 1.
a(4) = 1: 1|234.
a(6) = 1: 1|2356|4.
a(8) = 1: 12345678.
a(9) = 23: 12345678|9, 123568|4|79, 1236789|45, 1245789|36, 126|345789, 12589|367|4, 1258|3679|4, 12679|358|4, 1267|3589|4, 1345689|27, 135|246789, 13|24568|79, 13579|268|4, 1357|2689|4, 13678|259|4, 13|259|4678, 13|2689|457, 13|268|4579, 156789|234, 18|2345679, 169|23578|4, 1789|2356|4, 178|23569|4.
a(10) = 9: 1|2356|4|78(10)|9, 1|23578|4|6(10)|9, 1|258(10)|367|4|9, 1|258(10)|36|4|79, 1|259|36|4|78(10), 1|267(10)|358|4|9, 1|268|357(10)|4|9, 1|27|3589|4|6(10), 1|27|358|4|69(10).

Cf. A252897, A275780, A278329, A278340, A281994.

A252897 Rainbow Squares: a(n) = number of ways to pair the integers 1 to 2n so that the sum of each pair is a square.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 6, 18, 12, 36, 156, 295, 429, 755, 2603, 7122, 19232, 32818, 54363, 172374, 384053, 933748, 1639656, 4366714, 20557751, 83801506, 188552665, 399677820, 640628927, 2175071240, 8876685569, 32786873829, 108039828494, 351090349416

Offset: 0

Gordon Hamilton, Mar 22 2015

nonn

The original sequence is from Henri Picciotto, who asked for which n is such a pairing possible: A253472.
The name "rainbow squares" refers to the use of this problem in the elementary school classroom where children draw colored connecting "rainbows" to make the pairings.
Number of perfect matchings in the graph with vertices 1 to 2n and edges {i,j} where i+j is a square. - Robert Israel, Mar 22 2015

			One of the solutions for n=13 consists of the following pairings of 1-26:
  {1,15}, adding to 16;
  {2,23}, {3,22}, {4,21}, {5,20}, {6,19}, {7,18}, {8,17}, {9,16}, {11,14}, {12, 13}, each adding to 25;
  {10,26}, adding to 36;
  {24,25}, adding to 49.
There are five other such pairings possible, so a(13) = 6.

Martin Fuller, Table of n, a(n) for n = 0..42
Gordon Hamilton, Kiran S. Kedlaya, and Henri Picciotto, Square-Sum Pair Partitions, The College Mathematics Journal, Vol. 46, No. 4 (September 2015), pp. 264-269.

Cf. A253472, A278329, A278339.

F:= proc(S)
  option remember;
  local s, ts;
  if nops(S) = 0 then return 1 fi;
  s:= S[-1];
  ts:= select(t -> issqr(s+t),S minus {s});
  add(procname(S minus {s,t}), t = ts);
end proc:
seq(F({$1..2*n}), n = 0 .. 24); # Robert Israel, Mar 22 2015

F[S_] := F[S] = Module[{s, ts}, If[Length[S] == 0, Return[1]]; s = S[[-1]]; ts = Select[S ~Complement~ {s}, IntegerQ[Sqrt[s + #]]&]; Sum[F[S ~Complement~ {s, t}], {t, ts}]];
Table[Print[n]; F[Range[2 n]], {n, 0, 24}] (* Jean-François Alcover, Mar 19 2019, after Robert Israel *)

a(26)-a(30) from Hiroaki Yamanouchi, Mar 25 2015
a(31) from Alois P. Heinz, Nov 16 2016
a(32)-a(36) from Linus and Joost VandeVondele, Jun 07 2018
a(37)-a(39) from Bert Dobbelaere, Aug 09 2022

A281706 Number of sets of three positive numbers <= n whose sum is a square.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 5, 8, 11, 15, 20, 26, 33, 40, 48, 57, 67, 80, 93, 107, 121, 136, 153, 172, 193, 214, 236, 259, 284, 311, 340, 371, 402, 433, 466, 501, 538, 577, 618, 661, 705, 751, 798, 847, 897, 949, 1002, 1057, 1115, 1176, 1239, 1303, 1369, 1436, 1505

Offset: 0

Alois P. Heinz and Robert G. Wilson v, Jan 28 2017

Inspired by A278329.

a(n) >= a(n-1), first differences are nondecreasing.

			a(1) .. a(3) = 0;
a(4) = 1 since 2+3+4 = 9;
a(5) = 2 since 2+3+4 = 1+3+5 = 9;
a(6) = 3 since 2+3+4 = 1+3+5 = 1+2+6 = 9;
a(7) = 5 since a(6) = 3 plus 3+6+7 = 4+5+7 = 16;
a(8) = 8 since a(7) = 5 plus 1+7+8 = 2+6+8 = 3+5+8 = 16; etc.

Alois P. Heinz and Robert G. Wilson v, Table of n, a(n) for n = 0..20000

Cf. A176615, A278329.

Column k=3 of A281871.

g:= (n, t)-> max(0, iquo(n-1, 2)-max(1, n-t)+1):
b:= n-> add(g(k^2-n, n-1), k=ceil(sqrt(n+3))..floor(sqrt(3*n-3))):
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+b(n)) end:
seq(a(n), n=0..100);

f[n_] := Length@ Select[Plus @@@ Subsets[ Range@ n, {3}], Mod[ Sqrt[#], 1] == 0 &]; Array[f, 65] (* or *)
f = Compile[{{n, _Integer}}, Block[{a = 1, b = 2, c = 3, cnt = 0}, While[a < b, b = a +1; While[b < c, c = b +1; While[c < n +1, If[ Mod[ Sqrt[a + b + c], 1] == 0, cnt++]; c++]; b++]; a++]; cnt]]; Array[f, 65] (* or *)
g = Compile[{{n, Integer}}, If[n < 4, 0, Block[{a = 1, b = 2, cnt = f[n -1]}, While[a < b, b = a +1; While[b < n, If[ Mod[ Sqrt[a + b + n], 1] == 0, cnt++]; b++]; a++]; cnt]]]; f[n] := f[n] = g[n]; Array[f, 100]

A295946 Number of set partitions of [3n] into n subsets of size three such that all element sums are triangular numbers.

Original entry on oeis.org

1, 1, 1, 2, 17, 149, 1439, 16993, 373393, 6899469, 214746442, 7287992421

Offset: 0

Alois P. Heinz, Nov 30 2017

			a(0) = 1: {}.
a(1) = 1: {{1,2,3}}.
a(2) = 1: {{1,2,3}, {4,5,6}}.
a(3) = 2: {{1,6,8}, {2,4,9}, {3,5,7}}, {{1,5,9}, {2,6,7}, {3,4,8}}.
a(4) = 17: {{1,2,12}, {3,8,10}, {4,6,11}, {5,7,9}}, {{1,2,12}, {3,7,11}, {4,8,9}, {5,6,10}}, {{1,3,11}, {2,9,10}, {4,5,12}, {6,7,8}}, {{1,6,8}, {2,9,10}, {3,7,11}, {4,5,12}}, {{1,9,11}, {2,3,10}, {4,5,12}, {6,7,8}}, {{1,9,11}, {2,6,7}, {3,8,10}, {4,5,12}}, {{1,4,10}, {2,8,11}, {3,6,12}, {5,7,9}}, {{1,5,9}, {2,8,11}, {3,6,12}, {4,7,10}}, {{1,9,11}, {2,5,8}, {3,6,12}, {4,7,10}}, {{1,3,11}, {2,7,12}, {4,8,9}, {5,6,10}}, {{1,5,9}, {2,7,12}, {3,8,10}, {4,6,11}}, {{1,9,11}, {2,7,12}, {3,4,8}, {5,6,10}}, {{1,9,11}, {2,7,12}, {3,8,10}, {4,5,6}}, {{1,8,12}, {2,3,10}, {4,6,11}, {5,7,9}}, {{1,8,12}, {2,9,10}, {3,5,7}, {4,6,11}}, {{1,8,12}, {2,4,9}, {3,7,11}, {5,6,10}}, {{1,8,12}, {2,9,10}, {3,7,11}, {4,5,6}}.

Cf. A000217, A278329.

b:= proc(s) option remember; `if`(s={}, 1, (j->
      add(add(`if`(i b({$1..3*n}):
seq(a(n), n=0..7);

b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]},
     Sum[Sum[If[i < j && k < i && IntegerQ@Sqrt[(k + i + j)*8 + 1],
     b[s ~Complement~ {k, i, j}], 0], {k, s}], {i, s}]]];
a[n_] := b[Range[3n]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 9}] (* Jean-François Alcover, Mar 08 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A278339 Number of set partitions of [n] into subsets whose element sums are distinct squares.

Views

Author

Keywords

Examples

Crossrefs

A252897 Rainbow Squares: a(n) = number of ways to pair the integers 1 to 2n so that the sum of each pair is a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A281706 Number of sets of three positive numbers <= n whose sum is a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A295946 Number of set partitions of [3n] into n subsets of size three such that all element sums are triangular numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica