cp's OEIS Frontend

A051014 Number of nondividing sets on {1,2,...,n}.

%I A051014 #31 Feb 16 2025 08:32:41
%S A051014 1,2,3,5,7,11,14,21,27,38,52,73,90,123,159,211,263,344,413,535,658,
%T A051014 832,1026,1276,1499,1846,2226,2708,3229,3912,4592,5541,6495,7795,9207,
%U A051014 10908,12547,14852,17358,20493,23709,27744,31921,37250,43013,49936,57319,66318
%N A051014 Number of nondividing sets on {1,2,...,n}.
%C A051014 A set is called nondividing if no element divides the sum of any nonempty subset of the other elements.
%H A051014 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/NondividingSet.html">Nondividing Set</a>
%e A051014 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}.
%e A051014 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}.
%p A051014 sums:= proc(s) option remember; local i, m;
%p A051014           m:= max(s[]);
%p A051014          `if`(m<1, {}, {m, seq([i,i+m][], i=sums(s minus {m}))})
%p A051014        end:
%p A051014 b:= proc(i,s) option remember; local j, ok, t, si;
%p A051014       if i<2 then 1
%p A051014     else si:= s union {i};
%p A051014          ok:= true;
%p A051014          for j in sums(si) while ok do
%p A051014            for t in si while ok do
%p A051014              if irem(j, t)=0 and t<>j then ok:= false fi
%p A051014            od
%p A051014          od;
%p A051014          b(i-1,s) +`if`(ok, b(i-1, si), 0)
%p A051014       fi
%p A051014     end:
%p A051014 a:= n-> `if`(n=0, 1, 1+b(n, {})):
%p A051014 seq(a(n), n=0..25);  # _Alois P. Heinz_, Mar 08 2011
%t A051014 sums[s_] := sums[s] = Module[{m=Max[s]},
%t A051014 If[m<1, {},
%t A051014   Join[{m},
%t A051014   Sequence@@Table[{i,i+m}, {i,sums[DeleteCases[s,m]]}]]]
%t A051014 ];
%t A051014 b[i_,s_] := b[i,s] = Module[{ ok,si,sij,sik},
%t A051014 If[ i<2, 1, si = Union[s,{i}];
%t A051014 ok = True;
%t A051014 For[j=1, j <= Length[sums[si]] && ok, j++,
%t A051014   sij = sums[si][[j]];
%t A051014   For[k=1, k <= Length[si] && ok, k++,
%t A051014     If[Divisible[sij,sik=si[[k]]]&&sij!=sik,ok=False]]];
%t A051014     b[i-1, s] + If[ok, b[i-1,si],0]
%t A051014   ]
%t A051014 ];
%t A051014 a[n_] := a[n] = If[n==0, 1, 1+b[n, {}]];
%t A051014 Table[ Print[ a[n] ]; a[n], {n,0,47}]
%t A051014 (* _Jean-François Alcover_, Oct 10 2012, after _Alois P. Heinz_ *)
%Y A051014 Row sums of A187489. Cf. A068063.
%K A051014 nonn,nice
%O A051014 0,2
%A A051014 _Eric W. Weisstein_
%E A051014 More terms from _David Wasserman_, Feb 15 2002
%E A051014 a(41)-a(47) from _Alois P. Heinz_, Mar 08 2011