OFFSET
0,2
COMMENTS
A set is called nondividing if no element divides the sum of any nonempty subset of the other elements.
LINKS
Eric Weisstein's World of Mathematics, Nondividing Set
EXAMPLE
a(5) = 11 because there are 11 nondividing subsets of {1,2,3,4,5}: {}, {1}, {2}, {3}, {4}, {5}, {2,3}, {2,5}, {3,4}, {3,5}, {4,5}.
a(7) = 21: {}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {2,3}, {2,5}, {2,7}, {3,4}, {3,5}, {3,7}, {4,5}, {4,6}, {4,7}, {5,6}, {5,7}, {6,7}, {4,6,7}.
MAPLE
sums:= proc(s) option remember; local i, m;
m:= max(s[]);
`if`(m<1, {}, {m, seq([i, i+m][], i=sums(s minus {m}))})
end:
b:= proc(i, s) option remember; local j, ok, t, si;
if i<2 then 1
else si:= s union {i};
ok:= true;
for j in sums(si) while ok do
for t in si while ok do
if irem(j, t)=0 and t<>j then ok:= false fi
od
od;
b(i-1, s) +`if`(ok, b(i-1, si), 0)
fi
end:
a:= n-> `if`(n=0, 1, 1+b(n, {})):
seq(a(n), n=0..25); # Alois P. Heinz, Mar 08 2011
MATHEMATICA
sums[s_] := sums[s] = Module[{m=Max[s]},
If[m<1, {},
Join[{m},
Sequence@@Table[{i, i+m}, {i, sums[DeleteCases[s, m]]}]]]
];
b[i_, s_] := b[i, s] = Module[{ ok, si, sij, sik},
If[ i<2, 1, si = Union[s, {i}];
ok = True;
For[j=1, j <= Length[sums[si]] && ok, j++,
sij = sums[si][[j]];
For[k=1, k <= Length[si] && ok, k++,
If[Divisible[sij, sik=si[[k]]]&&sij!=sik, ok=False]]];
b[i-1, s] + If[ok, b[i-1, si], 0]
]
];
a[n_] := a[n] = If[n==0, 1, 1+b[n, {}]];
Table[ Print[ a[n] ]; a[n], {n, 0, 47}]
(* Jean-François Alcover, Oct 10 2012, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from David Wasserman, Feb 15 2002
a(41)-a(47) from Alois P. Heinz, Mar 08 2011
STATUS
approved