|
%I #29 Jun 28 2022 03:30:55
%S 1,2,4,8,12,24,28,56,72,104,116,232,248,496,544,616,728,1456,1520,
%T 3040,3232,3616,3872,7744,8000,11168,11904,14656,15488,30976,31232,
%U 62464,69888,76160,80256,89856,91648,183296,192640,208640,214272,428544
%N Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor.
%C Also the number of subsets of {1,...,n} whose product of elements is equal to the least common multiple of elements. - _Michel Marcus_, Mar 27 2016
%D Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication. [Apparently unpublished as of 2016]
%H Alois P. Heinz, <a href="/A084422/b084422.txt">Table of n, a(n) for n = 0..220</a>
%H N. J. Calkin and A. Granville, <a href="http://www.math.clemson.edu/~calkin/Papers/calkin_granville.pdf">On the number of coprime-free sets</a>, Number Theory: New York Seminar 1991-1995 (eds. D. Chudnovsky, et.al.), Springer-Verlag (1996).
%H Marcel K. Goh and Jonah Saks, <a href="https://arxiv.org/abs/2206.12535">Alternating-sum statistics for certain sets of integers</a>, arXiv:2206.12535 [math.CO], 2022.
%F a(n) = 1 + Sum_{k=1..A036234(n)} A186974(n,k) if n>0; a(0) = 1.
%e Exactly 4 of the 2^4=16 subsets of the integers from 1 through 4 contain a pair of integers that share a common factor; these are {2,4}, {1,2,4}, {2,3,4} and {1,2,3,4}. The other 12 subsets do not; hence a(4)=12.
%t Prepend[Table[Length@ Select[Rest@ Subsets@ Range@ n, Times @@ # == LCM @@ # &], {n, 22}] + 1, 1] (* _Michael De Vlieger_, Mar 27 2016 *)
%o (PARI) a(n)=nb = 0; S = vector(n, k, k); for (i = 0, 2^n - 1, ss = vecextract(S, i); if (prod(k=1, #ss, ss[k]) == lcm(ss), nb++);); nb; \\ _Michel Marcus_, Mar 27 2016
%o (PARI) a(n,k=1)=if(n<2, return(n+1)); if(gcd(k,n)==1, a(n-1,n*k)) + a(n-1,k) \\ _Charles R Greathouse IV_, Aug 24 2016
%Y Cf. A051026 gives the number of primitive subsets. A087080 gives the number of elements in coprime subsets. A087081 gives the sum of the elements in coprime subsets.
%Y Cf. A036234, A186974.
%K nonn
%O 0,2
%A _Matthew Vandermast_, Jun 26 2003
%E More terms from Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 12 2003
|
