cp's OEIS Frontend

A196722 Number of subsets of {1..n} (including empty set) such that the pairwise LCMs of elements are not distinct.

%I A196722 #12 Apr 12 2017 15:21:42
%S A196722 1,2,4,7,11,16,23,30,38,47,58,69,83,96,111,128,144,161,181,200,223,
%T A196722 246,269,292,319,344,371,398,429,458,496,527,559,594,629,668,708,745,
%U A196722 784,825,870,911,962,1005,1052,1102,1149,1196,1248,1297,1349,1402,1457,1510
%N A196722 Number of subsets of {1..n} (including empty set) such that the pairwise LCMs of elements are not distinct.
%C A196722 All pairwise LCMs of each subset are equal if there are any.
%H A196722 Alois P. Heinz, <a href="/A196722/b196722.txt">Table of n, a(n) for n = 0..1000</a>
%e A196722 A(6) = 23: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6}, {4,5}, {4,6}, {5,6}, {2,3,6}.
%p A196722 b:= proc(n, s) local sn, m;
%p A196722       m:= nops(s);
%p A196722       sn:= [s[], n];
%p A196722       `if`(n<1, 1, b(n-1, s) +`if`(1 >= nops(({seq(seq(
%p A196722            ilcm(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
%p A196722     end:
%p A196722 a:= proc(n) option remember;
%p A196722       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
%p A196722     end:
%p A196722 seq(a(n), n=0..50);
%t A196722 b[n_, s_] := b[n, s] = Module[{sn, m}, m = Length[s]; sn = Append[s, n]; If[n<1, 1, b[n-1, s] + If[1 >= Length @ Union @ Flatten @ Table[ LCM[ sn[[i]], sn[[j]]], {i, 1, m}, {j, i+1, m+1}], b[n-1, sn], 0]]];
%t A196722 a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]];
%t A196722 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Apr 12 2017, translated from Maple *)
%Y A196722 Cf. A143823, A196719, A196720, A196721, A196723, A196724.
%K A196722 nonn
%O A196722 0,2
%A A196722 _Alois P. Heinz_, Oct 05 2011